BledDest's blog

By BledDest, 3 weeks ago, translation, In English

2260A - Monocarp's Contest

Tutorial
Solution

2260B - Monocarp and Projects

Tutorial
Solution

2260C - Maximize XOR, Minimize Operations

Tutorial
Solution

2260D - Signs of Prefix Sums

Tutorial
Solution

2260E - Cyclic Balance

Tutorial
Solution

2260F - Edge Three-Coloring

Tutorial
Solution

2260G - Sortable Permutations

Tutorial
Solution
  • Vote: I like it
  • +83
  • Vote: I do not like it

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The tutorials for problems will be available in a few minutes.

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

B felt like a bullet stuck in the ribs, nor does in come out nor was it blocked, felt suffocated!

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

A — easy, B, C literally 1500

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I guess I shall improve my implementation skills now, as I got WA on #2 5 times during contest while getting AC only require changing a few chars (my specific implementation was inferior to the official solution that made debugging harder, though). Submission: 389954784.

»
3 weeks ago, hide # |
← Rev. 3  
Vote: I like it +4 Vote: I do not like it

Solution to E without using binary search 389952685

  • »
    »
    11 days ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    if x1 is number of 00 , x2 is number of 11 and x3 is number of 01 then following function gives the answer

    int ans(int x1, int x2, int x3){
        if(x3 >= max(x1,x2)) return 2*x3 - x1 - x2;
        else if(x3 >= min(x1,x2)) return max(x1,x2) - min(x1,x2) + 2*((max(x1,x2) - x3)%2);
        else{
            if((max(x1,x2) - min(x1,x2)) >= (min(x1,x2) - x3)) return max(x1,x2) - min(x1,x2) + 2*((max(x1,x2) - x3)%2);
            else{
                int d = 2*min(x1,x2) - max(x1,x2) - x3;
                return max(x1,x2) - min(x1,x2) + 2*(d/3) + 2*(d%3);
            }
        }
    }
    
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I was close to solving D , just kept trying to find a arrangement of the prefix that is optimal by considering block interval sizes (if its odd , then it can have 1 , 1 on the ends optimal).

figured prefix would only take value between [-2 , 2] .

  • »
    »
    3 weeks ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +1 Vote: I do not like it

    The prefix values need not be in [-2, 2], Example : -++++-, Answer : 2, Construction : (-1, 2, 2, -1, -1, -2), Prefix : (-1, 1, 3, 2, 1, -1), I too got one WA due to missing this case where increasing by 2 while positive makes sign transition using -2 possible.

»
3 weeks ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Good contest, tho I couldn't solve C. I found the obervation where we need $$$x$$$ $$$AND$$$ $$$y$$$ $$$=$$$ $$$0$$$ but I couldn't do anything further

»
3 weeks ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

It seems that I was able to somehow find all the possible cases and ended up just if-else my solution for D, submission — https://codeforces.me/contest/2260/submission/389959167

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

6 successful hacking attempts(tl) on C, E and F :>

»
3 weeks ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Why isn't this blog more openly visible. I had to go to dude's profile to get this.

»
3 weeks ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

I have another approach for D. We can just consider few cases and decide if its -1,1,2 or 3.

1) If 1st char is 0 or there are consecutive 0s then -1

2) Now we set ans=1

3) If + and — are adjacent anywhere or there are even number of — or even number of + between 2 0s then we update ans to 2

4) If we encounter +--+ or -++- then we update it to 3

There's code in previous Rev

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Another necessary and sufficient condition for problem E is $$$cnt_0 = cnt_1 = numFlips$$$ where $$$numFlips$$$ represents $$$cnt_{01} + cnt_{10}$$$

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Anyone else found their questions skipped? What could be the potential reasons?

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My unusual solution for C was doing binary-search on every possible combination of bits to find the maximum <= x. But I have now realized that I could have done it greedily.


#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = 1e18; #define all(x) x.begin(),x.end() #define int long long #define pb push_back #define endl "\n" void fastIO() {ios::sync_with_stdio(false);cin.tie(NULL);} int32_t main() { fastIO(); int t;cin>>t; while (t--){ int x,y;cin>>x>>y; vector<int> bits; for (int i=0;i<29;i++){ if ((y+x)&(1<<i)){ bits.pb((1<<i)); } } int bbb=(1<<(bits.size()))-1; int l=0; int r=bbb; int ans=0; // print(bits); while (l<=r){ int mid=l+(r-l)/2; int tot=0; for (int i=0;i<bits.size();i++){ if (mid&(1<<i))tot+=bits[i]; } // cout<<mid<<" "<<tot<<endl; if (tot<=x){ ans=tot; l=mid+1; } else{ r=mid-1; } } cout<<y+x<<" "<<x-ans<<endl; } return 0; }
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

nice contest, learn a lot tysm

»
3 weeks ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Alternative solution for F:

After seeing that the edges colored 1 and 2 must form a cycle, we also observe that this cycle must have length $$$\leq m-n+1$$$. This is because the graph still needs to be connected after removing the cycle. The minimum number of edges needed for a graph of size $$$n$$$ to be connected is $$$n-1$$$ edges, so if the cycle was more than $$$m-n+1$$$ edges long, it is impossible for the graph to be connected after removing them.

So, we just run a dfs starting from each node, with a max depth of 10, finding every cycle candidate containing that node. The complexity should be the same as in the official solution.

Submission: 390181201

  • »
    »
    3 weeks ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it

    There can be many paths of length at most $$$10$$$. Enumerating all of them may be too slow. Consider for example this graph:

    Graph
    • »
      »
      »
      3 weeks ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +10 Vote: I do not like it

      You are right about that. I think repeatedly removing leaves of the graph until only nodes of degree $$$\geq 2$$$ are left will reduce the amount of paths by an order of $$$n$$$, since the sum of degrees of all nodes will be $$$\leq 2n+20$$$, and the maximum degree of any node will also be 20. It should pass within the time limit now.

      390263643

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Problem D can also be solved by greedy 390216387

»
3 weeks ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

tourist where to learn each topics for competetive programming

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What I did for F: We take only 1 edge of colour 1. Now we need to find a path connecting the 2 nodes of that edge which can be coloured 2. Since colour 3 must form atleast a tree, the nodes of all the 1 or 2 coloured edges must have degree atleast 3. So we find edges which will have both vertices of degree atleast 3. It feels that such edges should be low when m<=n+9. (It turns out that such edges are atmost 27). Then for each such edge say e={u,v} we try to find a path of length atmost m-n edges (with vertices that must belong to those precalculated 3 degree egdes) from u to v via DFS and if we find a path we then check if the remaining 3 colour edges form a connected tree. We are doing like DFS inside DFS so I didn't think it would work but idk it worked somehow.

Submission: 390066836

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I passed F with DFS and union-find disjoint sets. Actually it just like brute force. But it runs faster than the tutorials' solution. (lol)

390234644

(I'm sorry for the terrible variable name.)

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Problem E can be solve in $$$O(n+q)$$$ 390259364

The logic is

1.Simulate adding 0/1,we observe that we can increase #00 when #00>0/#01/#10 > 0,increase #01/10 when #00>0/#11>0 ,increase #11 when #11>0 /#01/10 > 0

2.From step 2,we observe #01/10 is always increase same unit and the problem didn't say there is impossible condition,this lead me think that #01 and #10 is always same otherwise it can't exist solution,and the truth is it can be show that #01 and #10 is always same

3.now we got a element u=(x,y1,y2,z) x=#00,y1=#01,y2=#10,z=#11,the problem reduce to the minimum operation to make all number in u equal,and since from step 2 ,y1 always equal y2,then we may cut one of them into u=(x,y,z)

4.Problem now is minimum operation to make all element in (x,y,z) equal,and constraints is x/z can reduce 1 unit to increase y 1 unit,if x/z == 0 then can't perform this operation,if y>0 then x/z can increase 1 unit

5.Let m be the number of (x,y,z) final be,then it can be show that answer is $$$4\cdot m-(r-l+1)$$$ and $$$m = \max(1,y,\lceil \frac{x+y}{2} \rceil,\lceil \frac{y+z}{2} \rceil,\lceil \frac{x+y+z}{3} \rceil) $$$

Proof of step 5
»
2 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i hate tutorial of nowadays why there are no hints why direct solution hints give us the thought process required to solve a problem a novel problem

»
2 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In problem C, the editorial said lastly

Spoiler

Why is that ? why is that gives me the nearest true value smaller than x? why is that greedily work?

Why from the least significant to the most significant does not work?

  • »
    »
    2 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Explaination

    Assume x = 01101010 s = x + y = 11100010

    Our target to get the maximum number less than or equal to x and all its on bits are on in the s as well at the same positions.

    What i mean by that is if s = 1101 all of those answers are valid 0000 0001 0100 0101 1000 1001 1100 1101

    lets go bit by bit from left to right

    x = 01101010 s = 11100010

    x[0] = 0

    so ans[0] = 0 no matter what, because ans must be less than x. if ans[0] = 1 and x[0] = 0, so ans will be greater no matter what and this is not what we want.

    Remember we want to find the biggest number less than or equal to x and its on bits is also on bits in s "s = x + y".

    x[1] = 1

    lets see s[1].

    s[1] = 1

    so ans[1] = 1, right now ans will might be less than or equal to zero

    x[2] = 1

    s[2] = 1

    ans[2] should be equal to 1

    x[3] = 0

    ans[3] = 0

    x[4] = 1

    s[4] = 0

    ans[4] = 0 and it should be, because we can't have a bit in ans that is on and at the same position off at s.

    from now on, ans must be less than x, we should from now on MAXIMIZE ANS AS WE COULD, we make this by "whenever we see an on bit in s, make the bit in ans on as well and we do not afraid to be larger that x because x[4] = 1 and ans[4] = 0, so no matter what are the next bits in ans, ans will be smaller than x"

    this result to ans being equal to 01100010, and this is the maximum number less than or equal to x and at the same time all its bits are on at s at the same positions.

»
10 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

This is my solution on F, simple and easy



void solve() { int n, m; cin >> n >> m; // vector g(n + 1, vector(0 , 0)); const int M = m * 2 + 10; vector head(n + 1, 0), nex(M, 0), ver(M, 0), frm(M, 0); int gps = 1; auto add = [&] (int x, int y) -> void { ver[++gps] = y, nex[gps] = head[x], head[x] = gps; frm[gps] = x; swap(x, y); ver[++gps] = y, nex[gps] = head[x], head[x] = gps; frm[gps] = x; }; for (int i = 1; i <= m; ++i) { int x, y; cin >> x >> y; add(x, y); } vector vis(n + 1, 0); vector<int> sta; sta.reserve(m + 1); vector<int> tmp; tmp.reserve(m + 1); auto check = [&] (const vector<int> &now) -> int { vector<bool> book(gps + 1, 0); vector<int> fa(n + 1, 0); for (int i = 1; i <= n; ++i) { fa[i] = i; } auto find = [&] (auto &&find, int x) -> int { return x == fa[x] ? x : fa[x] = find(find, fa[x]); }; auto merge = [&] (int x, int y) -> void { x = find(find, x); y = find(find, y); if (x != y) fa[x] = y; }; for (int i : now) { book[i] = book[i ^ 1] = 1; } for (int i = 2; i <= gps; ++i) { if (!book[i]) { book[i] = book[i ^ 1] = 1; merge(ver[i], frm[i]); } } int rt = find(find, 1); for (int i = 1; i <= n; ++i) { if (find(find, i) != rt) return 0; } return 1; }; auto dfs = [&] (auto &&dfs, int x, int fa) -> int { vis[x] = 1; for (int k = head[x]; k; k = nex[k]) { int y = ver[k]; if (y == fa) continue; if (vis[y]) { tmp.clear(); for (int i = sta.size() - 1; i >= 0; --i) { if (ver[sta[i]] == y) break; tmp.push_back(sta[i]); } tmp.push_back(k); if (check(tmp)) return 1; } else { sta.push_back(k); if (dfs(dfs, y, x)) return 1; sta.pop_back(); } } vis[x] = 0; return 0; }; int ans = dfs(dfs, 1, 0); cout << (ans ? "YES" : "NO") << "\n"; }
»
9 days ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it
C spoiler, for newer users