Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

JATC's blog

By JATC, history, 5 weeks ago, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Sorry if the tutorial for F is too long.

 
 
 
 
  • Vote: I like it  
  • +87
  • Vote: I do not like it  

»
5 weeks ago, # |
Rev. 7   Vote: I like it +31 Vote: I do not like it

As for D, there is a simple O(N) solution. First of all, let's forget about a and b less than 0 We can observe that score is increased on each integer as many times, as this integer appears a divisor of some other integer. This happens floor(n / i) — 1 times for number i. Then we can see, that we have a mirror situation with a and b less than 0. And with a < 0, b > 0 and a > 0, b < 0 works the same. That's why answer is sum of i * (floor(n / i) — 1) for i from 2 to n multiplied by 4.
Here is my solution 45732442

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

    Why every "i * (n / i — 1)" can be choosed?

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

      eg: 6->2, -6->2, 6->-2, -6->-2 in all the above case 3 is the divisor of the integer 6 so suppose n=18 then 3 appears as divisor for 6,9,12,15,18 so the score becomes 3(|x|:divisor) * 5(floor(n/i)-1) * 4(for a,b +ve 0r -ve cases).

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

    Thanks for suggesting this trick.Learnt something new.

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

A can be done by an O(n) algorithm by just traversing once along the array

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

In problem D.

Could someone elaborate more on the proof that all the nodes are in the same component?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 6   Vote: I like it 0 Vote: I do not like it

    Set of numbers that can transform into a number x is always even (if a can transform to x, -a can either), so the graph built by connections that based on two numbers which is transformable to each other or not will have vertices with even degree, so the graph is Eulerian, which means you can travel through all the vertices without coming back to previous vertices. And so all the vertices must be in a same component.

    I guess.

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

    Suppose you transform a into b and |a| < |b| then x = b / a right? It's clear that a, b and x are in the same component. You can see that |b| ≤ n and |a| ≥ 2 so |b / a| ≤ n / 2, which means you are able to transform x into 2x as well, that makes x, 2 and 2x belong to the same component. So for every node that has at least an edge attached to it, we know that node is in the same component as 2.

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

    how to solve this problem? Can someone provide a simpler version of this problem or can explain this problem? Thanks in advance :)

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

    Cool solution, that uses the same idea as my, but faster

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

    fascinating solution :)

    can you please explain it? especially the line below:

    ans += (cnt * (cnt + 1) / 2 - 1) * (r - l + 1)
    
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      https://codeforces.com/contest/1062/submission/45724128 It's this solution but optimized. The answer is: for each i, for each multiple of i, sum j / i as can be seen from this code. N / i is the number of multiples and you can take that sum in O(1). Now, just group the i's by the value of N / i.

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

Can someone share their code for problem E with same solution as the editorial?

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

    My implementation is almost the same as the editorial.

    One difference is that my range queries return the two smallest and two largest dfs-order labels in [l, r]. We will either delete the smallest and use the LCA of the second smallest and the largest, or we will delete the largest and use the LCA of the smallest and second largest.

    The editorial instead suggests to make additional queries on [l, u) and (u, r] to simulate deletion of node u.

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

    You can find my solution here. It's the same approach as the author's, provided a quick explanation to the thought process commented above the code.

    If you have any questions, please let me know :)

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

      Thank you very much! Your clean code helped me learn and implement lca and solve this problem.

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

        You're welcome! Glad i could help :)

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

Can someone share their code for problem D with same solution as the editorial?

»
5 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

Codefores is the best!!!

»
5 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

Am i the only one who solved D in less than 10 lines?

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

    Me too, and it was a O(n) solution.

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

    I an not able to understand how to solve that problem. Please can you help me with this. I know the theory behind Euler's path and graphs but how to think this problem can be solved using graph? Any help would be appreciated.

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

There is an O(n) complexity algorithm for A. Since we need to check for the longest set of increasing difference-by-1 consecutive elements in the array, we don't need to use all pairs i,j. It can be done by for i in size of array, if a[i]==a[i-1]+1 and a[i]==a[i+1]-1 then we increase the delable_currentsize_var by 1; else (means we find the barrier of the increasing set) we update max_delable_size = max(max_delable_size, delable_current_size) and reset the delable_currentsize_var to 0.

https://codeforces.com/contest/1062/submission/45727163

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

An alternative solution to problem F:

First, find any topological order of the DAG.

Observation 1: A city is important if and only if all the cities before it can reach it and all the cities after it can be reached from it.

Observation 2: In a DAG, vertex v can be reached from any other vertex if and only if v is the only vertex to have no outedges.

From 1 and 2, we can find which cities are important(by adding the vertices in the topological order and maintain a set of the cities with an outdegree equal to zero). This is O((m + n) log n) and with some tricks it can be done in O(m + n).

Now, let's focus on semi-important vertices:

Observation 3: Assume that v is a vertex without outedges in a DAG. Then v can't be reached from exactly 1 city if and only if:

  1. There is only one city without outedges apart from v(let it be u);
  2. There's no vertex with exactly one outedge that points to u.

So through restoring the vertices with exactly one outedge and how many times each vertex is pointed to by these vertices, we can easily deal with semi-important vertices in O(m + n).

Submission: 45770465

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

    Correct me if i'm wrong. The topological ordering is not so important with two node that can't reach each other, right?

    So with test case 3,

    5 4 1 2 3 2 2 4 4 5

    if i change the topo order before we apply solve(tsq, G), particularly node 3 and node 1 ( swap(tsq[3], tsq[4] ) ), your code will give answer 4, instead of 5, which is WA.

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

      Swapping node 3 and node 1 should be swap(tsq[0], tsq[1]).

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

    Nice solution. I have found a similar one, but mine is a little bit more complex.

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

What is the intuition behind C's solution? Someone explain please.

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

    Solve the problem by hand for some cases, and you should realize that each time the numbers keep doubling. If the whole array is ones, then a number at step i will contribute (2^(i — 1)).

    However that doesn't hold for zeros, so you assume everything is ones, then subtract the excess.

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

    it is like when you transfer from binary to decimal and you should take attention that you should take all ones first so if the number is 101001 you can say the number is 111000 * take care that if the number is 111111 the decimal will be 2^6 — 1 and if if the number is 111000 the number is 2^6 — 2^3 so the solution is 2^(all segment) — 2^(number of zero's) hope that is clear for you

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

      Can you help me? What is wrong in this code 45786145 ? I changed all things but even is getting the same result.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it -10 Vote: I do not like it

      ahmed_nabil1297 Why are we multiplying 2^(no_of_ones)-1 and 2^(no_of_zeroes) ?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        when you transform from binary to decimal if the one's are at the left and the zero's are at the right like 111000 you can transform it quickly by make the number equal 1000000 — 111 and 1000000 = 2^(all segment) -> 111 = 2^(no_of_zeroes)

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it -10 Vote: I do not like it

          I got that part. But why are we multiplying these two values?

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

    There is a dynamic programming approach that independs of pots of 2.

    Let n be the number of 1's in the interval. Now you can have two processes: 1) the total deliciousness of the n pieces will be the deliciousness of the n-th piece plus the total deliciousness of n - 1 pieces. 2) the deliciousness of the n-th piece will be the total deliciousness of n - 1 pieces plus 1.

    Let x be the total deliciousness for the n pieces, and m be the number of 0's in the interval. Then the answer for these guys will be x *  total deliciousness of m pieces (since, instead of starting with 1, these guys are starting with x)

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

if anyone solved problem D by editorial approach, please provide the code.

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

is the tutorial for E has a error? it should be out[u]=max(out[v1],out[v2],...),or my understanding of in[] is wrong?

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

    "a child of u" includes all the direct and undirect childs of u. Apparently, inu = max(inv1, inv2, ..., invk) (v is a child of u, both direct and undirect) and inu = max(outv1, outv2, ..., outvk) (v is a DIRECT child of u) are basically the same.

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

In second sentence in E we should have the reverse implication i.e inu ≤ inv ≤ outu implies u is an ancestor of v, instead of u is an ancestor of v implies inu ≤ inv ≤ outu which is written, since this is the direction used later in the proof.

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

    You're right. It should have written as u is an ancestor of v if and only if inu ≤ inv ≤ outu

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

can anyone explain problem B again please ?

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

Can someone explain me why in the 7 pretest of A problem answer is 2 but not 4?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Okay, I just read the task one more time ;D

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

    The statement says "the maximum_ number of consecutive elements" not "the total number of consecutive elements".

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

Can someone explains why the complexity of the final step in tutorial F is O(N+M),please? (......After that we pop those nodes from the stack (or whatever), mark them as not visited and continue to iterate(迭代) to si−1.) (......To calculate in we reverse the directs of the edges and do the same. Because each node is visited 1 time by nodes on (P) and at most 2 times by candidate nodes ) in such a way why some nodes won't be visited more than 1 time?

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

    Assume we have: 1->2->3->4 1->5->3 2->6->4 6-> a set of nodes S1 5-> a set of nodes S2

    Let go backward from 4 to 1. First, at 4, because R_6 points to 4 so we start a search at 6, each node in S1 is iterated one time. After that, we reach 3, because R_5 points to 3 so we also start a search at 5 and each node in S2 is iterated one time. There maybe a chance that nodes in S1 are revisited (there is an arc from 5 to 6). Okay so let's deal with the worst case here: nodes in S1 are visited the second time. Then we reach 2, we start a search that goes from 2 to 5 and to all nodes in S1. So that's the third time we visit nodes in S1. The important thing is, this time we mark all nodes in S1 as visited and we will never visit them again. Therefore, each node is visited at most three times, one time by the nodes lie on the longest path and two times by the candidate nodes.

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

Does anyone wrote the code for Problem D in editorial approach? please comment link.

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

In problem A, I'm getting an error on Test 7.

9 1 4 5 6 7 100 101 102 103

My answer is 4. However, the Jury's Answer is 2. Why is it 2? I can delete 5,6,101,102 for a total of four, right?