ch_egor's blog

By ch_egor, 21 month(s) 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, _kun_, gritukan 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. I_Love_Kirino

  3. Akikaze

  4. tshil

  5. WatchClannad

Division 1 + 2 (unofficial):

  1. uwi

  2. zzs_dasc

  3. FMota

  4. I_Love_Kirino

  5. eddy1021

UPD3: Editorial

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

»
21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +42 Vote: I do not like it

Perfect time for Chinese users!

  • »
    »
    21 month(s) 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!

»
21 month(s) 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

»
21 month(s) 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

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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

    • »
      »
      »
      21 month(s) 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.

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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? :))

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it -20 Vote: I do not like it

What a short announcement it is!

»
21 month(s) 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?

  • »
    »
    21 month(s) 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. :))

»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

How many tasks will be given?

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What's the main character of this contest?

»
21 month(s) 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 :)

  • »
    »
    21 month(s) 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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

»
21 month(s) 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...

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Unique contests have unique times... :)) 100% this contest will be great like others. I hope questions judges have no problems and contest have beautifull questions ;)

»
21 month(s) ago, # |
  Vote: I like it -24 Vote: I do not like it

I hope many hacks and high rating

»
21 month(s) ago, # |
  Vote: I like it +24 Vote: I do not like it

I hope this contest will make me green !

»
21 month(s) 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?

»
21 month(s) ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Is this round a replacement of VK Cup Qualification round?

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Scoring distribution?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this round rated?

  • »
    »
    21 month(s) 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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

»
21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it +48 Vote: I do not like it

I found this on a market

»
21 month(s) 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.

  • »
    »
    21 month(s) 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

    • »
      »
      »
      21 month(s) 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 :)

»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

Here in the U.S. ;)

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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?

      • »
        »
        »
        »
        21 month(s) 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).

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

scoring distribution?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

It's on my mind since yesterday the contest is today at 12:00

Today 11:15 on codeforces solving some problems while waiting for the contest to begin..

At 11:44 accidentally see:

"Contest is running Codeforces Round #466 (Div. 2)"

The contest is at 11:30 not 12:00 -_____-

»
21 month(s) 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...

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    on again ... off again ...

    • »
      »
      »
      21 month(s) 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...

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        It's so frustrating in the last 15 minutes.

        • »
          »
          »
          »
          »
          21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +22 Vote: I do not like it

10 minutes with Internal Server Error :(

  • »
    »
    21 month(s) 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.

    ?

    • »
      »
      »
      21 month(s) 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.

  • »
    »
    21 month(s) 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:(

»
21 month(s) ago, # |
  Vote: I like it +14 Vote: I do not like it

Hack page not loading :/

»
21 month(s) 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.

  • »
    »
    21 month(s) 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 .

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      Even server was not responding when trying to submit.

»
21 month(s) ago, # |
  Vote: I like it +51 Vote: I do not like it

Please Don't make the contest unrated.

»
21 month(s) ago, # |
  Vote: I like it +26 Vote: I do not like it

Will you make this round unrated?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D ?

  • »
    »
    21 month(s) 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

  • »
    »
    21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    21 month(s) 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

»
21 month(s) 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?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

  • »
    »
    21 month(s) 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)

    • »
      »
      »
      21 month(s) 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?

      • »
        »
        »
        »
        21 month(s) 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

        • »
          »
          »
          »
          »
          21 month(s) 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.

    • »
      »
      »
      21 month(s) 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?

      • »
        »
        »
        »
        21 month(s) 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

      • »
        »
        »
        »
        21 month(s) 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]).

»
21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +24 Vote: I do not like it

Is it rated? :-p

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to Solve F?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Here for upvotes?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      use Mo's algorithm with modification

      • »
        »
        »
        »
        21 month(s) 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?

        • »
          »
          »
          »
          »
          21 month(s) 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

  • »
    »
    21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

cf server dropped harder than hardbass beat in my headphones

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Semi-rated contest time?

»
21 month(s) ago, # |
  Vote: I like it -35 Vote: I do not like it

make this contest unrated. In may case, the codeforces server keeps reseting up to 30min.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Really?! not even extending?

»
21 month(s) 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 .

»
21 month(s) ago, # |
  Vote: I like it +34 Vote: I do not like it

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

  • »
    »
    21 month(s) 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 !

  • »
    »
    21 month(s) 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...

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what if someone had the solution at 1.50hrs and his solution was ac solution... instead of getting +20 he/she will get -90 ... 10 mins won't change that much...sure... -_-

»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
21 month(s) 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?

  • »
    »
    21 month(s) 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

  • »
    »
    21 month(s) 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).

    • »
      »
      »
      21 month(s) 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.

      • »
        »
        »
        »
        21 month(s) 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 ;)

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      How do you prove ur soln works?

      • »
        »
        »
        »
        21 month(s) 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).

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      I think you probably meant

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
21 month(s) 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

»
21 month(s) 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.

»
21 month(s) 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??

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same with my D :")

»
21 month(s) 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 ?

  • »
    »
    21 month(s) 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 :)

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I faced some problems submitting my solution during contest... was it because of some problem with codeforces ??

»
21 month(s) 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!

»
21 month(s) 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://codeforces.com/contest/940/submission/35644516
WA: http://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...

»
21 month(s) 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.

  • »
    »
    21 month(s) 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. :)

    • »
      »
      »
      21 month(s) 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 =)

  • »
    »
    21 month(s) 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

  • »
    »
    21 month(s) 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! :)

  • »
    »
    21 month(s) 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) =(

    • »
      »
      »
      21 month(s) 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.

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it should be rateddd

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It should be rated

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    It should be rated

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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.

  • »
    »
    21 month(s) 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

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    21 month(s) 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. :/

  • »
    »
    21 month(s) 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.

»
21 month(s) 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

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    21 month(s) 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"

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you!i have found my bug!

»
21 month(s) 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?

»
21 month(s) 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://codeforces.com/contest/940/submission/35649388
If I add some validation into my submission it fails
RE: http://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, gritukan, _kun_, gritukan, ch_egor guys take a look

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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/

      • »
        »
        »
        »
        21 month(s) 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.

        • »
          »
          »
          »
          »
          21 month(s) 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

      • »
        »
        »
        »
        21 month(s) 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. :)

        • »
          »
          »
          »
          »
          21 month(s) 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

          • »
            »
            »
            »
            »
            »
            21 month(s) 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.

            • »
              »
              »
              »
              »
              »
              »
              21 month(s) 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

              • »
                »
                »
                »
                »
                »
                »
                »
                21 month(s) 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  21 month(s) 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 =(

  • »
    »
    21 month(s) 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.

    • »
      »
      »
      21 month(s) 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)

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      99% is actually an underestimation I'd say.

»
21 month(s) 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!

»
21 month(s) 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.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    size of vector dp seem to be the problem

    • »
      »
      »
      21 month(s) 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

      • »
        »
        »
        »
        21 month(s) 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 !!

        • »
          »
          »
          »
          »
          21 month(s) 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.

»
21 month(s) 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.

  • »
    »
    21 month(s) 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

»
21 month(s) 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.

  • »
    »
    21 month(s) 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 :(

    • »
      »
      »
      21 month(s) 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)

      • »
        »
        »
        »
        21 month(s) 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>...

      • »
        »
        »
        »
        21 month(s) 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

      • »
        »
        »
        »
        21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Why still no rating update yet?

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Is this unrated ???

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

****Ratings please!****

»
21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

By when will we have the editorial?

»
21 month(s) 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.

  • »
    »
    21 month(s) 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

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        two smallest -> 1 and 2

        second smallest -> 2

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you it makes sense now ^^.

          • »
            »
            »
            »
            »
            »
            21 month(s) 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

            • »
              »
              »
              »
              »
              »
              »
              21 month(s) 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

              • »
                »
                »
                »
                »
                »
                »
                »
                21 month(s) ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Thanks a lot. Understood now!

»
21 month(s) 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.

  • »
    »
    21 month(s) 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 '<=' 。

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. I dont understand how works min_element (it works on half-open interval), so there was the problem. Then it AC me. 35678006.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Greedy, brute force, implementation all in one!

»
21 month(s) 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://codeforces.com/contest/940/standings Many of the Black name's grade are canceled.

  • »
    »
    21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it -6 Vote: I do not like it

Please publish the editorial ASAP !

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem difficulty of this contest : A<D<C<B

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What's the approach for problem C?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

TY for short statements