vovuh's blog

Codeforces Round #605 (Div. 3)
By vovuh, history, 5 years ago, translation, In English

<almost-copy-pasted-part>

Hello! Codeforces Round 605 (Div. 3) will start at Dec/12/2019 16:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

UPD: Great thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for testing the round and help with bugs fixing! Artem is also proposed one of the problems for today's round!

UPD: Editorial is published!

  • Vote: I like it
  • +166
  • Vote: I do not like it

Comments Comments (140)
| Write comment?
»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Hope to see non-black IDs win this contest(for whom this isn't first contest)

→ Reply
»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Anyways I hope high ratings to all the non-black handles

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

vovuh one love

→ Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Orange vovuh

→ Reply
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I think it is the first round made by vovuh as a Master . Good Luck and I hope the contest will be nice .

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Add the information to the right to capture the audience.e.

→ Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

will 15 december held two contest?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

After a long time Codeforces arranged a contest. I am waiting for this contest. I think, the contest will be nice and interesting for me and also for others. Thanks to MikeMirzayanov and vovuh for arranging the [Codeforces Round #605 (Div. 3)] contest.

→ Reply
»
5 years ago, # |
  Vote: I like it -25 Vote: I do not like it

hoping to qualify for Codeforces platinum!

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +21 Vote: I do not like it

79353118_444821413104507_8018561245638557696_n2.jpg

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

Is the scoring (points per problem) known?

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

    "The round will be hosted by rules of educational rounds (extended ACM-ICPC)"

    → Reply
»
5 years ago, # |
  Vote: I like it -17 Vote: I do not like it

codeforces server seems to be broken same code giving diffrent output on my macinhe and server on my machine my code passes the same code while on server produces wrong ans i got 3 penalities due to that still not able to submit ..

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

    Use custom invocation on cases like that, and then debug.

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

    +1 the main website was broken and I wasnot able to open it until the contest was over.

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

      Yup site was broken for me too. Took part from m1.codeforces.com.

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Can anyone hack this solution 66706230?

UPD: Hacked, thx dead_blue!

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve D? I kept going in circles thinking about stack and non-positive difference...:(

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

    I can't tell you how to solve it in English, but you can check my solution, maybe it will help you. https://mirror.codeforces.com/contest/1272/submission/66702493

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

    Maintain 2 arrays, Increasing and Decreasing. Increasing[i] will store maximum increasing subarray till ith element, similarly Decreasing[i]. For each element check if (i+1)th element is greater than (i-1)th element, If true, then we can delete this element and updated ans=max(ans, Inc[i-1] + Dec[i+1]).

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

      Elegant Solution, can you explain why this holds?

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      I didn't use this dp approach. The following is the algorithm I came up with. First find all strictly increasing continuous subarray and store each such subarray's start and end index as an interval. Update the max length for each interval.

      Then iterate through all intervals and check every two adjacent intervals and do the following. 1. if the current interval only has 1 element, remove it, get the next interval if possible and check if the previous interval and this next interval can form a longer strictly increasing subarray. Update max length if necessary.

      1. else if the current interval has more than 1 element, 2a.if the previous interval has more than 1 element, remove the last element of the previous interval and check if the previous and current interval can give a better answer. 2b. else if the previous interval has only 1 element, remove the first element of the current interval and check if the previous and current interval can give a better answer.

      The above solution fails on test 14 by a difference of 1. Can you help explain why this solution is incorrect? My submission is 66729847. Thanks!

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

        Your idea is almost same as me.

        I stored all strictly increasing sub_sequence block.

        Then updated result by comparing all block size.

        After that i took 2 consecutive block each time. If 1st block has size > 1, then we compare the 2nd element from last of 1st block with 1st element of 2nd block. if a < b then we have a length of block1+block2-1. Similarly i checked by ignoring 1st element of 2nd block.

        https://mirror.codeforces.com/contest/1272/submission/66754733

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Yeah, I think our idea are similar in general, except that I made the mistake of comparing value with index in one of the if statement, if only I could realize that during contest :(

          Thanks for replying though, without comparing your code I probably wouldn't even realize that bug in my code.

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

    do dp. dp1[i] = maximum length of increasing contigous subarray having the element of i from 0 to n. dp2[i] = maximum length of increasing contigous subarray having the element of i from n — 1 to i. Find out max length of subarray without removing element.Initially, this is the ans. And then, for every i from 1 to n — 2, check if(dp1[i — 1] + dp2[i + 1] > ans && v[i — 1] < v[i + 1]), if yes, then ans = dp1[i — 1] + dp2[i + 1]. That's it.

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

    Let pre[i] be the maximum possible length of strictly increasing contiguous subarray of array a from index 0 to index i

    Let suf[i] be the maximum possible length of strictly increasing contiguous subarray of array a from index n — 1 to index i

    Loop from i = 1 to n — 2, if a[i — 1] < a[i + 1], then ans = max(ans, pre[i — 1] + suf[i + 1]).

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

    very similar to this problem: PIBRO

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

    This AtCoder Problem is also an interesting one that you can solve using the above technique:

    GCD On Blackboard https://atcoder.jp/contests/abc125/tasks/abc125_c

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

    I've made a string of 0 and 1 of length N-1, where 1 means $$$a_i < a_{i+1}$$$.
    Then applied a regex / 1+ 0 1+ /x, and checked elements near matched 0 if they increase after one deletion (i.e. if exists $$$j$$$ that $$$a_j < a_{j+2}$$$, where $$$j$$$ is near 0). Perl code 66779749.

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

How to solve F? LCS and some post-processing?

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

    No, it is dp.

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

      I tried dp, but tbh, backtracking in dp made it quite implementation heavy.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Same feels. I coded a dp solution with backtracking for around 240 lines. Couldn't fix the bugs within the contest time. Got it accepted after contest.
        You can find my submission here.

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

    Simple DP in $$$O(n^3)$$$. Notice that the answer's length cannot exceed $$$400$$$ and do dynamic programming. $$$dp_{i, j, bal} = $$$ minimum total length of the string with the first $$$i$$$ characters processed in the first string, $$$j$$$ first characters processed in the second string and the current balance is $$$bal$$$. Transitions can be made in a straight-forward way (nested loops) but you should do them carefully or by bfs/recursion.

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

      Out of curiosity, is there a solution faster than cubic, or is the n^3 solution the fastest intended solution?

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

        I tried to come up with some faster solution but failed :( Maybe some cooler guys found something interesting.

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

    Actually, because problem limits were low, I just used dynamic programming.

    My state was (current unincluded character from S, current unincluded character from T, current bracket prefix). For some reason that I do not quite understand, the bracket prefix will not go above 200 and thus my state is 200^3=8000000 which is good.

    My transition is "add open bracket/add close bracket" depending on whether they are possible operations. I store which transition is better so that I can backtrack later to construct the bracket sequence.

    It passed the tests, so I think it's probably correct, but that was one of the ugliest case-check DP I have ever coded. Very unlikely to be official solution.

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

Any hints for E?

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

    Multi-source bfs on the transposed graph.

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

      What is the need for the transpose of the graph ? why a normal graph ( edje from i to a[i]+1,a[i]-1 ) will not work ?

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

    Take 2 additional nodes, and reverse the graph...Think about it afterwards.

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

    Form a graph from a[i]-i to i and a[i]+i to i.(a[i] -i >=1 , a[i]+i<=n) traverse the adjacency list and insert points on the other side of the edge in the queue if parity of both points are diffrent. (these points will have minimum distance which is 1). perform bfs.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Hello ; I constructed the graph in the same way ; but then I was doing DP on this graph...

      What I did was that let say node u has immediate child 'v'. Now if parity(arr[u]) != parity(arr[v]) ; then ans[u] = 1 ( This means that we may reach from u to v using only 1 step ).

      Else ; from all children of node u ( Which will be all v ) ; we may find the answer to node 'u' as ans[u] = min ( ans[u] , ans[v] + 1 ).

      But this gives me WA. Do you know what might go wrong in this approach ?

      CODE

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

        There may be a cycle. So it might possible that you are not updated the current node and it calls again from its child.

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

          Could you please elaborate a bit..

          I understand that there are cylces. I understand the the child might have an edge that is directed back from child to parent ( Or in general from child to some ancestor ).

          Doubt : When we came to that child ; we will come only after visiting the parent ( ancestor ).

          So even if there is an edge from child back to the parent ; we won't go over there again as the parent is visited ; and we don't re-visit the nodes in dfs.

          Clearly I have not understood something ; can you please elaborate a bit more...

          Thanks !

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

            Let take a node having three children{p, n1, n2, n3}, and there is a cycle b/w p and n2. Now your value of p = min(n1, n2, n3}, but when you go to n2, p is already visited but its value is not updated as it depends on value returned by n2.

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

              Ah I see... So you mean that by this we will never update the value of n2 as it's value would have been updated via p ; but P is itself not updated yet as it will get updated in the backtrack move of dfs.

              Have I followed?

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

How to solve E. I thought of bfs + dp but couldn't implement.

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

There is no constrain in problem B that length of string cannot be zero. Empty space should also be taken as correct input. Attempting to use this testcase for hacking shows invalid input. Is this intended?

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

    There are no empty strings in every test and empty strings are not allowed to input at all. Seems like it would be better to mark this in the problem statement more clearly.

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

Am I the only one who accessed CF from http://m1.codeforces.com after solving A ?

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

    The main site did not open for almost 2hr.I thought Round will not be rated but since 2200 users solved d, i think it will be rated.

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

Every day I have headache there is got to be a CF round SMH.

and I think I'm the only person who solved E but not D.

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

https://codefoces.com not working during the contest and I was thinking that my internet stopped working wasted my 10minutes

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

    Yeah mine also, code forces stopped working after solving A .

    → Reply
»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

The server was down throughout the contest. Did I only face the issue??

→ Reply
»
5 years ago, # |
  Vote: I like it -34 Vote: I do not like it

Organizers please make the contest unrated as the site was down during the contest.

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

    Not a valid reason because m1 website was up for the entire contest.

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

    this is not at all a valid reason for contest to be unrated .I also face the same problem , but then i shifted to m1 .

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I think the internet issue / connectivity was the problem and not codeforces "down"

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Need help in E. I thought of the dp solution, i.e let's start visiting every element and finding whether the given conditions satisfy or not. 66716159

→ Reply
»
5 years ago, # |
  Vote: I like it -25 Vote: I do not like it

MikeMirzayanov it is a request. I wasn't able to access the codeforces website after 9 minutes and hence wasn't able to continue with the contest after a wrong submission of A. This is leading a drastic rating drop for me. It is hence my humble request that if it be possible then please do not allow for my rating to change. As a proof that I could have done it, I have submitted another solution of A with a minor tweak. It works just fine and I was ready with it after a minute of my wrong submission but wasn't able to access codeforces due to unavoidable circumstances. I hope you'll help me in any way if possible.

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

    Why you did not continue with any of the other options the management has given ( m1 , m2 , m3 websites ) ?

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

i got a small problem in my code in problem F if someone can help me i just did dp[curr positions in s1][curr position is s2][diff between open and closed brackets] i will represent it as dp[curr1][curr2][val] i can made transitions just if after the transition the val will stay non-negative and then i know the length of the answer is less than or equal to 400 so if length > 400 or the val is > 200 i will just return inf that is my first submission 66726623 which just returned inf and that is my other submission 66727771 which i just return when siz > 1000 and it got accepted can someone explain the what is the problem please ?

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

Thank You vovuh I Loved this contest and I Love Div Three <3

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

Please give hint for F.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Think of a dp with transitions similar to LCS and more state parameters.
    You can find my submission here. :)

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I felt F was implementation heavy for those who are comfortable with top-down dp, especially the backtracking part.

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

If you can't wait to see the official editorial, come to see My Unofficial Editorial :)
Like to see comments and responses from you guys!

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    I think A can be solved on much easier way.

    just calculate sum of current distance from given input. Let say it d. Then max(0,d-4) is answer.

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

    Movement for friend who is in the middle doesn't make any change. Moving left one right will reduce distance by 2 similar for right one. You can reduce at most 4. Finally check reducing making it negative or not.

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

Can anyone explain how to approach problem B?

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

    Hint: Try the move in a rectangular path.

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

    If you go one step right then you also need one step left to come back ,similarly for up and down ...another case is if you can't move up of down then you can't move left and right more than 1 ..hope its enough for this problem

    → Reply
»
5 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

How would you do E? I tried BFS with adjacency vector, but no avail :(. It gives TLE on test 8.

UPD 1: I tried again this time with an array that stores the closest node with opposite parity to make my code faster. Also TLE on test case 8.

66742260

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

    After moving to position 10, you can make 1 more move to position 6 (10 — 4 = 6), position 6 has value 5 which is odd. So that is why the answer is 3.

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

      the answer for 10th position is 1. the answer for 8th position is 3 because : first you move to (8-4)=4th position which has value 6 which is also even (val(8)==4) so you have to move again to pos (4+6)=10 which has value 4 . then you move to pos 6 which has value 5 that is odd . 3 moves

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

"Can't read or parse problem descriptor"-Anybody else having this problem?

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

what is the idea for problem D

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

    See https://mirror.codeforces.com/blog/entry/72086?#comment-563624

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    For each element, remove it and then maximize the ans. For this we try to maintain two arrays(st[n] and ed[n])

    st[i] will store the length of contiguous subarray starting from pos i.

    ed[i] --------------------------------------------- ending at pos i.

    Now if you remove the i-th element check the answer after merging left subarray and right subarray if possible to merge(left element < right element) and maximize the ans.

    My solution

    Better Implementation

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    There are only two situations:

    1. move a letter to obtain the optimal answer.O(n)
    2. dont move a letter to obtain the optimal answer.O(n)

    So the easiest idea is just to implement this two process, and then take the longer length as the answer.

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

What is the logic behind problem E

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

I still can't figure out why this code gives a negative result for problem A.

Somebody help me finding the bug which I can't find. Here's the code 66703687

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

    Changing your array decltype from Long[] to long[] gave AC

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

      I just noticed something like that for my very first time. It works for values to 127. But after that from 128 it doesn't check the equality normally. For example,
      1
      127 127 127
      This test case goes fine. But

      1
      128 128 128
      This doesn't go fine.

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

        Don't compare objects using ==. Use equals().

        Java has a cache of numbers in range [-128, 127], that's why small tests work.

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

          Thanx. I noticed that too. I just didn't know "Java has a cache of numbers in range [-128, 127], that's why small tests work."

          Already updated the code 66762318 Now it worrks. I submitted this 4 times during contest and lost my precious 1 hour. My bad.

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

      I use Long[] instead of long[] when I need to sort the array so that it sorts in guaranteed O(nlogn) time complexity. For primitive array java sometimes give O(n^2) time complexity for almost already sorted array. That gave me TLE in a previous contest problem.

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

        Why are you so worried about time complexity when your array has length only 3.

        → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can not compare two object Long using != always.

    You can look here for details

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

Can I know why I got skipped

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

My rating should have increased by 9 according to CF Predictor but instead it decreased by 5??

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

when the editorial will be published...??

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Is there some error in rating change? The rating predictor predicted a +102 while I got only +74. How such a huge difference?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    According to predictor my rating should have increased +9 but instead I got a -5

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

    No. You might have checked predictor before system testing.

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

      It is showing +102 now too.

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

        You are absolutely right. In my case, it predicted correctly. I believe there might be some issue with the predictor.

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

Low tests in D problem :( My submission got passed but then failed at test 39.

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

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

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

    The editorial update at the top is looking a little weird and confusing as compared to other contests' blog.

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

      I pinned it at the top because I thought that it would be more visible. If it's weird I'll post it as usual at the bottom. Sorry.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +4 Vote: I do not like it

        Yeah I think that'll be better of you post it at the bottom. Just that I have been used to looking at it at the bottom, and I believe other people too. That's why I found it weird.

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

Problem D is very similar to this problem.

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

Screencast of my testing is available

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

please help to find out what's wrong in my solution of problem E https://mirror.codeforces.com/contest/1272/submission/79720918

→ Reply