300iq's blog

By 300iq, history, 4 weeks ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial of Grakn Forces 2020
 
 
 
 
  • Vote: I like it
  • +129
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

Rip FSTs on B

»
4 weeks ago, # |
  Vote: I like it -150 Vote: I do not like it

So Tourist as you now have 500 Euros, please give me a party!

»
4 weeks ago, # |
  Vote: I like it +45 Vote: I do not like it

Test 9 on problem B... It just destroyed everyone.

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

    well, not everyone...correct solutions have passed.

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

      I didn't mean literally everyone. I meant a lot of people, so I exaggerated. ;)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

      whoosh

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it -53 Vote: I do not like it

    Me too..

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

    Well, it do seems that many people wrote the correct solution, but failed because of some details... At least I do.

    The issue is that nothing shows the special detail on pretests.>_>

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it -19 Vote: I do not like it

    I didn't understand the editorial of problem D. Please someone help me to understand it.

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

      i is for ith robber j is for jth search light. x+y is the solution of our problem . Here in this editorial author is calculating the value of y for diffrent value of x. Let's say a[i] , b[i] is the position of one robber . As x , y is the answer so every robber position will increase by x and y. To escape from c[j] ,d[j] searchlight , either of condition must be true (a[i]+x)>c[j] , (b[i]+y>d[j])

      for x >(c[j]-a[i]) we don't need to calculate y as one condition is already satisfied. for x from 0 to (c[j]-a[i]-1) we need to calculate y and its minimum value will be d[j]-b[i] .

      I hope you can think further .

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

        But we will still need to iterate over all possible values of x for every robber and search light pair, that makes it O(C*m*n) , how to optimise this.

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

          I think this is the part where both you and I got lost on the editorial: So we have n*m queries of max= on prefix. We can do it using suffix maximums.

          It just starts to make sense to me. For any search light and robber pair, let's denote dx = c[j] — a[i] and dy = d[j] — b[i]. if dx >= 0, it means that for all right moves ranging from 0 to dx, we must move robber up by dy + 1. Instead of doing updates on all x in range[0, dx], we just set r[dx]] to max(r[dx], dy + 1), representing this prefix range must have how many up moves associated with them.

          After processing all n * m pairs, we then do a linear scan from right to left,(this is the suffix maximum the editorial mentioned) and update on each possible right move x, the least up moves we must have at that x. This must be done from right to left since r[x] of bigger index has an impact on smaller index, but not vice versa.

          I guess this is kinda similar with the common technique used in counting number frequencies for a given set of intervals [l, r], we would add 1 at index l then subtract 1 at index r + 1, then do a prefix sum computation from left to right.

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

            I too got stuck here, great explanation. Thanks a lot.

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

              you are welcome, us noobs gotta stick together and help each other to get better :)

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

            Thanks , i finally got it . There is one difference in difference array method and the technique used in this question is that you can choose the direction of accumulation in difference array method depending on whether you fixed the leftmost index or rightmost index but in this question we must go from right to left.

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

            Can you please explain why it is r[x] + x not r[x]?

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

              The final answer always consists of 2 types of moves: move right and move up. The index x represents how many right moves we perform, the value at index x r[x] represents the minimum up moves we must perform given we move right by x.

              Then we just loop through all possible right moves, add each associated up moves and get the min sum as the final answer.

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

            Thanks lzhang for very nice explanation. Can u provide any resources for suffix maximum. I don't know what is it and what types of problems can be solved using this.

            Thanks in advance (:

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

              Actually I am the same with you, this is the first time I heard about the term as well. I just spent some time staring at the editorial and other people's code to figure out how it works for this problem. :))

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it
»
4 weeks ago, # |
  Vote: I like it -57 Vote: I do not like it

What the hell with the problem F? why do you assume that we can use 2^(k+1) elements, which is strictly bigger than n in most cases? We only have n elements in the array a.

»
4 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it
»
4 weeks ago, # |
Rev. 4   Vote: I like it -21 Vote: I do not like it

Wrong Answer on test 9

»
4 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

It was a Div 1.5 actually.!

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

A bit different idea for C, so that you can do it similar to solution 2, but avoiding complicated part with the last segment being reached at different moments from different sides... Or maybe just a different way to approach the same idea.

Generate events "one of the cars reaches some flag" and sort them by time. Now you can say that every time the event happens total speed of two cars increases by 1, so you can proceed events one by one while maintaining current distance between the cars. Once you reach the point at which next event results in negative distance, you know that the cars met between previous and this event, and you know that their speed during that time period was constant, so finding the exact answer is easy. Possible implementation in 94309676.

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

    Did exactly this idea..although i was thinking it as a point of change.

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

    used same idea committed a very silly mistake

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

    My implementation was same as your idea, except instead of blindly sorting them, I choose between which of two events is going to happen first: Car1 reaches next flag, or Car2 reaches its next flag first and then update system (speed,next flag,etc). Code

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

what does this bit in problem A mean thou ? pi≠p(i mod n)+1.

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

    Let's say $$$n = 4$$$, that means

    • for $$$i = 1$$$, $$$p_1 \neq p_2$$$
    • for $$$i = 2$$$, $$$p_2 \neq p_3$$$
    • for $$$i = 3$$$, $$$p_3 \neq p_4$$$
    • for $$$i = 4$$$, $$$p_4 \neq p_1$$$

    Statement doesn't explicitly specify that "this should hold for each $$$i$$$", but it's pretty obvious that's what they mean.

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

      right thanks, actually my mistake was a misunderstanding in the concept of '%' after all , newbies learning i guess xD

»
4 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

Seems like problem setters were not very cooperative with the contestants while giving sample test case for Problem D. I agree I missed very simple case when all robbers are in safe position. But I guess it would have been very helpful if we had a case in sample test case which has answer = 0.

»
4 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

Actually it was Div 1+ Div 1.5

»
4 weeks ago, # |
  Vote: I like it +39 Vote: I do not like it

How to write the output-checker of F?

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

    I guess, each time one tries to calculate $$$f(x, y)$$$, return the minimal unused number unless the function was calculated before, in this case return the value we returned last times

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

      Yeah, that sounds pretty good, thanks!

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

      Or maybe $$$f$$$ is just a good hash function for pairs of integers.

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

      This is exactly what I did locally during the contest (I got annoyed with trying to test things by hand, so I wrote a quick simulator to test ideas).

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it -72 Vote: I do not like it

    set $$$f$$$ as a random function

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

What is the proof for problem B?

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

    Here is how I solved the problem :-

    Say we have the array[12,13,27,34,35] and k=2.

    At first we will try to take k distinct elements and make them 0 So, after that the array becomes [0,0,27,34,35]; Now as we can't take any more distinct elements so fill all the next elements by subtracting any previous number in the array say 13.Then the array becomes [0,0,14,21,23]; Now in the second step do the same step however now we can take only k-1 distinct elements as 0 is already in the array.In this way you can do 0(N^2) solution(As constraints are small).You also need to take care of edge cases(k=1).My is a bit messy code(Dont mind that) https://codeforces.com/contest/1408/submission/94349947

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

      Didn't get it could you elaborate more?

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

      Actually you don't need to have O(N^2) you can do it just like this 94480550

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

        Yes true, I realized after the contest that the problem can be done in O(n) time.

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

.....

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

    It is given that the array is sorted.

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

    This is in the problem statement:

    For each i, $$$a_i≠b_i, a_i≠c_i, b_i≠c_i$$$.

    So the testcase is invalid.

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

Um_nik can you please explain your solution for F as you did some complex merging for even and odd length intervals.

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

    Yeah, I did some hard bullshit instead of trivial solution, do you really want to hear it? Why?

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

      Yes I want to know as I was trying for the same and finally resigned after thinking that it was not possible that way.

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

        ok

        If you can solve $$$n$$$, you can solve $$$2n$$$: do solution for two halves and then merge equal sets in $$$n$$$ operations.

        If you can solve $$$n$$$, you can solve $$$n+1$$$: do solution for $$$n$$$, now you have two sets A and B of total size $$$n$$$ and one more set C of size 1. Let's assume that A is larger (or the same size) than B. We'll try to double C by taking parts of A or B and getting rid of B completely. Since we will be doubling C its size will go through powers of 2, and the same is true about the parts we will be taking from A or B. That gives an idea that we have to look at the binary representation of B and take the part from B when we need it. What to do when we don't need it? Let's take a part from A. It's easy to see that the total size of everything we'll take from A is less than even the largest part we'll take from B, so A cannot run out before we use B completely. So after that we'll have only A and C. We'll use no more than $$$n$$$ operations to do it.

        So, the total number of operations is bounded by $$$T(n) \le 2 T(\lfloor n / 2 \rfloor) + 3n / 2$$$ which should result in $$$T(n) \le 3/2 n \log_{2} n$$$.

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

          Thanks, got it.

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

          I was also trying to think in this direction but couldn't solve it. Thanks for posting your explanation. Although the solution of the editorial is impressive, I like your approach more.

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Can anybody elaborate their binary search solution on problem C , i am not able to understand through editorial

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

    For problem C, I did binary search on time variable. For a given time, I calculate the total distance travelled by the person that starts from 0 and I calculate the total distance travelled by person that starts from the end and check whether they cross each other.

    Submission: https://codeforces.com/contest/1408/submission/94324318

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

      The_Devil Great code. Can you please explain what does the variable eps means? I have never used binary search on double/float values. Can you please explain why the while condition is end-start > eps ?

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

        The invariant I have used in the problem is that start variable always points to the time in which it is not possible for the two cars to cross each other and end points to the time for which the two drivers will always cross. start will always begin from 0 since at t=0 they cannot cross and in the worst case when there are no flags, the drivers will require atleast $$$\frac{10^9}{2}$$$ time (I have choosen $$$1e9$$$) time to cross. Now, after I calculate the middle value, I check if the drivers can cross each other. If they cross then we can do end=mid and if they cannot cross we keep start=mid. It is always true that start always points at time at which the drivers can not cross and end always points at the time at which they cross. In the while loop, I decrease end as much as I can and I increase start as much as I can. If end-start<=eps, then I have the lowest end I can achieve which is the least time required. Why did I choose eps as 1e-7: In the question, they have mentioned that they need precision of answers to be 1e-6. eps variable is used to handle that. Normally in integer questions we take jumps of value 1 i.e. we move from one integer to another so we keep eps=1 in integer questions, but in double values we take jumps of eps value and eps value is less than the required precision.

        I learned this concept in Binary Search of EDU Section. I would suggest you to do that.

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

    For a particular value of t, find the position of both the cars(x1 and x2). If x1 < x2, that means the cars have not yet crossed, so we try for a greater value of t. If x1 > x2, then the cars have already crossed each other. So we try for lesser value of t.

    We keep trying like this till the difference between the positions of cars reduces to less than ϵ.

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

    I feel like it is easier to not do binary search but instead find which car reaches a flag first and update the velocities and positions. Keep doing this until the two cars have no flags in between them and then find the remaining time. This is my solution — https://codeforces.com/contest/1408/submission/94324831 If you still aren't clear send me a private message

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

      I also did it with same approach and I think it is more intuitive as compared to binary search.

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

      thanks for your soln ,i had also solved it using your approach but i was interested in bs approach .

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

        I don't really get the BS approach either. It seems quite BS if you get me lol.

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

          lmao, but jokes apart i understood the bs(binary search) from The_Devil's above comment ,thanks to him.

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

    I did with simple speed-distance relation in linear time https://codeforces.com/contest/1408/submission/94328279

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

I found Maximum Spanning Tree in problem E, isn't there a typo in the editorial?

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

    No, as you want to remove the cheapest edges first. You want to minimize the total cost hence maximize the ST cost.

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

    Actually, it technically is a typo but for a different reason. The graph G is not necessarily connected, so it should be called a spanning forest, not a tree.

»
4 weeks ago, # |
  Vote: I like it +57 Vote: I do not like it

Is it so difficult to create nice easy problems? In my opinion D, E, F were nice and A, B, C were ugly.

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

    It is extraordinarily difficult.

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

    I don't think B was ugly (though it seems to have weak pretests)
    I agree on C though. I felt like crying while implementing it. It's been a while since I felt that way. Pure implementation

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

      For real got a headache sadly couldn't find the bug

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

        Found it almost immediately after seeing Failed System Test...

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

    Yes, creating a nice problem is difficult, and creating a problem everyone will consider nice is virtually impossible

    IMO D, E were quite ugly, F was decent, G was very nice, A, B, C were "yet another easy standard problems", so I don't want to judge their niceness

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

What questions to solve so to easily solve questions like B in this contest?

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

    Questions like B.

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

    Basically, none. Cause even Legendary Grandmasters like Radewoosh or even Errichto failed to solve problem B, whereas some pupils did it.

»
4 weeks ago, # |
  Vote: I like it -69 Vote: I do not like it

Worst contest

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Why ternary search doesn't work in problem D? submission

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

    Looks like you are ternary searching on the x shift. Ternary search doesn't work because the function can have multiple local minima. Sample case 2 gives 7 8 [4] 5 6 7 8 [7] 8 9 10 11 12 13 14 which has 2 minimums and ternary search can converge to any of them not necessarily the global minimum.

»
4 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

pretest poor

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

    Why blame the pretests or the problem setter. Why don't you write a perfect code that it can pass all pretests. I mean why rely on them

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

    Horrible audio quality bro...

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

      Yes , i am sorry for that . I will be improving the audio quality soon . What matters currently is distributing the knowledge i have

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

Please help me in question A. My solution is here 94351184. Please tell me where my logic gona wrong. Thanks alot.

»
4 weeks ago, # |
Rev. 7   Vote: I like it -107 Vote: I do not like it

.......

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

    Maybe that is why it called div1+2 :D

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

    The editorial for B skips the hardest part: that the answer is at least 1!

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

    To be fair, most people who FST'd B probably knew how to solve it (or some equivalently difficult problem if they misread), but just glossed over a detail.

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

    Lol, it's trivial. Some people have just fell into a trap on a corner case with constant sequence. Stop whining where you shouldn't because I have seen thousands of harder problems in Div2

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

    ok

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone explain the solution of problem D . couldn't understand what is done in editorial.

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

    Couldn't understand why the solutions work or how it works? any proof etc?

    Why are we only considering the x coordinates only not the why coordinates?

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

No codes?

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

i don't understand why not putting testcase 9 for B.

1) trapping someone is not nice.

2) in some worst case scenario, someone can get free 1000 point by spamming "1 4 4 1 1 1 1" which is ridiculous.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    That's the whole point of CF having pretests/hacks; you have to watch for your own edge cases, and people can get hacks for noticing others fail them.

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

      Maybe this was the original intention, but a lot has changed since CF held its first contests. These days pretests generally do cover corner cases. There are much fewer successful hacks and failed systests than 5 years ago. Of course this leads to people trusting pretests to cover silly corner cases, and I don't think it makes sense to punish them for it.

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

        Indeed, the meta has shifted a bit towards stronger pretests, but not so much that it's unacceptable for authors to design in hack cases if they choose to. I think that's still the intention of hacks, it's just used less frequently nowdays than before.

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

          Intention of hacks is allowing authors to pretend that they wanted to allow hacks when they accidentally didn't include some corner case

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

      I thought that pretests were a side effect of the fact that running all testcases on all submissions would be computationally infeasible if contests want short queue times

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

        I'm not too sure, but I think that's only part of the motivation. The hack mechanic is definitely designed for intentionally weak pretests, and you can see that in older contests with many hacks; the hacks are all for cases intentionally left out of pretests to give opportunities to hack.

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

    3) Whoever prepared B didn't make good multitest.

    Why are you assuming that they left out such a test on purpose?

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

    1000 free points? You have zero chance of getting 10 people in your room with this mistake.

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

      it had happened before where problemsetter deliberately make problem with lot of tricky cases and didn't cover them in pretest.

      i think that's not good and we definitely shouldn't go back there

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

I think the TL on problem D was quite strict. I did an overkill using segment tree but still I feel that N*M*log(C) + C*log(C) should have passed the time limit

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

    I'd rather say: "$$$n, m$$$ shouldn't be up to $$$2000$$$", instead of "TL should be higher".

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

      I would have preferred keeping ai, bi, ci and di to be 1e9. Not sure how many solutions would have failed.

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

      What's the difference? Is it that the later would take more time while system testing?

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

      No, I think the time limit should definitely be higher and the bounds were fine. People who use Java lose ~120-200 ms on getting the JVM to spin up. Small time limits exacerbate this issue.

      I had to remove a sort which was kind of silly in order to get it to run in time; it didn't make the problem or solution any more interesting, it just felt like a waste of 5 minutes needing to optimize something that should have been fine, especially on a problem that was that easy.

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

        Same here, but I didn't remove the sort. I spent my 5 minutes on changing the 2-int Object array to a primitive long (encoding both ints) array, which is faster to sort and managed to pass test within the time limit.

        Even though it is a log factor slower I prefer the "sorting" solution that doesn't depend on the coordinates being just up to $$$10^{6}$$$.

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

can anyone share problem c binary search solution

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Loved the contest, though will lose a lot rating

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

ok

»
4 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

Statement of problem E had a HUGE hint (description of the cycle tells us we can make our graph bipartite).

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

    Sorry, if this sounds stupid, but could you please describe this a bit please. I completely understand the editorial, like, how does making the virtual verticies for each set, and making a bi-partite graph out of it is helping.

    I also get, to why we need to find the Max Spanning Tree.

    Yet, I fail to realize, what could have hinted me, to use all of this. Or what prompts us to do create the virtual vertexes for each set, and making the bi-partite graph out of it.

    Thanks in advance.

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

      Well, there is not much else I can say. $$$i_1 \rightarrow e_1 \rightarrow i_2 \rightarrow e_2 \rightarrow ... i_1$$$. Now we want to make all the colors of the edges different. It's the same as replacing $$$e$$$ with $$$color_e$$$. So like you can imagine one more vertex in the middle of the edge which is the same vertex for the same color.

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

        Right, I get it. That could be used, to hint for creating the virtual vertices, and then, we can see, vertices from set i connect to vertices from set e. This I guess can hint the making of bi-partite graph ( as we have two sets, and edges are only such that they connect vertices from one set to another ).

        Great. Thanks !

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone explain the editorial of the problem D? Or any other way of solving it !!

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

Why does an nlogn approach gives TLE in D. I tried using a multiset to store the suffixes after sorting and then kept on erasing the values while traversing. This is my submission : https://codeforces.com/contest/1408/submission/94342487. Any help would be appreciated.

»
4 weeks ago, # |
  Vote: I like it +72 Vote: I do not like it

How to be familar with FWHT enough?

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

    I didn't use FWHT (even though I typed it up in my code LOL) ...

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

Beautiful E

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

Quite late, but here's my fun screencast with commentaries + solutions + playing chesss during contest :)

Link.

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

in problem 'C' I get "TLE" for my binary search solution any hints! https://codeforces.com/contest/1408/submission/94357957

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

    Since, l and r are "long double" in your code, instead of using "l<r" you should prefer using something like this "fabs(r-l)>10e-7"

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

      One bad but safe way to handle those limits is not handle them, instead just run that loop for ~100 iterations instead of checking those conditions. With 100 iterations you can always reach that conditions.

      PS: 100 iterations is big overbound... less number of iterations also could do the trick...

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

      thank you praveen, unfortunately its output not accurate.

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

    While using doubles it's better to fix the number of iterations of doing binary search (~100 for accuracy upto 1e-9) instead of while(l<r) as you have done in your solution since there can be a few reasons because of which your while loop will never terminate .

    You can learn more about these issues and the proper implementation of binary search on real numbers from the EDU section .

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

During the contest I sent this code https://codeforces.com/contest/1408/submission/94329698 And get WA due to precision

And right now I sent this one, getting AC. https://codeforces.com/contest/1408/submission/94361563

The only difference is: in the first one I use integers in some operations that I know that could be made with integers and later I cast to double, and in the last one I just change all the integer numbers to double. My question is: Is better work only with just one data type or What could be the issue? I thought that would be better if I managed some operations first with integers.

»
4 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

About problem G: Could anyone explain how the polynomial multiplication in the merge operation end up being O(N^2) overall?

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

    The transition ends up looking something like $$$dp_{\text{merge}(A, B)}[i + j]$$$ += $$$dp_A[i] \cdot dp_B[j]$$$ for every two components $$$A$$$ and $$$B$$$ that we merge, for all $$$1 \le i \le size(A)$$$ and $$$1 \le j \le size(B)$$$. That is, we perform $$$O(size(A) \cdot size(B))$$$ operations, and we want to estimate the sum of this over all merges.

    To analyze the total complexity imagine that whenever you merge two components $$$A$$$ and $$$B$$$, you write down the pairs $$$(a, b)$$$ for $$$a \in A$$$ and $$$b \in B$$$. Then the number of pairs you write is equal to the number of operations you perform in a particular merging step. But notice that each pair $$$(u, v)$$$ will be written at most once. This is because once it is written for the first time the vertices $$$u$$$ and $$$v$$$ will lie on the same component on all future steps. There are $$$O(n^2)$$$ possible pairs of vertices, each written at most once, so there's also $$$O(n^2)$$$ total operations.

    Edit: Sorry, I used slightly different notation than the editorial. Here $$$dp_C[sz]$$$ denotes the number of ways to split component $$$C$$$ into $$$sz$$$ sets.

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

      Oh, I see, great explanation, thank you!

»
4 weeks ago, # |
  Vote: I like it -25 Vote: I do not like it

In problem B for test case 4 2 1 2 3 4 the answer should be 2 as 1 2 1 2 0 0 2 2 but in everyones code it is the output 3

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

When I read the solution for F,I just want to laught at myself....Nice problems!Thanks.

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

Anyone with binary search solution for problem C ? Please share..

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

    The objective is to find the time required for the cars to meet. When the two cars meet, say at time $$$t$$$, $$$l = d_1+d_2$$$ where $$$d_1$$$ and $$$d_2$$$ are distances covered by the two cars.

    • $$$t \in [0, l]$$$ ($$$t=l$$$ when $$$\text{speed} = 1$$$ throughout, hence we obtain an upper bound).
    • $$$d_1$$$ and $$$d_2$$$ are monotonic w.r.t. time.

    We can perform a binary search on $$$t$$$ and obtain the answer.

    Submission

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

    You can binary search on distance.

    • Suppose distance is mid, we find times t1 and t2 for the cars to reach this distance mid.

    • How to find t1 ? Each segment of distance between flags contributes (a[i]-a[i-1])/curspeedofcarA to t1. We simply add it and keep incrementing curspeedofcarA. Obviously a[i] should be less then or equal to mid. t2 can be found similarly.

    • If (t1<t2) that means our mid needs to be shifted right for t1 to increase and t2 to decrease so make low = mid + epsilon... and if (t1>t2) inverse analogy follows i.e high = mid-epsilon.

    • At last our answer will be t1.

    • My submission :94377140

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

This contest is very difficult,I think(

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

And don't remember that the real answer is the smaller value of $$$\frac{z}{2}$$$ and your matching size.

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

Not able to understand the solution of Problem D, someone please help

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Please can someone explain the solution of problem D?

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

Can somebody please explain the editorial solution for Problem B? What do they mean by ceil(c / (k-1))? As the constraints were very small I did a brute force solution during the contest and it got accepted. Brute Force Solution The editorial solution looks simple. Can somebody explain?

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

    so basically u can create b1 with the first k distinct elements in the original array. After that u can go on creating new arrays of b with initial elements as 0 and rest k-1 elements as other distinct elements in the original array, so in a way that comes out to be ceil(distinct ele/k-1).U need to take care for k=1 separately for non-division by zero

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

      ronbil Got it. Thank you so much.

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

      so for the test case [2,2,3,5,7,11,13,13,17] my first array be [2,2,3,5,7,. . . .] and second be [0,0,0,0,0,11,13,13,17] my doubt is in the first array i have already uesd 4 distinct elements so what should be the values in place of "." Thanks.

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

Really awesome editorials :)

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

Finally got the right color!

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

can someone explain the editorial of B?

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

Guys like me who just struck till problem D thinks that the problems are really nice . Now after reading the statements of problems E, F and G found them really really nice . It's truly said , " beauty lies in the eyes of beholder " and Pure Mathematics is the most beautiful thing . I will try to upsolve these nice problems now . I think i will have a great day now with these beautiful problems :) Thanks 300iq & isaf27

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

still wondering why the name of first question is "CIRCLE COLORING"

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

Need proof for B that "there exists arrays bi with such number m." and explain why everyone is doing this max(1, (c+k-2)/(k-1))

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

Why does the following approach not working:-

Basically increasing the relative speed(starting with 2) every time a flag is encountered. The flags are processed from left to right ( i & j in the code) and whichever flag is closer to the current position of the car is chosen to update the relative speed.

my code

solution for the pretest (is close but not right):

3.000000
3.666667
2.042857
324619672.333333
53.700000
»
4 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Can any one tell me why my approach giving wrong answer for Problem F. Link To MyCode

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

In problem H, can somebody explain in more detail how to solve maximum matching problem, where a node on the left can be matched with either a prefix or a suffix on the right?

Observation 6 of the editorial tells us a method, but it seems to ignore the existence of $$$r$$$ completely. What happens when for a given $$$x$$$ you don't have such $$$(l, r)$$$ with $$$l \leq x$$$? Maybe I missed some key statement in the editorial, in which case I would appreciate if you could point me to that.

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

    It does not ignore $$$r$$$, as I choose the pair with the smallest $$$r$$$. I forgot to write that after that on $$$r$$$'s of the remaining tuples we have to solve the problem "guy can be matched with a suffix, find the maximum matching".

    About your other question, $$$x$$$ corresponds to the position in the left part. If you can't find a pair for the fixed $$$x$$$, just ignore it.

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

      Let me see if I got it right, so what you are describing is something like:

      1. For each $$$x$$$ decreasingly, try to match it with the pair $$$(l, r)$$$ with minimum $$$r$$$ such that $$$l \geq x$$$ and $$$r$$$ is as small as possible.
      2. For each of the unmatched $$$x$$$ decreasingly, try to match it with some unmatched pair $$$(l, r)$$$ where $$$r \geq n - x + 1$$$ and $$$r$$$ is as small as possible.

      This seems very asymmetrical to me, any small hints why it works?

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

        No-no-no. That's not what I am trying to say.

        Alright, so $$$1$$$ is right.

        After that, you have some unmatched pairs $$$(l, r)$$$, and $$$l$$$ for them does not matter anymore. So your goal is to find the largest matching for $$$r_1, r_2, \ldots, r_k$$$. Where $$$r_i$$$ denotes the number of elements on the suffix that $$$i$$$-th element can be matched with, you can do it in any way you prefer.

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

PD. why ans need add x ?

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

    For all the points who have smaller x-coor difference but larger y-coor difference

»
4 weeks ago, # |
  Vote: I like it -38 Vote: I do not like it

CAN ANYONE EXPLAIN ME C PROBLEM IN SIMPLE LANGUAGE. I JUST USED BRUTE FORCE APPROACH CALCULATE DISTANCE TRAVELLED AT PARTICULAR SPEED (MEANS I TOOK TWO POINTER ONE FRONT OTHER BACK AND FOR TRAVELING TO 1 IT TOOK 1 SECOND FOR FIRST AND TO TRAVEL L-1 IT TOOK 1 SECOND FOR BACK AND I JUST INCREASE THE SPEED AT FRONT AND/OR BACK IF 1 AND/OR L-1 COORDINATE ARE PRESENT IS FLAG ARRAY AND JUST REPEAT THIS PROCESS ). INCREASE THE SPEED ACCORDINGLY AND BREAKED THROUGH THE LOOP AS THE FRONT >=BACK. IS THIS APPROACH WA.

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

Is there any detail editorial for problem I using fwt

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

Can someone explain the solution to problem D ? By now I have understood the following part of the editorial.

Let's define as x our move to the right and as y our move to the up. For all pairs (i,j) of (robber, searchlight) at least one of this should be true: x+ai>cj, y+bi>dj. So if x≤cj−ai then y≥dj−bi+1. Let's make an array r of length C=1e6 and write on each position of x the minimum value of y.

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

I'm highly dissatisfied with your "It's easy to prove" in problem B editorial. If it was so easy, then why did you shit with its preparation (and your vaunty testers that sometimes write "I'm a tester, so provide me with contribution" and collect hundreds of upvotes)? I deem it necessary for you to write a comprehensive analysis for this problem as a lesson to yourself.

»
4 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

But otherwise the round was extremely qualitative, ideaful, and beautiful. Just visible are the huge efforts that you contributed to the round. Thank you for doing so!

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

Can someone explain this line from the editorial of problem E , We will connect vertex i from the left side with all elements of Ai. That implies that there will be m*n edges in this graph . How to calculate MST on this graph since the number of edges are huge??

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

    There won't be $$$mn$$$ edges in the graph, the statement guarantees that $$$\sum\limits_{i=1}^ms_i=\sum\limits_{i=1}^m\left|A_i\right|\leqslant2\cdot10^5$$$.

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

very elegant solution for F! Even G was really beautiful problem. Thanks!!

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
It can be proven, that the graph, which we create using our sets don't have rainbow cycles if and only if our bipartite graph don't have cycles.

Then prove it in the editorial itself or provide link for the same. Can anybody tell me how to prove what's written in the editorial of Problem E?

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

can anyone provide me the binary search solution of problem D?

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

Can "maxflow" works in H? I have one solution based on "HMT". code

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

    It seems that your solution strikes a lot of similarity with tourist ’s solution Link, which I’m struggling to understand for a couple of days now. Could you please check if that’s true?

    Can you give us more details about this ’HMT’ thing? (EDIT: never mind, I guess it means Hall Marriage Theorem)

    The best thing I got is that your solutions seems to solve the hitting set problem as the dual for the bin packing problem. Also, maybe it’s related to the matroid intersection approach briefly mentioned in the editorial, which I’m not familiar with.

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

      HMT must stand for Hall's Marriage Theorem, which my solution is based upon indeed.

      1. Binary search on the answer, $$$k$$$.
      2. We are joining the $$$i$$$-th zero from the left and the $$$(k-1-i)$$$-th zero from the right into a pair for each $$$i$$$ (0-based).
      3. We want to check if a perfect matching exists from these $$$k$$$ segments into distinct numbers inside them.
      4. Let's use Hall's Marriage Theorem. Since all segments have a common point, it's enough to check consecutive sets of segments instead of arbitrary subsets.
      5. A perfect matching exists iff for any $$$i$$$ and $$$j$$$, there are at least $$$k - i - j$$$ distinct numbers between the $$$i$$$-th zero from the left and the $$$j$$$-th zero from the right.
      6. Finally, get rid of binary search. The answer is the minimum of $$$\lfloor z / 2 \rfloor$$$ and $$$f(l, r)$$$ over all $$$0 \le l \le r < n$$$, where $$$f(l, r)$$$ is the number of distinct numbers inside $$$[l; r]$$$ plus the number of zeros outside of $$$[l; r]$$$.
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, I see now. I also had the same idea while upsolving and managed to squeeze a $$$O(n log^2(n))$$$ solution, but didn’t figure out step 6. I guess that still leaves the ‘matroid intersection’ solution in the dark. Thanks!

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

        Also, by solving this problem you are equivalently trying to erase as few elements as possible such that no triples could be formed with the remaining elements (something similar to vertex cover in bipartite graph, or hitting set in general). Initially I thought you were explicitly doing that, and it’s still surprising that it would work. I think that might follow from some strong LP duality properties that I find hard to prove (and I’m wondering in general when this kind of approaches work).

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

          Now I'm sure that mine is exacly the same with tourist :)

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

          However mine is much slower ,LOL.(Though it is O(N*logn))

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

        Sorry can you explain what is “z” in step 6?

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

          The number of zeros in the array (as defined in the editorial).

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

Please explain Problem B test case 4 I am unable to generate the two arrays.

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

Problem E. Can someone please explain the intuition behind the below claim/statement? "It can be proven, that the graph, which we create using our sets don't have rainbow cycles if and only if our bipartite graph don't have cycles"

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

In problem C, Can somebody explain why iteration happened 100 times exactly to find correct mid ? Maybe i am missing something here.

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

can someone help me in understanding problem D?step by step ?or suggest some good editorial of this question.

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

A visual attempt at deciphering problem D (nice problem!) :

Reference Code

(Credit: Thanks to SecondThread's excellent youtube editorial)

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

Is problem D known or something?
It was very hard to even understand the tutorial, but it seemed a lot of people solved it. Once I got the point, it seemed intuitive, but there are still difficult small details that you have to do. For example, the fact that you use exactly the distance to the border of a square, and not +1 (not escape entirely), only so at the end, at the final update, you do +1. Another hard small detail is updating r[x] = max(r[x],r[x+1]) (max prefix), which is not an easy detail.

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

Can Someone Please Explain Problem B Solution and Approach ??

Am not able to understand the Editorial Explanation even after thinking about it for 2 days.

Especially this part It's easy to prove that there exists arrays bi with such number m.

Please Guys Help me out here.

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

Anyone willing to elaborate on G?

I'm probably missing something. Why do we keep DP and traverse edges in ascending order? I believe it is possible that edges forming connections inside of groups aren't necessarily prefix of edges sorted in ascending order. I can't understand editorial at all..

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

Hi can anyone explain of problem d can be solved using binary search? I actually thought of binary search solution. If it is not correct then why is binary search a problem tag?

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

I might be wrong, but I just checked QAQAutoMaton's profile, and I found no submission for 1408I.

If you have a Nlog^2+log^6 code (or perhaps know someone who does), please reply to this with a link to the submission. It would be much appreciated.