ch_egor's blog

Codeforces Round #466 (Div. 2)
By ch_egor, 7 years ago, translation, In English

Hello everybody!

Tomorrow in unusual time round will be held using problemset of Moscow programming competition for school students of grades from 6 to 9. Do not be tricked by the age range of the participants, Moscow jury always tries its best to select interesting problems of various topics. Problems were developed by halin.george, Sehnsucht, cdkrot, vintage_Vlad_Makeev and ch_egor.

Thanks to MikeMirzayanov for an excellent platform Codeforces for contests and an excellent platform Polygon, which greatly simplifies the preparation of contests.

Thanks to V--o_o--V for reducing the statements and translating them into english.

Hope to see you in the standings!

UPD1: Scoring 500-1250-1250-1500-2000-2750

UPD2: Our problemsetters are tired because of olympiad, so editorial will be a bit later. We apologize for it.

Winners:

Division 2:

  1. zzs_dasc

  2. Kataoka_Yuuki

  3. AkiLotus

  4. tshil

  5. WatchClannad

Division 1 + 2 (unofficial):

  1. uwi

  2. zzs_dasc

  3. fmota

  4. Kataoka_Yuuki

  5. eddy1021

UPD3: Editorial

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

Comments Comments (205)
| Write comment?
»
7 years ago, # |
  Vote: I like it +29 Vote: I do not like it

What a lovely weekend heading up!! :)

Codeforces round 466 and Codechef lunchtime on Saturday and Codeforces round 467 on Sunday.

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

Perfect time for Chinese users!

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

    Round #464 and #466 are both perfect time for Chinese users!

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

Hope the problems statements are as short as the announcement ! :D

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

this is such a bad time for egypt as it will be 11:30 AM

why don't you make it at the usual time as every other contest

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

    We need intersection between official contest and round because we want to prevent cheating from onsite participants.

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

      And if all contests was at the usual time, some programmers from various countries will never be able to participate

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

      How we could cheat? Access to Internet was blocked. BTW. On every Moscow olympiad (including RosOI regionals) lksh.ru and ejudge.ru weren't blocked. Is it some LKSH PR? UPD. Oh, I understood. We could cheat on Codeforces.

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

    In my time zone, the usual contest is 10:30 or 11:30 am. This one is 4:30 am. You have no right to complain.

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

    You do understand why there aren't so many American algorithmists on this site, right? :))

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

Chinese users will like it because of the time of the contest~

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

Why it's not on the main page?

UPD Now it's ok

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

What a short announcement it is!

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

Does anyone feel like when there are lot of Chinese participants the round gets harder, because Chinese coders are good?

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

    Out of curiosity, are you trying to get the lowest contribution on codeforces right now? This is a seriously legit question, nobody has > -100 contribution by accident. :))

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

How many tasks will be given?

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

What's the main character of this contest?

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

Perfect time setting for Chinese. Especially just after I finished my Chinese New Year :)

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

    its so early for hunting but take care Rengar may attend the round :D

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

    I thought I am the only Jhin-main in Codeforces :D

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

I was a little bit nervous about next contest after completing DIV2 465. but codeforces is always best... 2 in a row...

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

I don't know why tf I posted this comment 7 years ago 😭

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

I hope many hacks and high rating

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

I hope this contest will make me green !

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

The time of this contest is very friendly for China :)

UPD: But seems like the connections is not so friendly,since I'm "500 ERROR" for at least 5 times during the contest... Am I the only one?

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

Is this round a replacement of VK Cup Qualification round?

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

Scoring distribution?

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

Is this round rated?

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

    They didn't announce if it rated or not but they explained the unusual time is for preventing onsite participants from cheating in codeforces so i guess its rated

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

    I guess it's Rated , See the Calendar !!

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

Scoring distribution and Number of problems yet not revealed! Time left to start of contest is 2 hours

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

I found this on a market

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

Would it be rated for contestants having rating below 1900? As the rating has not been mentioned in the announcement.

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

    Did you read the blog title? Since it mentions Div.2 so yes, it should be rated for Div.2

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

      That doesn't imply about the rating I guess. Since in usual announcement or invitation mail it is clearly mentioned about the same, so I doubted. Anyway thanks :)

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

This time isn't so bad for south asian I think ...

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

Here in the U.S. ;)

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

    We usually have about 8 hours for sleep every day. There isn't 8 hours worth of codeforces contests everyday though. This is my 4 am proof for why codeforces > sleep.

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

      Codeforces contests needs clear mind so you should sleep good to participate. but how can you do both?

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

        Sometimes I can't do both so I guess it just depends on the night (tonight was not one of the good nights lol).

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

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

scoring distribution?

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

Currently something is going not so right with the Codeforces server...

Let's hope that everything will be okay soon...

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

    on again ... off again ...

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

      Like a switch. Not totally unreachable, but performing a task (hacking/submitting) is more struggling than usual...

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

        It's so frustrating in the last 15 minutes.

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

          I couldn't submit a solution Because it showed "The requested url couldn't be retrieved" everytime.

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

10 minutes with Internal Server Error :(

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

    lots of times I tried to submit. The server was not responding. Even commenting on this gets a server error.

    ?

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

      I can't do anything during the last 30 minutes, including hacking or entering the standing page. All of the web pages in Codeforces were not available, I can't even enter my profile page. Hope it is not rated due to fairness, even if CF predictor told me that my rating will ascend a little.

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

    I even hadn't submited a problem that should have to be Accepted:(

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

Hack page not loading :/

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

There's issue with hacking page.

UPD: Round should be declared as Semi-rated so that it is fair enough for all.

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

    they can extend the round for like 10 minutes and it will be better than making it unrated .

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

    I agree. The hacking page wasted me at least 20 min....

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

      Even server was not responding when trying to submit.

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

Please Don't make the contest unrated.

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

Will you make this round unrated?

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

How to solve D ?

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

    Initialize l = -1e9 and r = 1e9. Whenever one of two conditions(bi equal 1 and previous 4 values equal 0 or bi equal 0 and previous 4 values equal 1) occur then update l or r accordingly. This works because for other conditions array values will lie between l and r.

    Code

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

    The problem ensures that a solution exist, so each time that b[i]!=b[i-1] you just update l and r for a valid value that make this change

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

What's wrong with my code? Why TL? http://mirror.codeforces.com/contest/940/submission/35642398

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

    if n < k, then you set n to 0 and 0 % k is always 0 so it repeats infinitely.

    Try this case:

    4 100 100 100

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

I only have a solution for E when n % c <= sqrt(n). What's the full solution?

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

How to solve E?

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

    I'm not sure, but i think that is only good divide in subarrays of size multiple of c. So, u can do a dinamic programming using your current position and take the min in go to the pos+1 or pos+c(in this case you have to know the minimun element fast)

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

      If that's correct then you can just use sparse tables to quickly grab the min in O(1) and then just do the dp right?

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

        Yes, you just have to know this min fast enough, has many ways to do this :D
        A pre process of costs is welcome too

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

          I used multiset to get min in log(n) time. Much easier than implementing sparse tables or segment tree.

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

      But if there are many multiples of c in the range <n in that case would you check every possible solutions of dividing the subarrays in multiples of c?If yes how would you do proceed then?

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

        Is ever better dividing by c. Try to understand the why, but is not too hard

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

        Denote the smallest value of first i as d[i]. Then consider the length of the last partition part(the one include the last element). If its length is smaller than c, then it's not better than d[i — 1] + a[i]. If its length is larger than or equal to c, then it's always better to cut another one at i — c. And in this case, the value is not better than d[i — c] + sum(i — c + 1 to i) — min(i — c + 1 to i). So in a word, we just have to calculate min(d[i — c] + sum(i — c + 1 to i) — min(i — c + 1 to i), d[i — 1] + a[i]).

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

Usual 'connection was reset' and 'try again' later when the contest time will be over.

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

Is it rated? :-p

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

    Here for upvotes?

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

      use Mo's algorithm with modification

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

        SO complexity is O(n^(5/3) logn)??

        Or can be logn be got rid of?

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

          Use another sqrt decomposition to know the mex value, you do updates in constant time and query in , since you make only N queries the overall complexity becomes

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

    This is the only time "is it rated ?" question didn't get down voted.

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

cf server dropped harder than hardbass beat in my headphones

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

Semi-rated contest time?

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

Really?! not even extending?

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

To be fair, Those who their rating change is positive their contest should be rated, and the other's contest should be unrated .

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

Come on. Would those last 10 min change that much?

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

    On the last minute , I was about submitting a solution for the problem D .. But, I hope that the contest is rated for those who their rating change is positive !

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

    I spent time trying to submit, I had only a small change to make in one more solution... Perhaps my score would be better had the server been working ok...

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

    I coudn't submit my solution to D, but, probably, it would have failed.

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

fast system testing but during the contest codeforces broke down much ):

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

Couldn't submit D in the last 3-4 mins. Server issues...

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

I did not understand problem (statement) E. Can someone please explain it to me?

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

    statement is quite confusing, but examples are highly helpful to get into it

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

    I approached this by dynamic programming.

    Let's make dpi the minimum value of the i-length prefix of the array a (1-indexed).

    Also, let's define sum(a, b) and min(a, b), respectively, the total values and the minimum values in the continuous segment [a, b] in the array.

    Initially dpi = 0.

    If i < c, dpi = dpi - 1 + ai.

    Otherwise, dpi = min(dpi - 1 + ai, dpi - c + sum(i - c + 1, i) - min(i - c + 1, i)).

    The sum and min-value of each segment can be calculated in O(logN) time complexity by RMQ-based approaches (I myself used segment trees).

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

      Since range is a sliding window you can do it using multi set.

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

        Thanks for the suggestion :D

        After drafting out the approach, I coded without thinking, and make every calculation as formal (and also universal) as possible :D didn't even think about sliding window actually ;)

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

      How do you prove ur soln works?

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

        First of all, as the problem itself provides, we can see that no matter how we chose the segments, it will always turn out to be equivalent with a distribution, such as each element is either in a size-1 segment or a size-c segment.

        Secondly, if we merge two adjacent size-c segments together, there may be two cases:

        • If the minimum values of both segments (before merging) are also the 2 minimums of the merged one, the total value of these 2 * c element will remain the same.

        • Otherwise, when one minimum value of one value is higher than an arbitrary element in the other segment (which is not the minimum of that), the 2 minimums now will have the total value lower than that when the segments were separated, therefore, increasing the total value.

        In conclusion, there is no point in merging any adjacent size-c segments.

        Therefore, during the DP process, each element has (at most) two choices: to stand in a size-1 segment, or in a size-c segment with c - 1 elements standing before it (provided there are enough elements).

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

      I think you probably meant

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

        Oops, a fatal mistake while typing. Thank you! :D

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

If I didn't get fst on C, I would be purple......so sad

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

There were glitches in server, but only for short time. I don't think for that round should be unrated. Well, it was first time I submitted all four correctly. I hope, it is rated.

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

In the last few minutes of the round submission page was not loading properly. So I could not submit the solution of the third one. Bad luck that the code I was goind to submit for C at last minute was correct indeed. Happened with anyone else??

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

    Me too. My code for problem C was accepted the first time I submitted after system testing was over, and I was not able to submit that code during the last 5 minutes of the contest.

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

    Had around 3 mins to submit the D which I had corrected. Still couldn't submit it. And it turned out to be correct

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

    Same with my D :")

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

why isn't there any announcement whether it is rated or not ?

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

    It is not easy to take a decision for headquarters.. The fate of 3377 participiants depends on them :)

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

can someone please help me! my submission for C (on ideone)

submission of codeforces is going runtime error on case 26!!! why?? can someone tell

the case is

7 5000

qqqqqqq

it works properly on ideone and other places!! i feel its unfair because i could not find anything wrong! please help me, atleast prove me wrong so that i can sleep in peace! thank you!

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

When I handle 'same number' case in D it fails for some reason. Help me to understand why.
AC: http://mirror.codeforces.com/contest/940/submission/35644516
WA: http://mirror.codeforces.com/contest/940/submission/35645618
diff: http://www.mergely.com/sf680QoI/

I understand that I can only decrease r and increase l, but anyway how is it possible that i got WA with those additional checks...

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

We encountered a ddos-attack, which affected the round. I'm investigating the impact. If the impact is not fatal, then the round should be rated. Currently I'm sticking to the decision to leave the round rated.

I apologize to the participants who encountered difficulties in submitting solutions. Sorry about it.

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

    I think that it was ok. I had some difficulties but not the end of the world. It should be rated. :)

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

      I also think so, because the complexities were, but for a minute trying to solve a task, I solved it. Sorry for my english =)

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

    Everyone was affected, so it should be rated I think. Tho I didnt participate

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

    The server difficulties didn't impact so much on the ranklist. I think it should be rated, but the rest depends on you! :)

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

    I agree, but I don't remember when was the last normal round(without lags and server crashings) =(

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

      I'm surprised. For me almost all rounds in 2018 happen without server-side issues. At least I didn't notice them, no notifications from monitoring systems and no massive comments about such cases from users. Can you clarify issues? BTW, I see that you didn't take part much in recent contests.

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

    At the end I faced some difficulties when I tried to submit D. But the impact is not too much to make it unrated. It should be rated.

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

    it should be rateddd

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

    It should be rated

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

    It should be rated

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

    Hello, MikeMirzayanov. Can you explain the compiler issue? Thanks in advance.

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

    In fact,most of us had solved the problem we can before the impact,because this round is a little easier.Therefore,it's ok to be rated.

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

    Would you please exam the register system?I can not receive the Email confirmation by anyway.MikeMirzayanov

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

    D U D O S E R

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

    Consider the plea of participants who managed to solve the problem towards the end of the contest and were not able to submit it because of the issue.

    I was also facing the issue while submitting solution for problem C, 30 mins before the end but luckily I was able to submit it. 5 mins before the end, I managed to solve problem D and due to the server crashes I couldn't submit it. :/

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

    New way to improve rating: If you're having a bad contest, ddos the site and hope for unrated.

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

Woh! It was a great contest! All problems were interesting to solve! :D

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

i don't know why i wa http://mirror.codeforces.com/contest/940/submission/35646284 who can give me the data?

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

    check diagnostics in the wrong answer test case "Diagnostics detected issues [cpp.clang++-diagnose]: p71.cpp:57:4: runtime error: index -1 out of bounds for type 'int [200005]' SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior p71.cpp:57:4 in"

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

Same code compiled with C++11 and C++14 made different result.

C++11: Code1 Compilation error (which cost more than 10 minutes)
C++14: Code2 Accepted

Can someone tell me why?

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

It seems to me that some of inputs for D were generated in invalid way

AC: http://mirror.codeforces.com/contest/940/submission/35649388
If I add some validation into my submission it fails
RE: http://mirror.codeforces.com/contest/940/submission/35649409

diff: http://www.mergely.com/diBmBHT8/

What I'm validating:
condition ai, ai - 1, ai - 2, ai - 3, ai - 4 > r must be false if current number in b' is 1 and previous 4 numbers were also 1.
condition ai, ai - 1, ai - 2, ai - 3, ai - 4 < l must be false if current number in b' is 0 and previous 4 numbers were also 0.

If at some point we have to increase r or decrease l to hold conditions above, it means that there is a conflict, because on each step we calculate lowest possible r and highest possible l.

Is there a mistake in my logic?

halin.george, Sehnsucht, vintage_Vlad_Makeev, cdkrot, vintage_Vlad_Makeev, ch_egor guys take a look

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

    I think you should not use the Deque. For this example:

    10
1 2 3 4 -1 -2 -3 -4 -5 -6
0000111110

    The answer should be:

    5 -7

    I mean, this sequence is not in descending order or ascending order.

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

      And my solution gives that answer :)
      as i understand you didn't get the point of queue. it is used to maintain min/max of all current subarrays. check https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/

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

        The process of the program, I think the size of deque may less than 4 on test 6. I think you can simpliy use the Array instead of deque.

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

          size doesn't matter. please check AC link and try to understand sliding window approach

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

        I am a user of C++. I can't handle your problem about Java. :)

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

          sliding window is not related to language. check C++ variant on geekforces, link is above

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

            I don't think that this problem is a sliding window problem. The problem is to get some inflection points for array b, I think. It means that we should get the point which the point is 0, the previous point is 1 and vise versa.

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

              sliding window can be used to maintain min/max of subarrays. don't reply

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

                Although it does help but since window size is just 5 linear checking is good enough

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

                  agree. i did it just for practice. did you check the main point of my post btw? everyone ignores me =(

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

    Your assertions are incorrect. You should swap minDec and maxDec in your assertions. Also it is generally a nice idea to take a good look at your code before posting something like "The tests are incorrect" and so on, because in 99% of the cases they are correct. I'm sure you could've found this mistake by yourself.

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

      i finally got it. thanks. sorry xD

      my mistake was wrong transformation of boolean expression.
      correct one looks like that:
      !(ai > r && ai - 1 > r) => (ai <= r || ai - 1 <= r)
      and my mistake was to transform it as:
      !(ai > r && ai - 1 > r) => (ai <= r && ai - 1 <= r)

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

      99% is actually an underestimation I'd say.

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

Why rating changes is so long? I spent a lot of time and efforts to solve my first problems. I wrote it in train, where is no Wi-Fi or 4G, I submited it as soon as train arrived at rare stations. I so tired, I need to know what happens with my rating. So this silent expectation makes me crazy!

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

Can someone please help me with this on problem E?

I seem to be getting random REs with the same code. All of these codes I just declare some random variables, or increasing array size, so they're practically the same.

My latest submission.

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

    size of vector dp seem to be the problem

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

      Thank you very much :((( I'm still not getting why it doesn't RE on some tests, but fixed and ACed now

      That was a silly mistake

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

        Nice solution and excellent code style! I learned a lot from your code.

        And may you share some problems similar to this, or some good dp problems? I want some practice. Thanks !!

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

          Thanks :D I tend to get lost in my own code, so I have to keep it simple.

          You can search for problems by tags in the problemset. Here

          The dp in problem 940E is actually the well-known "house robber" problem. You can try looking it up.

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

My dp in E just missed a line f[i] = max(f[i-1], f[i]); and I got WA.

I actually ignored the truth that f[i] can be equal to f[i-1] which means the i position number is split as a single partition.

Very sad to review the mistake because I lost a quite good opportunity to increase my rating.

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

    Can you please explain your logic behind E. I cannot understand the dp part. Thanks

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

Hi ch_egor!

I'd like to thank you for the exciting competition, but I think there's something wrong with the test case #5 of problem D.

I used assert(minl <= maxl); assert(minr <= maxr); assert(minl <= maxr); to make sure my answer was legal. However, I got an RE at test case #5, see 35641797.

Then I tried to delete those asserts and submitted it 35642151 again, but I was surprised. Not only it passed pretest, but also the system test. I didn't made any change except removing these asserts!

It's good for me that test case #5 is not large (n = 95) and I can copy it all. Finally I found out why.

Here's array a and b at i = 8 (counted from 0):

i:...4 5 6 7 8 ...

a:...94 96 91 98 95 ...

b:...0 0 0 0 0 ...

Now that b[8] = 0 and b[7] = 0, we have r >= 91.

And Here's array a and b at i = 38 (counted from 0):

i:...34 35 36 37 38 ...

a:...62 68 63 64 69 ...

b:...1 1 1 1 0 ...

Now that b[38] = 0 and b[37] = 1, we have r < 62.

So, assert(minr <= maxr) was false and returned an RE. And in fact, this case has no solution.

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

    Oops I made a serious mistake, sorry for the disturbance.

    EDIT: Yet there still exist problems I cannot explain :(

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

      Hmmmm... I'm still confused. Here's another problem of this test case.

      i:...29 30 31 32 33 34...

      a:...-75 -80 -78 -74 -76 62...

      b:...1 1 1 1 1 0

      Since b[33] = 1, we have r >= -80 (otherwise b[33] should be 0 according to condition 1).

      Since b[34] = 0, we have r < -80. Strange.

      It's midnight here so I'll work on it tomorrow. By the way, forget about my solutions above, they make no sense. (I wonder how could they pass the system test...unbelievable)

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

        Are you talking about test case #5?

        Then you might have miscounted indexes in b: <23 times 0><15 times 1>...

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

        Since b[33] = 1, we have r >= -80

        Also while proving/disproving, dont forget it can continue to be 1 without even satifying condition 1

        b[i] = b[i-1] part

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

        Yes, dantrag is right, I happened to delete something in my input file. It's my fault.

        Now everything makes sense. I get an AC after bug fixed. 35665198

        Thank you guys anyway.

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

Why still no rating update yet?

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

Is this unrated ???

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

we want rating we want rating we want rating ho ho ho ho

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

By when will we have the editorial?

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

Can any one explain problem E to me, or explain the sample case in the statement please ?

The value of some array b of length k is the sum of its elements except for the [k/c] smallest. For example, the value of the array [3, 1, 6, 5, 2] with c = 2 is 3 + 6 + 5 = 14.

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

    length of array, k = 5
    c = 2
    [k/c] = 2
    so , sum of array without considering "2" smallest values is 3+6+5 = 14
    PS: comment has been edited

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

      what about 1 ? it should be 3+1+6+5 no ?

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

        two smallest -> 1 and 2

        second smallest -> 2

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

          Thank you it makes sense now ^^.

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

            Hi, Need help to understand it. The example is perfect that we should not consider [k/c] numbers. The second, third and fourth examples doesn't make sense to me.

            Input : 12 10 1 1 10 10 10 10 10 10 9 10 10 10

            Here, [k/c] is 2. In the second example one of the optimal partitions is [1, 1], [10, 10, 10, 10, 10, 10, 9, 10, 10, 10] with the values 2 and 90 respectively.

            How did this happen. We shouldn't consider the least 2 right? so, 1 ,1 in shouldn't be considered right?

            Please help, I'm unable to understand the examples

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

              floor(k/c) numbers need to be considered. So in second example in partitions - [1 1] floor(2/10) i.e. 0 smallest numbers are removed. [10 10 10 10 10 10 9 10 10 10] floor(10/10) i.e. 1 smallest number is removed from sum. So total sum is 9*10+1+1 = 92

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

Can anyone explain, why this output is bad? 35663077 I think is it ok.

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

    Check i = 88 i: 84 85 86 87 88 a: 33 34 34 42 32 b: 1 1 1 1 0

    b[88] = 0 so r < 32. Be careful with '<' and '<=' 。

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

How to solve F?

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

Greedy, brute force, implementation all in one!

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

What happened for the people get stared? I didn't realize what I have done bad and I found I was unrated(* Acvator). Also, I found many of the tops are unrated(By get a star in front of it). What happened? Can anybody explain this? http://mirror.codeforces.com/contest/940/standings Many of the Black name's grade are canceled.

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

    The top rated guys are Div 1 contestants and this contest was for div2 partcipants that's why they are not rated.

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

TY for short statements

→ Reply