robinyu's blog

By robinyu, 3 days ago, In English,
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  
  • +218
  • Vote: I do not like it  

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

In div1 B, preprocessing all relevant factorials and also their modular multiplicative inverses modulo 109 + 7 can be in O(n) even if we don't consider the a constant :)

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

    How can we calculate modular multiplicative inverses of factorials in O(n) for inverse we will need logN

    Like this? first calculate ifact[MAXN] , then ifact[x-1]=ifact[x]*x ?

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

      oops, sorry I can't read.

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

      Yes, this is an efficient method in , and I prefer it to the following O(n) method: rev[i] = -(MOD / i) * rev[MOD % i] (where MOD  = 109 + 7), and then ifact[i] = ifact[i - 1] * rev[i].

      Anyway, is very close to O(n) and much smaller than .

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

In "Karen and Test": We will repeatedly perform the operation until the number of elements n is even, and the first operation is addition, ... this will happen somewhere within the first 4 rows.

Even better, it will happen within the first 2 rows. If n is even, it has already happened. If n is odd, we only need to do one iteration. The second line will have an even number of elements, and the first operation will always be "+". That's because the first line has (n-1) operations, which is an even number, so the first operation in the second line is guaranteed to be "+".

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

Really awesome editorials along with pictorial representations <3

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

Div 2 B with binary search Complexity O(nlogn + n + q)

Code

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

Div.2 B was really nice, there is more than a dozen of approaches to solve this task :D

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

In div1 E, I used binary search. Fix k and divide the segments to three sets(left, right, middle). The remaining part is easy. Time complexity is O(log^2 n).

http://codeforces.com/contest/815/submission/27895623

  • »
    »
    8 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. Your solution is much easier to understand and implement for me compared to other solutions of Div.1 E .

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

Nice contest and editorial, too. However, the following makes me a bit sad:

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

    Actually, there is no upcoming contest in AtCoder too. It's so sad...

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

      There is a contest in csacademy, and hackerrank. I believe that there are a lot of other contests in other websites.

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

    I do not know if it is a notorious coincidence :P When I have my holidays,CF rounds are so rare but during my semester exam time ,They are quite frequent :(

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

Can inclusion exclusion be used for Karen and cards?

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

I used event sorting for my DIV2 B solution but i think i like the solution of the problem setter. Simple and interesting.

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

Please hide this anime bullshit. Codeforces is not an anime site. I don't want to see these pictures when I read an editorial.

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

    Please hide this hate bullshit. Codeforces is not a hate site. I don't want to see these comments when I read an editorial.

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

    Understandable. The editorial is already quite long, and adding the pictures just makes it a bit longer and less readable. They should be removed in a while.

    Have a great day!

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

Nice explanations! I liked the reduction presented in 2D's editorial.

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

In Div2D/Div1B[editorial] what does the K represent?

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

I can't understand how and why exactly greedy solution works in div2 C.

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

For Div1B, I'm very curious why we can always reduce it to the "addition" version of the problem. In contest I failed to find a proof for it, and the editorial only mentions some pattern finding, which is way far from proving it. Is there any Div1B level proof for it?

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

    I'm not quite sure what you mean by reducing it to "addition" version of the problem. If you start with addition then after applying the operation four times, you'll do n - 1 + n - 2 + n - 3 + n - 4 = 2(2n - 5) additions/subtractions in total, so if you start with addition, after four rows the first operation will also be addition.

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

      Well sadly, I also can't understand what you are saying, too..

      Whatever, Let me rephrase what I meant. Author claims :

      • The problem with only plus operation is easily solvable with fast algos.

      • After 4k-th iteration, The problem with only minus operation actually become an instance of "The problem with only plus operation", with input as odd / even array element. So we can perform 4[n/4] operation very fast.

      I agree on first paragraph, and pattern shows second is true, but I'm not sure why.

      UPD : Ok now I got it. I didn't read the part that we always reduce it to + / even n case. Now we can prove it. I'm sorry, and thank you for the help!

      • »
        »
        »
        »
        3 days ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        What I was trying to say is the pattern always repeats itself every four rows so the pattern will continue.

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

Yeah! After a long time waiting

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

In div 1 C. How does the sum converge to O(n)?

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

    It's not exactly the same. However, both are similar to problem I proposed at Croatian Olympiad in Informatics 2 years ago (http://hsin.hr/2015/olympiad/tasks.pdf; OGLEDALA).

    Also, the story of GCJ one is similar, but it's understandeable, as the inspiration obviously comes from real life — urinals. I don't remember why we changed it to washbasins in my problem, though.

    • »
      »
      »
      3 days ago, # ^ |
      Rev. 2   Vote: I like it +20 Vote: I do not like it

      Ha, speaking of urinals: http://www.spoj.com/problems/URI/

      And if I'm not mistaken, this is actually exactly the same as Div1E. (I'm problemsetter for the SPOJ problem). Too bad I did not participate in the round :D

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

In div1 C, the naive dp actually works in N^2 if you don't take j and k all the way up to n every time but only the amount which is actually possible in those subtrees.

  • »
    »
    2 days ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Will you please explain how it runs in O(n^2) .

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Initially you have the size of 1. When you get a subtree of size S you'll make a S * size transition and then you'll make size += S. On the first step, you'll pair the current vertex with all the vertices from the subtree. From the second step onwards, you'll pair the current vertex AND the already counted vertices with the vertices of the next subtree (the number of such pair is S * size). This means that you'll never count any pair twice and the complexity will be exactly the number of such pairs, or O(n^2)

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

      To be pricise,you can calculate the complexity is this way: just a sketch:

       int now=1;
      	  	for (k=0;k<v[i].size();k++)
      	  	{
      	  	  int t=v[i][k];
      	  	  for (j=now;j>=0;j--)
      		  for (int l=s[t];l>=1;l--)
      		    {
      		    	f[1][i][j+l]=min(f[1][i][j+l],f[1][i][j]+f[1][t][l]);
      				f[0][i][j+l]=min(f[0][i][j+l],f[0][i][j]+min(f[0][t][l],f[1][t][l]));
      			}
      		  now+=s[t];
      		}
      

      s[1]*1+s[2]*(1+s[1])+s[3]*(1+s[1]+s[2])+...=sigma(s[i]*s[j])=[(sigma(s[i]))^2-sigma(s[i]^2)]/2

      adding each iteration together,you will find all terms except n^2 will cancel each other So in total,complexity=O(n^2)

      • »
        »
        »
        »
        29 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Here, you have calculated the time complexity of finding f values for a single node and it turns out to be O(n^2). It may still become O(n^3) when you sum it over all the nodes.

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

          No.

          As I explained above, for each iteration(say node v), the complexity is O((number of sons of v+1)^2-sigma(size of each subtree of v)^2) =O((size of tree rooted at v)^2-sigma(size of tree rooted at a son of v)^2)

          When adding these complexity together, we get O(n^2),where n is the size of tree rooted at 1, as all other terms will cancel each other. (according to the problem statement ,each node has only one father;and of course each node is the root of a unique subree)

          • »
            »
            »
            »
            »
            »
            16 hours ago, # ^ |
            Rev. 3   Vote: I like it -13 Vote: I do not like it

            How come my this solution is not passing then, which is IMO exactly as per the algorithm which you have shown to be O(N^2). It's TLE(ing) on 27th test case.

      • »
        »
        »
        »
        28 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks a lot .

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

In 815B/816D the pattern found for the n mod 4 = 2 on the fourth constant should it be (((n-2)/2) 1)?

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

Please add link to editorial to "Contest Materials" section for the tasks. Thank you in advance!

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

I have some complaints.

B: 'Well, we can do something and find magic formulas but wait, we can do something different with triangles and find other magic formulas, now it is much more beautiful!' I will leave aside question about why give this problem to the round. But how can 'watch closely' be an editorial?

C: 'Rather straightforward O(n3) DP' is actually O(n2).

D: Sorry, I stop reading after words 'segment tree'. 27860187 — easy O(n + p + q + r) solution without any data structures.

E: WTF is this?! 'Now, draw the trees with root segments 40, 41, 42, ..., 47' Really? You expect me to draw all these trees to find some really strange pattern which you don't even bother to prove? Who needs proofs anyway. If you don't have any other solutions then 1. How you prove for yourself that all these patterns lead to a correct solution? 2. Why to give this problem on round? You really expect that someone will make all these great observations during two hours?
And yes, there are much simpler solutions 27862681. And (look in comments) there were problems similar to given and even this exact problem.

To sum it up: we have three problems (out of five) for which there exists a solution simpler than it was expected. And expected solution for E looks like it is really unlikely to come up with.

I think that coordinator should have done much more serious work here.

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

    I completely don't get your point in B. I am satisfied by described solution.

    For D I think there are few ways to solve this problem instantly using really standard ideas like some segment trees or I thought about some set of pairs that also does work. You came up with some tricky solution, fine, you're clever, but that doesn't mean that problem is shit. However I didn't really like it anyway because "compute volume of sum of boxes" doesn't sound like an innovative problem.

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

      Reread editorial for B. Phrases that are closest to formal proof are 'Observe the following picture' and 'Am I the only one whose mind is on the verge of exploding?'. We observe and notice, we don't prove.

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

        Did you notice the picture with yellow and blue numbers :|? Isn't that sufficient for you as a proof? Would you feel better if instead of that there will be some hard to follow formulas that will prove what is obvious from that picture? Observing, noticing and proving for statement of such type are typically the same thing. By no means I want to say that noticing pattern is always sufficient for a proof but here once we note pattern from picture then converting it to formal proof is a task for 10years old child, I thought you are capable of such feat.

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

          I get your point. You can deduce the proof from that picture so you think that everybode can.

          Yes, triangle on the picture is quite convincing and I can make from it a proof. But that's not what author says. He says 'It is beautiful that is why it's true'.

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

      Maybe you are right about D. Maybe I just tried to find more examples of strange things in this round and went too far.

  • »
    »
    2 days ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Can you explain your O(n + p + q + r) solution for problem D?

    • »
      »
      »
      2 days ago, # ^ |
        Vote: I like it +64 Vote: I do not like it

      We will see card (x, y, z) as cube with coordinates (x, y, z). All our cards form a cuboid with sides p, q and r. Let's count the number of such cards (x, y, z) that there exists a card in our set such that (x, y, z) cannot beat it. For given card (X, Y, Z) from our set all such cards forms union of three cuboids: (y ≤ Y, z ≤ Z), (z ≤ Z, x ≤ X) and (x ≤ X, y ≤ Y). So our task is to find the volume of the union of this figures for all cards from our set.

      First cuboid has 'free' x coordinate, second -- 'free' y coordinate and third -- 'free' z coordinate. Let's regroup this 3n cuboids in three groups by free coordinate. How the union of all cuboids in one group looks like? Let's look at group with free z coordinate, for example. z coordinate remains free, and union of rectangles froms ladder-like structure. For every x0 coordinate there is y(x0) such that cube with coordinates (x0, y, z) is in our figure iff y ≤ y(x0), and y(x0) is non-increasing function. There also exists non-increasing function x(y0) with similar meaning. We can build all the functions y(x), x(y), z(x), x(z), z(y) and y(z) in linear time with suffix maximums. That's arrays AB, BA etc. in my code.

      Now we want to find the volume of the union of this ladders with one free coordinate. Let's use inclusion-exclusion principle. Now we want to calculate volumes of ladders, pairwise intersections of ladders and intersection of all ladders together.

      Volume of one ladder is easy to calculate: it is area of planar ladder multiplied by the legnth of free coordinate. The area of ladder is just sum of y(x) for all x.

      Volume of intersection of two ladders is not harder. Let's assume that these two ladders have y and z free coordinates. Let's iterate over x. Then first ladder gives us the range of z and the second gives range of y. Each cross-section with fixed x is a rectangle with sides z(x) and y(x). Sum of z(xy(x) over all x is the volume.

      And the volume of intersection of all three ladders is the hardest part. Again, let's iterate over x. That gives us rectangle z(x) × y(x), but there is also a ladder y - z. We should intersect the ladder with the rectangle to get the cross-section for given x. There is two cases: rectangle inside the ladder and reactangle has part outside the ladder. In the latter rectangle z(y(x)) × y(x) lies inside the ladder and we should add sum of y(z) for all z(y(x)) < z ≤ z(x) to its area. To get this sum in O(1) we can use prefix sums.

      Please refer to my code for further explanations. There are three clear parts each doing what is written here.

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

Does anyone have a rigorous proof of Div2 D/Div1 B?

I am simply unable to understand why the last two terms come out as the answers to the "simpler" versions a1,a3,a5,... and a2,a4,a6,...

  • »
    »
    2 days ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Claim: So long as the number of terms is even, in 2 lines, the each term will be dependent only on the similarly colored term.

    Proof: Basically what is shown, because arbitrary numbers are being used the result will not depend on input. The addition pattern is going to be the same since the number of terms is even.

    This proof shows that after 2 lines it will still be true. We can again use it to show that after 4 lines it will still be true. And so on to the last line.

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

"woosh"? Does this word exist? XD

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

    It surely exists, and it's pretty rad.

    https://xkcd.com/1627/

  • »
    »
    2 days ago, # ^ |
      Vote: I like it +54 Vote: I do not like it

    Humans :
    How to solve div 2/1 A B C D E ?
    How to prove div 2/1 A B C D E ?
    I know simpler solution than editorial.

    round winner:
    Is 'woosh' a real word?
    Yo mama is a presentation error.

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

In f(i, j) = min(f(i, j), f(i, j - k) + f(i, k)), how are we making sure that we don't repeat elements?

»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Waiting for another contest !!

»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

 What does it mean?

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

    You might know it as C(n - 1, k - 1). It's number of ways to choose k - 1 elements from n - 1 elements.

»
44 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

can someone explain why can we skip the largest subtree, i didn't got that point. thanks in advance

»
43 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me why the contribution of the K-th element when there are n elements is precisely

»
33 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the editorial for problem div2 E karen and supermarket, its not striking after reading the editorial. please help

»
19 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

"First, simplify the problem so that only addition ever happens. In fact, this version is much easier: the contribution of the element when there are n elements is precisely (n-1) (k-1)."

Can anyone explain this line in Div1 B editorial?

»
9 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

A great editorial and thank u sooo much for such detailed approaches...A newbie like me will learn a lot.

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

For Div 2 Problem E/Div 1 Problem C:

Note that we can't do this at the start, because otherwise it could cause conflicts.

What conflict could it possibly cause? I can't seem to think of any in this case.