ch_egor's blog

By ch_egor, 7 months 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  

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

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

Perfect time for Chinese users!

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

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

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

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

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

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

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

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

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

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

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

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

What a short announcement it is!

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

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

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

How many tasks will be given?

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

What's the main character of this contest?

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

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

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

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

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

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

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

I hope many hacks and high rating

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

I hope this contest will make me green !

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

»
7 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Is this round a replacement of VK Cup Qualification round?

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

Scoring distribution?

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

Is this round rated?

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

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

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

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

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

I found this on a market

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

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

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

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

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

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

Here in the U.S. ;)

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

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

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

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

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

scoring distribution?

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

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

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

    on again ... off again ...

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

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

        It's so frustrating in the last 15 minutes.

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

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

10 minutes with Internal Server Error :(

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

    ?

    • »
      »
      »
      7 months ago, # ^ |
        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 entering my profile page. Hope it is not rated due to fairness, even if CF predictor told me that my rating will ascend a little.

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

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

Hack page not loading :/

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

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

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

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

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

      Even server was not responding when trying to submit.

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

Please Don't make the contest unrated.

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

Will you make this round unrated?

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

How to solve D ?

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

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    7 months 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

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

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

How to solve E?

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

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

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

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

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

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

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

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

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

Is it rated? :-p

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

    How to Solve F?

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

    Here for upvotes?

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

      use Mo's algorithm with modification

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

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

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

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

cf server dropped harder than hardbass beat in my headphones

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

Semi-rated contest time?

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

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

Really?! not even extending?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

      How do you prove ur soln works?

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

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

      I think you probably meant

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

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

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

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

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

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

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

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

    Same with my D :")

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

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

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

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

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

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

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

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

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

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

  • »
    »
    7 months 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) =(

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

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

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

    it should be rateddd

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

    It should be rated

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

    It should be rated

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 months 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 =(

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

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

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

      99% is actually an underestimation I'd say.

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

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

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

    size of vector dp seem to be the problem

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

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

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

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

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

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

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

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

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

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

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

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

Why still no rating update yet?

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

Is this unrated ???

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

****Ratings please!****

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

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

By when will we have the editorial?

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

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

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

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

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

        two smallest -> 1 and 2

        second smallest -> 2

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

          Thank you it makes sense now ^^.

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

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

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

                Thanks a lot. Understood now!

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

  • »
    »
    7 months 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 '<=' 。

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

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

How to solve F?

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

Greedy, brute force, implementation all in one!

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

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

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

Please publish the editorial ASAP !

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

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

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

What's the approach for problem C?

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

TY for short statements