_kun_'s blog

By _kun_, history, 2 weeks ago, In English,

Div2A ("Palindrome Dance") was authored by jury members altogether, development: darnley

Div2B ("Skewers") was authored by jury members altogether, development: GlebsHP, Codeforces hardened version: KAN.

Div1A ("Timetable") was authored by Zlobober and _meshanya_, development: kraskevich.

Div1B ("Subway Pursuit") was authored by V--o_o--V, development: alkurmtl

Div1C ("Network Safety") was authored by V--o_o--V, development: achulkov2.

Div1D ("You Are Given a Tree") was authored by GlebsHP, development and codeforces edition _kun_, faster model solution: V--o_o--V.

Div1E ("Summer Oenothera Exhibition") was authored by Zlobober, development by malcolm.

Some editorials are being published, please wait a bit :)

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  
  • +16
  • Vote: I do not like it  

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

I get a Wrong Answer on 1039B. I submit the same code again. I get AC ???

how bad luck...

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

what if n is even and middle two are R min of the cost is considered for replacing both R but should'nt cost be 2 * mins

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

It's a hard contest :(

»
2 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

This round made me decide not to used rand() again :(

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

May I ask whether an O(n log^3(n)) solution of Div. 1 D will get Accepted? (DP + Union by size, O(n/k * log^3(n/k)) for each k)

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

What is the proof that We will always be able to get answer in 4500 steps.. I was stuck there for 1:30 hours, I was able to get solution described in editorial.

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

    The initial binary search will take at most 100 steps.

    Let's say you perform binary search until the interval is  ≤ 50, and then guess random numbers. After a guess, the interval is at most 70, so after two binary search iterations you are again at a interval  ≤ 50.

    Therefore you will have around guesses, each one in a interval  ≤ 50.

    The probability of guessing at least once correct is

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

      Then can you please explain me, why this solution is not passing testcases if probablity is this much high. https://codeforces.com/contest/1040/submission/42542608

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

        In the following piece of code, you ask two queries, but only increase the intervals by k once. Should be a simple else, not else if.

         if (get(in, out, low, mid)) {
             high = Math.min(n, mid + k);
             low = Math.max(0, low - k);
        } else if (get(in, out, mid, high)) {
             low = Math.max(0, mid - k);
             high = Math.min(n, high + k);
        }
        

        Also I recommend setting a bigger interval limit than 4*k, otherwise you need a lot more time for binary searches. E.g. if k = 10, then in the worst case you have an interval of length 60 after asking, then 50 after one BS iteration, 45 after the second, 43 after the third, ... So you might only get to ask  < 500 questions this way.

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

          OK bro. Got that, Trying to remove TLE in 7th testcase by setting a good seed. Thank you!!!

»
2 weeks ago, # |
  Vote: I like it +99 Vote: I do not like it

I like how Div1A is the only problem without an editorial :)

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

    Finished with it, sorry for the delay :)

    Well, most editorials were written by their developers, with two editorials missing. So yesterday I was very sleepy and managed to write only one of it. But now it is done!.

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

In Div1D, how exactly do you find the transitions that add new paths from the segment tree efficiently? Knowing the longest incomplete path in a segment doesn't necessarily tell you whether any element of the segment has a longest incomplete path that is now long enough to be a complete path.

I also thought of having each segment hold the minimum extra needed to complete a path, but that can't be updated in O(log n) when merging.

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

    When you process a light child, you can check that the current longest path + a path in the light child is at least k. And then you can check all numbers >= k (you can do it with segment tree on maximum containing length — k, and then find all numbers bigger than zero), and find that path.

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

I know in Div2D were some problems with rand() Could you please explain what type of random function should we use to avoid these problems??

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

    Check the recent posts by neal, like this and this.

    I pretty much agree with everything he suggests.

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

Let me try to explain my solution to Div1A (42525555).

First of all, we have some initial conditions: ai + t ≤ bi.

Now, iterating over x, assume we got xi = k. What can that mean?

First, we need to ensure that i-th bus can't arrive (k+1)th and later. How to do that? The only way I see is to ensure that (k+1)-th bus can't arrive k-th — that is, ak + 1 + t > bk.

But that's not all.

If k < i, the answer is instantly No: we can't guarantee that i-th bus will always arrive in first k places (all i — 1 previous buses can always come before i-th one).

If k > i, we need to ensure that i-th bus can really arrive k-th. To do that, we need to ensure that (i+1)th, ..., k-th buses can all arrive at least one position earlier (that is, (i+1)th one can arrive i-th, ..., k-th one can arrive (k-1)th). Which gives more conditions: ai + 1 + t ≤ bi,  ...,  ak + t ≤ bk - 1.

After collecting all these conditions on bi and taking into account that bi < bi + 1, we can generate a solution (or answer No if for some bi its lower bound exceeds upper bound). We can just store array with upper and lower bounds on bi and update it carefully.

The only algorithmical problem here is to update (k-i) boundaries in case k > i quickly enough. To do that, I created an ordered set of i-s for which condition of form ai + 1 + t ≤ bi has not been applied yet. When I apply this condition, I remove corresponding index from the set. There can't be more than n removals each worth, so the overall complexity of my solution is .

»
2 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Never seen trick like Div1 E before..

»
2 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Is it the editorial for Div2C/Div1A would be even more confusing, and so skipped?

»
2 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

I have seen a similar idea about div1 D before, in "Petrozavodsk Winter-2015. Moscow SU Tapirs Contest", problem F.

You can Click here

I tried an approach but failed at that time, just because it was too complicated.

And my friend who was taking virtual contest with me simply used this trick, but he failed too :). Maybe N is a little bigger and the time limitation is tighter.

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

can someone explain the last part of Div1C where the number of connected components are calculated in linear time

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

    For each value, take the edges with that value. Use a DSU data structure to connect the two vertices of each edge. The number of connected components starts at N, and goes down by 1 each time you join.

    The problem here is that resetting the DSU takes O(N) each time, which can be too slow. So modify the DSU to keep track of which vertices you modify. Then, instead of resetting all the vertices, only reset the ones that have been modified in the last DSU.

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

In problem E, can we find q without dfs, or dsu? UPD I figured out.

»
2 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

It's hard to cut off O(n2) solutions, when you propose O(n5 / 3). And you almost did it =) http://codeforces.com/contest/1039/submission/42621125. 4.8s out of 7s TL. The key idea — to process simultaneously every 4 queries. That allows us to use vectorization.

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

why is the test case in 1040 B giving wrong answer

30 Time: 0 ms, memory: 0 KB Verdict: WRONG_ANSWER Input

4 2

Participant's output

1 4

Jury's answer

1 3

Checker comment

wrong answer Skewer 1 remains at initial state.

AND why is Jury's answer correct when we take 1 and flip it then both 2,3 with rotate with it and if we rotate 3 later, then both 1,2 will again flip to their natural position ?

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

    The output format is

    1//the number of shifts
    3//indexes
    

    So in your case you take the 4 skewer and the skewers 2, 3, [4] are turned over(but not 1). Jury answer: to take the 3 skewer and the skewers 1, 2, [3], 4 are turned over,

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

Can anyone explain to me the solution for 1040B ? I am not able to conceive any idea related to what the editorial is stating.

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

Div 2 E, Compare to Previous Submission

Changed from C++17 to C++14, TLE becomes AC in less than half the allotted time limit...

I'm hecking bamboozled!

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

Can someone explain why the second example in Div1 A is invalid? I am still confused. I think the first bus can arrive 2nd then the second bus arrives 1st... so why Xi<i means the answer is No?

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

Can someone help to explain why this submission failed? I viewed the Output log and I think I got the correct answer?? https://codeforces.com/contest/1039/submission/42753994

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

pls anyone explain me 1040B shashlik cooking .. and send the code of this problem...