majk's blog

Codeforces Global Round 6 Editorial
By majk, 5 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +159
  • Vote: I do not like it

Comments Comments (62)
| Write comment?
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Wow, fastest editorial out there!

→ Reply
»
5 years ago, # |
  Vote: I like it +97 Vote: I do not like it

Gap between E and F is HUUUUUGGGGGEEEEE :C

→ Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Fast Editorial and system testing :)

→ Reply
»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

epic F...

→ Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

wow fastest guide ever i have seen

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For D, you have given solution for min dept, how to find number of depts?

I did a greedy solution 67115957, can anyone please tell me why i am getting TLE.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yeeee. This is the fastest guide I've ever seen

→ Reply
»
5 years ago, # |
  Vote: I like it +81 Vote: I do not like it

For E , what ideally we should have done -" It is obvious that we cannot do better and this number is necessary. Let's prove that it is also sufficient. "

What most people did — " It is obvious that we cannot do better and this number is necessary. Let's submit."

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve D with rule 1 changed to d(a, b) and d(b, c) instead of d(a,b) and d(c, d)? If I understand that correctly, it means we cannot greedily match balances and we need to preserve (more or less) the original graph structure.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I also thought that it was important in the contest, but if you carefully read and understand all the limitations in the first operation, it will become clear that you can get any situation that is described in the solution.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yeah, I know, I managed to reread the problem statement after 1 hour and solved it, but I am wondering about a harder problem now :P

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry, confused in the letters :D

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.me/contest/1266/submission/6708325 Please someone can find mistake in my first question solution..

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Your link is incorrect. This one I think you mentioned. Try this test: 100. Your output I think red, instead of cyan.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -27 Vote: I do not like it

Thanks for the quick editorial!!!

→ Reply
»
5 years ago, # |
  Vote: I like it +74 Vote: I do not like it

H is very cool, one of my favorite problems now. Thanks!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello majk !

I want to ask something about problem C. Since it is a constructive algorithm task ; could you please describe the thought process involved while arriving at the construction.

PS : I also solved the problem in the contest ; however it took me a lot more time to derive the construction.

Thanks in advance !

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    Here is how I thought of it it, Since we have to produce minimum magnitude and all Gcds should be distinct, I thought the gcds should be of the form 1,2,3,4,5. I didn't know of this will work, but just a trail. I tried to produce gcd = 1. This can easily be done by writing 2,3. I also noticed that 1 cannot be written anywhere as it make gcds of column and row same. So in the first row I wrote 2,3,4,5,6,....,m + 1.after this I observed that I can make gcds of each column the topmost element if each column is a multiple of the topmost element. After this, I thought that if I multiply the first row by some number and write it in the second row, the gcds of the second row will be the number it was multiplied with as I can take the number common and the gcds of remaining elements is one. It's easy to see how this works after this.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks! I was just thinking like you, but missed to notice a silly mistake I was making in my logic, now I understand my mistake.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I think my solution for C plainly describes the thought process involved. here

    I created two arrays(one for row and one for column) that contains the targeted minimum disjoint gcd values that can be achieved ie { 1,2...r...(r+c) }then I filled the matrix by multiplying each row array element with column array element. By analyzing output you can infer {1...r} values can be achieved by taking gcd of each row and remaining {r+1...c} can be achieved by taking gcd of each column.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be really helpful if someone could provide the thought process required for C,as it is a constructive algo?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Since we want to minimise GCD we may want to start with putting 1 but we can't do so because it will make the GCD of that particular row and column 1 which will not satisfy condition that GCD values must be distinct. Firstly, try a simpler case like when r = 1 and c > 1, we can have values like 2,3,4,...c-1. Similarly, for case when c = 1 and r > 1. Now, Let us consider case when r = 3 and c = 3. Then in first row we can have 4,5,6 which have GCD = 1. Now observe that for second row we can multiply the first row by 2, which gives for second row 8,10,12 which will have GCD as 2. Similarly, third row will be 12,15,18 having GCD as 3. And for the first column GCD will be 4, second column GCD will be 5 and for third column GCD will be 6. So set of distinct values of GCD = {1,2,3,4,5,6} and also we can say that r+c will always be the optimal value.

    → Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

good contest !

Thanks majk !

→ Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Why is it clear in problem D that we can't do better than sum of balances divided by 2?

→ Reply
»
5 years ago, # |
  Vote: I like it +75 Vote: I do not like it

I have a linear-time solution (67124772) to F.

The idea is to make extensive use of the trivial data structure that maintains a set of integers and supports the following operations:

  1. Add value $$$v$$$ to the set (in $$$\mathcal{O}(v)$$$ time)
  2. Decrement value $$$v$$$ that appears in the set (in $$$\mathcal{O}(1)$$$)
  3. Output the maximum value in the set (in $$$\mathcal{O}(1)$$$)

To do this, just store for every value how many times the value appears in the set, and maintain the maximum.

We'll loop from $$$k = 1$$$ upwards, and maintain $$$dp[i] = $$$ number of subtrees of $$$i$$$ with depth at least $$$k$$$ (including parent). Then at step $$$k$$$ we have $$$ans[2k] = \max(\max_{i} dp[i], \max_{a, b \text{ adjacent}} dp[a] + dp[b] - 2)$$$ and $$$ans[2k-1] = \max_{i} dp[i] + \text{at least one of the subtrees of i has depth exactly } k-1$$$.

To maintain $$$dp[i]$$$, note that when we increase $$$k$$$ and calculate the new value $$$dp'[i]$$$, we have $$$dp'[i] = \sum_{t \in conns[i]} \max(1, dp[t]) - 1$$$. Hence we can store a queue of nodes whose some neighbour had their $$$dp[i]$$$ decreased to one in the previous step. The nodes in the queue are exactly the nodes whose $$$dp[i]$$$ will decrease in this step (multiple times if they appear multiple times). Since initially $$$dp[i] = deg(i)$$$, and they can only decrease, and we do updates to them in $$$\mathcal{O}(1)$$$ time, this part takes linear time.

We'll use one copy of the data structure to maintain values of $$$dp[i]$$$. To maintain the values we need to calculate $$$ans[2k-1]$$$, we'll maintain the values $$$dp[i] + \mathbb{I}[dp[i] \text{ got decremented in the previous step}]$$$ in another copy of the data structure.

Lastly, to maintain the values to calculate $$$ans[2k]$$$, we'll maintain for every node a copy of the data structure storing the current values of $$$dp[i]$$$ for its children. Note that every $$$dp[i]$$$ appears in exactly one such data structure, so to initialise and maintain them we again do only linear work. We'll also have a data structure storing the "active" values $$$dp[i] + \max_{c \in childs[i]} dp[c] - 2$$$. Whenever $$$dp[i]$$$ decreases, we decrement its active value, its parents children data structure, and its parents active value if $$$dp[i]$$$ was the unique maximum in the data structure. All the operations we'll ever do again take in total time equal to the sum of degrees, which is linear.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +20 Vote: I do not like it

    I have a similar solution to you, and the complexity is also linear: 67162965.

    We notice that the number of subtrees of $$$i$$$ with depth at least $$$k$$$ is always smaller than that of $$$k - 1$$$. So, instead of looping $$$k$$$ from $$$1$$$ upwards, we loop $$$k$$$ from $$$n$$$ downwards, which will make every variable in the computation non-decreasing, so we don't have to use any data structures; straight up updating every variable using the $$$max$$$ function is enough.

    Edit: Courtesy to GreymaneSilverfang for helping me with this discovery :D

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In D editorial can someone explain "We have just reduced the total debt by z, which is a contradiction."

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    We assume that the debt is already minimal, and there is a vertex triple such that ... We managed to reduce the debt, so it wasn't minimal. This means that for a minimal debt, there cannot be such triple.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

[DELETED]

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

In question D
for input:
6 4
1 2 6
2 3 4
4 5 3
5 6 5
is this a correct solution?:
4
1 6 5
4 3 3
5 2 2
1 3 1

Edit: It is .. nevermind

→ Reply
»
5 years ago, # |
  Vote: I like it +39 Vote: I do not like it

In problem H:

These two conditions are in fact necessary and sufficient.

How to prove that these conditions are sufficient?

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

https://codeforces.me/contest/1266/submission/67100495

Can someone tell why my solution is failing in D. Is there something to do with it out of bounds?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it 
             a[u] = 0;
         a[v] = a[v]+a[u];

    You should swap these two lines.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Shit. How could I make such mistake. Thanks for help.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the contest!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D
"It follows that any solution in which every vertex has either outgoing or incoming edges is constructible using finite number of applications of rules."
I couldn't understand why... How to prove it? Can someone explain?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "It follows that any solution in which every vertex has either outgoing or incoming edges is constructible using finite number of applications of rules." Because if there is combination of vertices like a->b->c then this combination surely results in a decreased total debt i.e. why using any number of operations we can achieve the state of graph where every vertex has either incoming or outgoing edge.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you,but why "any solution is constructible"...?
      I understood there exists the graph which we can construct where every vertex has either outgoing or incoming edges,but I don't think it is clear that we can construct "any" graphs that satisfies the condition.
      (I'm sorry if I misunderstood the editorial)

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For example, imagine that there is a answer a->b 10, c->d 10. In order to get another answer, we add two edges a->c 10 and c->a 10, then we could use the first rule to get another answer a->d 10, c->b 10

        → Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I'm really interested in yosupo's and eatmore's solutions to problem H.

It looks they are quite different from the intended solution.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    For each vertex, we assign a level as the shortest distance for the vertex N.

    Core part is making function succ(l, State={position, color, time}) -> new_State: this function simulate the state while a token reach one of the vertex whose level is l(we assume the first position of token is a vertex whose level is higher than l). We can memoize this function by (l, color of vertexes whose level is higher than l).

    How many states this function memoized? ... actually I don't have any proof(so, my solution is unproved, sorry). My intuition say that it is exponential, but quite small (even in the worst case).

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      I can make a test which makes it memoize $$$O(n2^{n/2})$$$ states.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    My solution uses simulation with memoization.

    Suppose that we start in some state, and the token is in vertex $$$i$$$. If we know only the state of vertex $$$i_1=i$$$, we can simulate one step (or two, if the first step moves the token to the same vertex). Then, the token lands at vertex $$$i_2\ne i_1$$$. If we know the state of vertices $$$i_1$$$ and $$$i_2$$$, we can simulate more steps until the token lands at vertex $$$i_3\ne i_1,i_2$$$. This way, it is possible to construct the following lazy DP: the state is $$$(i,k,\textrm{state of }i_1\ldots i_k)$$$, and the value is $$$(i_{k+1},\textrm{new state of }i_1\ldots i_k,\textrm{number of steps})$$$.

    The simulation function (run in my solution) takes the following arguments: initial vertex, current state and a set of vertices. It runs the simulation until the current vertex is not in the set. There is also an option to limit the number of steps. It starts with $$$k=1$$$ and $$$i_1=i$$$ to compute $$$i_2$$$, $$$i_3$$$ and so on. To compute DP for some $$$k$$$, it runs the same procedure recursively with starting vertex $$$i_k$$$ and the set $$${i_1,\ldots,i_k}$$$. For $$$k=1$$$, a straightforward simulation is used (this requires at most two steps).

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone help me why the following solution is incorrect for C? I hope my logic was correct.

https://codeforces.me/contest/1266/submission/67161724

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your logic is half correct,your solution does produce disjoint gcd arry or diverse matrix,but it is failing to produce the diverse matrix that minimises the magnitude For eg. dry run your program for 3 3,you will get it.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Two doubts for problem D editorial

  1. how did you conclude this " This means that we can just find balances, and greedily match vertices with positive balance to vertices with negative balance.The total debt is then Σd=∑v|bal(v)|2 , and it is clear that we cannot do better than that"

  2. how do we find the final debts i.e. the second half of the answers , the remaining edges.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Since the bal of all the vertices can either be positive or negative (positive for incoming edge and negative for outgoing edge), and you have to match the positive vertices with negative vertices (as the person who is in debt has to pay it to someone and it doesn't matter who pays to whom, all that matters is what one person owes has to be fulfilled by 1 or more than 1 vertices), when you take the sum of all the absolute values of the balances, you are left with 2 times the total debt, because of the fact that you are taking the sum of absolute values. It won't be wrong to say that the total sum of all the balances, after matching all the positives with negative will be zero, because, in the end, all the people in debt have to repay it. Hence, the claim in the editorial is rightfully the minimum.
    2. You take each positive balance, take the absolute value of one negative vertex, take the minimum of the positive and abs(negative), add the index of negative, the index of positive and min value to your final result, and keep on greedily matching positive and negative vertices.
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is it like to minimize the debt we have to pay all the loan back so that the overall debt decreases and that is why we are matching the positive ones with negative ones so as to make positive ones as small as possible. Do we have to think like this ??

      → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In E if we consider a = {1,1} and queries are — (1, 1, 2) and (2, 1, 1) then p will be {0,0} how is it possible to not create anything?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Hey, I was also stuck on this. However, the question states that ti < ai.

    → Reply
»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

In problem H,why are these two conditions sufficient?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 5   Vote: I like it +8 Vote: I do not like it

    For a valid state, we take the subgraph of all active arcs.

    It's easy to see that there exists exactly one vertex such that:

    • The active arc starting from it ends at v.

    • The path from 1 to the said vertex does not include v.

    Then the only possible predecessor of v is the said vertex.

    The rest is induction.

    upd:

    I seem to have missed the case when v=1...

    Forget what I've said before.

    take the directed multigraph, where each arc appears exactly the number of times it is traversed.

    Given the constraints of the matrix, it's easy to see that there exists an Euler path(if it's connected, hence the condition we're checking).

    Consider constructing an Euler path the following way:

    Start from 1;

    If the vertex we're at has been traversed odd number of times, take the blue arc; else take the red arc.

    It could be checked that this Euler path is the legitimate path.

    P.S.

    Since all other vertices must be traversed before v, it could be checked that they should all be able to go to v using only active arcs.

    → Reply
»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it 
#include <bits/stdc++.h>
#define ll long long
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
using namespace std;//coded by abhijay mitra
#define watch(x) cout << (#x) << " is " << (x) << endl
int main()
{
    ibs;cti;
    int t;cin>>t;
    while(t--){
        ll x; cin>>x;
        if (x>15) {x%=14;x+=14;}
        if(x>14 and x<21) cout<<"YES\n";else cout<<"NO\n";
    }
    return 0;   
}

B solution

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is a Detail explanation for Div2 D Here. Hope could be helpful to someone

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is the worst and the most unrigorous explanation I have ever seen.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well Sorry for that.I will try to improve

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the editorial of problem G, "the answer is $$$|p|⋅(|p|+1)−∑LCP[i]$$$", shouldn't it be $$$|p|⋅(|p|+1)/2−∑LCP[i]$$$ ?

→ Reply