I_love_tigersugar's blog

By I_love_tigersugar, 11 months ago, In English

1255A - Changing Volume

Author: UncleGrandpa925. Prepared by UncleGrandpa925

Tutorial

1255B - Fridge Lockers

Author: prof.PVH ft. MikeMirzayanov. Prepared by UncleGrandpa925

Tutorial

1255C - League of Leesins

Author: MikeMirzayanov. Prepared by UncleGrandpa925

Tutorial

1254A - Feeding Chicken

Author: Prof.PVH. Prepared by Prof.PVH

Tutorial
Source code

1254B1 - Send Boxes to Alice (Easy Version)

Author: MofK. Prepared by UncleGrandpa925

Tutorial
Source code

1254B2 - Send Boxes to Alice (Hard Version)

Author: MofK. Prepared by MofK and UncleGrandpa925

Tutorial
Source code

1254C - Point Ordering

Author: ngk. Prepared by ngk

Tutorial
Source code

1254D - Tree Queries

Author: prof.PVH Prepared by prof.PVH

Tutorial
Source code

1254E - Send Tree to Charlie

Author: MofK Prepared by: MofK

Tutorial
Source code
Tutorial of Math and Games
 
 
 
 
  • Vote: I like it
  • +144
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by prof.PVH (previous revision, new revision, compare).

»
11 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Why my submissions are skipped? :/

»
11 months ago, # |
  Vote: I like it -27 Vote: I do not like it

orz

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

For Problem D I just sorted the adjacency list by size of the subtree (then flatten it with euler tour). That way even if nodes are heavy I can update all the subtrees in $$$sqrt(N)log(N)$$$ since it will have at most $$$sqrt(N)$$$ different value in sizes and I can update several subtrees of the same size in one single range update (because they are in one complete range in the euler tour) and you want to add the same value $$$\frac{1}{n}d(n-sz)$$$ to all of them.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Hacked. Each update for a subtree size should call only 1 Fenwick Tree update instead of 2. Or you can do this.

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

    I did the same thing and was getting TLE, but then I realized that I can optimize the worst case if I batch update queries for the same node, so if there is 1 node that has sqrt(2*n) different values, worst case will be Q/2 modifies which should reduce the constant by 2 and make it work. It now passes.

    https://codeforces.com/contest/1254/submission/65470890

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

    I use similar idea about different subtree size. But I also divede the queries into sqrt(Q) parts then get a O(NsqrtN) off-line algorithm: We use an array to modify the updates and calculate the presum after each part. Then for each query with type 2, we just need to calculate the updates from the queries with type 1 in the same part. For all Nsqrt(N) such pairs of queries, we sort them by dfs order using bucket sorting. Then we insert the pairs into corresponding vertex's vector, then for each vertex we calculation the values of all the queries corresponding to it one by one with the vector containing its subtrees with different size and their dfs orders, just like a merge sorting.

    Code:65993177

»
11 months ago, # |
  Vote: I like it +9 Vote: I do not like it

prof.PVH

For editorial of Div2E2/Div1B2, shouldn't it be min(Si%k, k - Si%k) instead min(Si%k, (k-Si)%k)?

And btw, anyone has the link for the markups used for blogs/comments on CodeForces?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    It was fixed, thank you!

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

    does the idea of grouping k chocolates into their coordinates meridian work? I did it on contest, but got wa on pretests of E1 (but not on pretests of E2) and not sure if it is a bug or wrong solution.

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

      I think it will work, but then the hard part here is you don't know the number of candies in each part to determine the median.

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

        I did it in the contest (65365892). Basically, you just divide all candies into groups of $$$K$$$ and move each group into its median box. Just need to be careful because the number of candies at a time can exceed $$$K$$$.

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

          So E1 editorial solution can be done for E2 also with some modifications (or a lot of modifications :D). Am I right?

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

          How can we prove that median will give optimal answer

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Notice that we can map the given rectangle to an array. In other words, there exists a path in the rectangle that goes through every cell exactly once. can someone explain this part

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

I don't understand why the round was rated for me. On what basis did you decide that the mistake in problem B did not affect me ? This mistake completely ruined my contest. I wasted 100 min in B. And when I up-solved C and D I could solve them quickly. this could have been a very good contest for me but now I lost 50 points. and yet you refuse to make round unrated

»
11 months ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

How I did D:

Call a vertex heavy if it has more than $$$T$$$ neighbours.

For updates at $$$u$$$, first update the complement of the subtree rooted at $$$u$$$. Then, if $$$u$$$ is heavy, just keep track of the update at $$$u$$$. Otherwise, update the subtrees rooted at the children of $$$u$$$. This is $$$O(T\log(N))$$$.

For queries at $$$u$$$, first query the value at $$$u$$$. Then, jump upwards to the next heavy vertex until we reach the root, and update the answer with the values at these heavy vertices. This is $$$O(\log(N)+N/T)$$$.

Setting $$$T=\sqrt{N/\log(N)}\approx93$$$ gives $$$O\left(Q\sqrt{N\log(N)}\right)$$$ total. Runs in under half a second on system tests but I found an input that makes it run in 2.6 seconds.

(seems like a less intelligent version of this $$$O(N\log(N))$$$ solution: https://codeforces.com/blog/entry/71534?#comment-559222)

»
11 months ago, # |
  Vote: I like it +122 Vote: I do not like it

An alternative solution for D. Tree Queries.

It's obvious that for each "modify" operation we can spend $$$O(degree_x \log n)$$$ time naively updating the answer using BIT in the tree-dfs order. And now we can get some improvements. For each node we initially choose one of its sons of the largest size. For a "modify" we only update its father's "subtree" and the heaviest son's subtree. And for each query, we not only calculate the answer in the BIT, but also jump up to the query node's ancestors that haven't updated the query node yet and calculate the extra answer.

It can be shown that there are at most $$$O(\log n)$$$ such ancestors to deal with. So the total complexity is $$$O((n+q) \log n)$$$, with quite a small constant.

Code: 65403262

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

My solution to Tree Queries:

  1. For a set of updates, we can easily calculate their contributions to each node in $$$O(n)$$$ time -- for each node $$$u$$$ we get the sum of $$$d$$$ of all operations that $$$v=u$$$, then iterate all neighbours of $$$u$$$. Since we do not need to support online query, the updates can be done with difference in linear complexity.

  2. Also it's easy to tell an update's contribution to a specific node $$$u$$$: we just need to get the size of the subtree of $$$u$$$ when we root at $$$v$$$. This can be done in $$$O(n\log n) - O(1)$$$ complexity.

We calculate the contribution to each node every $$$\sqrt n$$$ operations, and when query on a node we consider the latest $$$\sqrt n$$$ updates' contribution to it. This works in $$$O(n\log n+n\sqrt n)$$$ time.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain in Div2E2, how can we assume that if we are taking k-S[i]%k from i+1 th element then it will not become negative ( does it have enough candy to give). The author has said something related to this doubt as 'S[i]>S[i+1]'. Can someone give an intuitive proof of th this. Thanks in advance.

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

    lucifer_1502 Did you get it? If yes, then can you please explain? I've spent 4hrs on this problem, but couldn't come to a conclusion.

»
11 months ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

In div2 E1 or (div1 B1) how to prove that maximum number of divisors of a number less than 10^5 is 240 (It is given in editorial but no proof has been provided) .Thanks !

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Hi. To prove that, you can either factorise all intergers from $$$1$$$ to $$$10^5$$$ to count the number of divisors it has, or just google search for the list of highly composite numbers. For estimation purposes, the number of divisors a number $$$n$$$ has is about $$$O(n^{1/3})$$$

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

In problem B1, it suffices to iterate through only the prime divisors (taking as k) of the total number of chocolates.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain this for me :"A number ≤10^5 has at most 240 divisors". I tried to create number that can have most divisors but all I found was 128 divisors (120120). Thanks in advance.

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

    So that's why they said "at most" XD... Moreover 120120 is greater than 10^5 XD...

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

    I checked... it's actually 83160 with 128 factors.

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

      okay, got it, thanks!

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

      In div2 E1 or (div1 B1) how to prove that maximum number of divisors of a number less than 10^5 is 240 (It is given in editorial but no proof has been provided) ?

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

    Sorry, it is in 83160 with 128 divisors. I mistook this problem for the original problem(which has a constraint of 1e6)

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

      thanks, but I still wonder how to get maximum number of divisors for number with value that does not exceed some specified boundary.

      • »
        »
        »
        »
        11 months ago, # ^ |
        Rev. 3   Vote: I like it +1 Vote: I do not like it

        Please see my comment above. There also exists a way of backtracking. You just need to backtrack for a sequence of $$$k_1, k_2,...k_n$$$ such that $$$(k_1+1)*(k_2+1)*...*(k_n+1)$$$ is maximum, $$${p_1}^{k_1}*{p_2}^{k_2}*...*{p_n}^{k_n}$$$ $$$\le N$$$ and $$$k_1 \ge k_2 \ge k_3 ... \ge k_n$$$ But on practical I think referring to the highly-composite number list is a more convenient way

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

@prof.PVH

pls explain this..

STATEMENT : "Now it is clear that we will divide the array into segments, such that sum of each segment is divisible by K, and move all the chocolates pieces in that segment into one common box."

lets say my input array is : [ 6 7 9 7 6 7 7 ]

now the sum of the array is 49 ...

and optimal divisor(k) for this array would be 7 ...

Why do I need to move all the candies into common box ?

we can see that we need to pass one candy from index '2' to index '0' and one candy from index '2' to index '4'... and that would 4 seconds...

and we are not moving all the candies to any common box..

so can please explain that statement

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

    That statement is about the easy version, where each element is 0 or 1.

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

      sam721

      I realised that I after posting the comment :p ... my bad, I opened both questions, and I thougth I was reading E1, but I was actually reading the E2 :p .

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I still don't understand tutorial for feeding chicken? Does anyone have better explanation?

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

    You can solve the 1xn problem assigning equal or almost equal quantities of rice fields to each chicken, for example, if there are 32 rice fields and 6 chickens, you go 6, 6, 5, 5, 5, 5, giving the non-rice fields in between the rice fields to the corresponding chicken.

    Now "cut" and "stretch" the original rectangle into one long strip or array of 1x(r*c). You can do that in several ways, like zig-zag, spiral, etc, and solve like above.

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

      I guess the hardest trick for me was to understand that it doesn't matter how many fields belong to one chicken. It is all about rice per chicken.

      Zig Zag was another trick.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There is a way that cost $$$O((n+q)\log n)$$$ for problem D.Here it is.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please help me in solving problem B1 SEND BOXES TO ALICE(EASY VERSION). it's giving me wrong ans in test case 7...

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Problem E2 is very nice ! Thank you!

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Div2 Task E2 is awesome.

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

fridge locker is completely a case of circular rotation

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

In problem E2, is there a proof (or at least help me understand) for this fortunately true statement : " The only concern is that: is there any scenario when there exists some i such that $$$S_i > S_{i+1}$$$, which is indeed a violation? Fortunately, the answer is no. ".? Thanks <3.

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

    _LNHTD_ Did you get it? If yes, then can you please explain? I've spent 4hrs on this problem, but couldn't come to a conclusion.

»
6 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Div2. E2/ Div1. B2:

"But if you have solved the problem to this phase already, you can easily realize that we only need to consider prime k, because if k is composite then picking any prime divisors of it will lead to either a better result or an equal result."

Why and how?

UPD: Understood. If all $$$a_i$$$ are to be made divisible by some composite say p*q (p and q are primes), then they are also made to be divisible by p and q, at (in the worst case) the same cost. So it is sufficient to only consider the primes (as they guarantee an equal, if not better, answer).

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

    Can you please explain in Div2E2, how can we assume that if we are taking k-S[i]%k from i+1 th element then it will not become negative ( does it have enough candy to give). The author has said something related to this doubt as 'S[i]>S[i+1]'. Can you give an intuitive proof of this? Thanks in advance.I've already spent hours but couldn't get to any conclusion. the_hyp0cr1t3

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

      If $$$S_i \% k \le (k - S_i \% k)$$$, then it is optimal to move $$$S_i \% k$$$ chocolates from $$$S_i$$$ to $$$S_{i+1}$$$.

      Otherwise $$$(k - S_i \% k) < S_i \% k$$$. It is optimal to move $$$(k - S_i \% k)$$$ chocolates from $$$S_{i+1}$$$ to $$$S_i$$$. We know that $$$S_{i+1} \geq S_i$$$, so there are at least $$$S_i \% k$$$ chocolates in $$$S_{i+1}$$$. And $$$(k - S_i \% k) < S_i \% k$$$. So there are always enough.

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

        the_hyp0cr1t3 I tried to prove it this way, I do not understand where am I getting wrong

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

        How does Si+1>=Si implies that there are at least Si%k chocolates in Si+1?

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

          $$$S_i$$$ has at least $$$S_i \% k$$$ chocolates, so $$$S_{i+1}$$$ also has at least that many.

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

            Si+1 is greater than Si%k but how can we prove that it is greater than Si+k-Si%k because will be taking chocolates out of ai+1 i.e. si+1-si?

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

In Div1 B1 why moving all the ones to $$$temp[(i+i+p-1)/2]$$$ is optimal than to moving ones to $$$(temp[i]+temp[i+p-1])/2$$$ ??

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

Hi, MofK, question regarding following statements:

The only concern is that: is there any scenario when there exists some i such that Si>Si+1, which is indeed a violation?

Since S[i]=sum(a[0]..a[i]), thus S[i+1]-S[i]=a[i+1]. If S[i]>S[i+1], then a[i+1]=S[i+1]-S[i]<0. To my understanding, all a[i], either before or after any operation, should be positive. If I were correct, then there should be no case that S[i]>S[i+1].

Anything I am missing here?

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

    happy15 But how do we make sure that ai+1 will remain positive after the most optimum choice of operation for that case when Si%k>k/2

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

We can enforce the solution to iterate each Si from 1 to n−1 and always choose to decrease if there is a tie

In fact, even if we choose to increase for every tie, we can enforce a non-decreasing sequence. We just have to fix and follow it.

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

    Can you please explain in Div2E2, how can we assume that if we are taking k-S[i]%k from i+1 th element then it will not become negative ( does it have enough candy to give). The author has said something related to this doubt as 'S[i]>S[i+1]'. Can you give an intuitive proof of this? I've already spent hours but couldn't get to any conclusion. Thanks in advance. mshiladityam

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

I am getting WA on test case 7 for the problem 1254B1 - Send Boxes to Alice (Easy Version), the code seems to be logically correct to me, where am I getting wrong?: 86285300

UPD: Fixed