prof.PVH's blog

By prof.PVH, 3 weeks 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
 
 
 
 
  • Vote: I like it
  • +144
  • Vote: I do not like it

»
3 weeks 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).

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

Why my submissions are skipped? :/

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

orz

»
3 weeks 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.

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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

  • »
    »
    10 days 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

»
3 weeks 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?

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

    It was fixed, thank you!

  • »
    »
    2 weeks 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.

    • »
      »
      »
      6 days 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.

      • »
        »
        »
        »
        6 days 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$$$.

»
3 weeks 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

  • »
    »
    3 weeks 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.

»
3 weeks 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

»
3 weeks 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)

»
3 weeks 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

»
3 weeks 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.

»
3 weeks 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.

»
3 weeks 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 !

  • »
    »
    3 weeks 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})$$$

»
3 weeks 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.

»
3 weeks 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.

  • »
    »
    3 weeks 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...

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

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

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

      okay, got it, thanks!

    • »
      »
      »
      3 weeks 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) ?

  • »
    »
    3 weeks 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)

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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

»
3 weeks 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

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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 .

»
2 weeks 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?

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks 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.

»
13 days 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.

»
10 days 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...

»
6 days ago, # |
  Vote: I like it +10 Vote: I do not like it

Problem E2 is very nice ! Thank you!

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

Div2 Task E2 is awesome.