vovuh's blog

By vovuh, history, 9 months 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 ZeroAmbition Stepanova, Mikhail PikMike Piklyaev, Maksim Ne0n25 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 opukittpceno_hhr 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

»
9 months 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)

»
9 months ago, # |
  Vote: I like it +24 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

vovuh one love

»
9 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Orange Vovuh

»
9 months 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 .

»
9 months 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.

»
9 months ago, # |
  Vote: I like it +13 Vote: I do not like it

will 15 december held two contest?

»
9 months 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.

»
9 months ago, # |
  Vote: I like it -25 Vote: I do not like it

hoping to qualify for Codeforces platinum!

»
9 months ago, # |
Rev. 3   Vote: I like it +21 Vote: I do not like it

79353118_444821413104507_8018561245638557696_n2.jpg

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

Is the scoring (points per problem) known?

  • »
    »
    9 months 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)"

»
9 months 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 ..

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Same here. I solved 1st and 3rd question on paper within few minutes and when I clicked submit button after writing the code on their editor, connection failed and page could not reload for about an hour. After some time the issue resolved but after submitting solution of 1st question, same thing happened again

    • »
      »
      »
      9 months 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.

»
9 months 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!

»
9 months 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...:(

  • »
    »
    9 months 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://codeforces.com/contest/1272/submission/66702493

  • »
    »
    9 months 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]).

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

      Elegant Solution, can you explain why this holds?

    • »
      »
      »
      9 months 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!

      • »
        »
        »
        »
        9 months 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://codeforces.com/contest/1272/submission/66754733

        • »
          »
          »
          »
          »
          9 months 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.

  • »
    »
    9 months 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.

  • »
    »
    9 months 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]).

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

    very similar to this problem: PIBRO

  • »
    »
    9 months 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

  • »
    »
    9 months 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.

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

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

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

    No, it is dp.

    • »
      »
      »
      9 months 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.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I feel you man.

      • »
        »
        »
        »
        9 months 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.

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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?

      • »
        »
        »
        »
        9 months 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.

  • »
    »
    9 months 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.

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

Any hints for E?

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

    Multi-source bfs on the transposed graph.

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 3   Vote: I like it -8 Vote: I do not like it
      • Build a transpose graph
      • Maintain two queues to obtain the distance from the nearest odd and even numbers respectively.
      • First, push odd numbers to first queue( with odd distance: 0 ) and even numbers to the second( with even distance: 0 )
      • Run bfs using first & second queue respectively
      • For odd numbers print nearest even distance and vice versa
      • sample code: 66742609
    • »
      »
      »
      9 months 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 ?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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

      • »
        »
        »
        »
        9 months 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.

        • »
          »
          »
          »
          »
          9 months 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 !

          • »
            »
            »
            »
            »
            »
            9 months 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.

            • »
              »
              »
              »
              »
              »
              »
              9 months 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?

»
9 months 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.

»
9 months 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?

  • »
    »
    9 months 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.

»
9 months 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 ?

  • »
    »
    9 months 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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    me also. I can not access codeforces.com after 10 minutes.

»
9 months 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.

»
9 months 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

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

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

»
9 months 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??

»
9 months 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.

  • »
    »
    9 months 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.

  • »
    »
    9 months 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 .

»
9 months 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"

»
9 months 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

»
9 months 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.

  • »
    »
    9 months 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 ) ?

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

      bro m2.codeforces.com and codeforces.com were simultaneously down and not only for me but for many candidates. As a result, I left the contest as I was unable to access it. Many times this has happened but every time the contest is unrated then. After one hour when I again checked codeforces.com it was still down but m1.codeforces.com was working. This is wrong I mean why 2 sites are down while the other two were working. The site was completely down for 2 hours. As soon as the contest got over, it was active again. It will appear as a case of partiality with many of the contestants if the round is kept rated. I request MikeMirzayanov sir to please look into the matter as it is not only me complaining but many other users doing the same. There is a reason behind this complaint.

»
9 months 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 ?

»
9 months 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

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

Please give hint for F.

  • »
    »
    9 months 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. :)

»
9 months 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.

»
9 months 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!

  • »
    »
    9 months 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.

  • »
    »
    9 months 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.

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

Can anyone explain how to approach problem B?

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

    Hint: Try the move in a rectangular path.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First count each occurrence of letters.
    To be able to return to initial position you need R = L and U = D so you can pick the min.
    Then If one of the directions is equal to 0 you can only move at most one in other directions.
    Finally you can construct result by moving in a rectangular path (ex: URDL)

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why if one side is equal to zero then it can move at most in one direction Ex: UUUDDDDD There is R and L is equal to zero. 3 U's and 5 D's. So answer must be 3 — UUUDDD But answer is 2. Why?

  • »
    »
    9 months 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

»
9 months 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

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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

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

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

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

what is the idea for problem D

  • »
    »
    9 months 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

  • »
    »
    9 months 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.

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

What is the logic behind problem E

»
9 months 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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      9 months 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.

      • »
        »
        »
        »
        9 months 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.

        • »
          »
          »
          »
          »
          9 months 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.

    • »
      »
      »
      9 months 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.

      • »
        »
        »
        »
        9 months 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.

  • »
    »
    9 months 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

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

Can I know why I got skipped

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maybe you submit two answer that get accepted?

»
9 months 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??

»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

when the editorial will be published...??

»
9 months 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?

  • »
    »
    9 months 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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No. You might have checked predictor before system testing.

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

      It is showing +102 now too.

      • »
        »
        »
        »
        9 months 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.

»
9 months 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.

»
9 months 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).

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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.

      • »
        »
        »
        »
        9 months 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.

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

Problem D is very similar to this problem.

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

Screencast of my testing is available

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

Where i am going wrong in Problem D . my code

»
4 months 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://codeforces.com/contest/1272/submission/79720918