I_love_tigersugar's blog

By I_love_tigersugar, 5 years ago, In English

1255A - Changing Volume

Author: UncleGrandpa. Prepared by UncleGrandpa

Tutorial

1255B - Fridge Lockers

Author: I_love_tigersugar ft. MikeMirzayanov. Prepared by UncleGrandpa

Tutorial

1255C - League of Leesins

Author: MikeMirzayanov. Prepared by UncleGrandpa

Tutorial

1254A - Feeding Chicken

Author: I_love_tigersugar. Prepared by I_love_tigersugar

Tutorial
Source code

1254B1 - Send Boxes to Alice (Easy Version)

Author: MofK. Prepared by UncleGrandpa

Tutorial
Source code

1254B2 - Send Boxes to Alice (Hard Version)

Author: MofK. Prepared by MofK and UncleGrandpa

Tutorial
Source code

1254C - Point Ordering

Author: ngkan. Prepared by ngkan

Tutorial
Source code

1254D - Tree Queries

Author: I_love_tigersugar Prepared by I_love_tigersugar

Tutorial
Source code

1254E - Send Tree to Charlie

Author: MofK Prepared by: MofK

Tutorial
Source code
  • Vote: I like it
  • +144
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Why my submissions are skipped? :/

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

    Same code was submitted by other handle.

»
5 years ago, # |
  Vote: I like it -27 Vote: I do not like it

orz

»
5 years 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.

  • »
    »
    5 years 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.

  • »
    »
    5 years 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://mirror.codeforces.com/contest/1254/submission/65470890

  • »
    »
    5 years 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

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I_love_tigersugar

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?

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

    It was fixed, thank you!

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years 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$$$.

        • »
          »
          »
          »
          »
          5 years 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?

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

          How can we prove that median will give optimal answer

»
5 years 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

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

    Sorry for the word choice. I have rewritten the tutorial for easier reading.

»
5 years 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

»
5 years 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://mirror.codeforces.com/blog/entry/71534?#comment-559222)

»
5 years 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

»
5 years 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.

»
5 years 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 years 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.

»
5 years 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 !

  • »
    »
    5 years 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})$$$

»
5 years 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.

»
5 years 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.

  • »
    »
    5 years 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...

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

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

  • »
    »
    5 years 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)

    • »
      »
      »
      5 years 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.

      • »
        »
        »
        »
        5 years 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

»
5 years 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

  • »
    »
    5 years 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.

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

      snacache

      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 .

»
5 years 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?

  • »
    »
    5 years 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.

»
5 years 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.

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

Problem E2 is very nice ! Thank you!

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

Div2 Task E2 is awesome.

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

fridge locker is completely a case of circular rotation

»
5 years 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 years 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.

»
5 years 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 years 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 years 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 years 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 years 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 years 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.

          • »
            »
            »
            »
            »
            »
            4 years 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?

»
4 years 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 years 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 years 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 years 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 years 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. towrist

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

      Have you understood it.. If yes , kindly explain it to me also.

»
4 years 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

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

If someone is trying to solve Div1-D by decomposing queries into square root blocks, but getting TLE because of the constant factor introduced by LCA for finding last node on path from $$$u$$$ to $$$v$$$ (given $$$v$$$ is ancestor of $$$u$$$). You can just manually check all adjacent nodes of $$$v$$$ to find the suitable one whenever $$$v$$$ has $$$\leq 5$$$ neighbours, and do normal binary lifting otherwise. Pretests might be slightly weak as this condition significantly reduces runtime.