KAN's blog

By KAN, 4 months ago, translation, In English,

Hi!

The Codeforces Round #464 (Div. 2) is going to be held on Saturday, 17 February 2018 at 10:05 UTC for participants from division 2.

The round is based on XIV Nizhny Novgorod Olympiad in Informatics named after V. D. Lelyukh for high school students, which will take place on Saturday in Nizhny Novgorod. However, the problems for the Olympiad and for the round are not completely identical.

The problems were prepared by KAP, ashmelev, ZhNV, kuzmichev_dima, demon1999, SYury, mmatrosov and me. Thanks to mike_live and vepifanov for testing the problems, and gritukan and MikeMirzayanov for helping us to host the round on Codeforces!

As usual, participants from division 1 can take part out of competition.

Good luck and have fun!

UPD: There will be 6 problems with the following scores: 500-1000-1500-2000-2500-2750.

You will be able to view submissions and tests after the end of the olympiad in Nizhny Novgorod around 13:30 UTC.

Congratulations to winners!

Div. 2:

  1. LitiIsPretty
  2. newbiedmy
  3. lijian666
  4. S.H.I.E.L.D
  5. OYZYWIN

Div. 1:

  1. dotorya
  2. eddy1021
  3. DmitryGrigorev
  4. uwi
  5. georgerapeanu

The editorial is here.

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

»
4 months ago, # |
Rev. 2   Vote: I like it +35 Vote: I do not like it

It's Codeforces Round #464 Div.2 not #265 Div 1. Correct me if I was wrong.

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

Hope that the problem statements are as short as the announcement.

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

high rating for every one :D

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

4 days 4 amazing rated contests!!

i'm feeling lucky!! 4 days doing favorite thing! XD

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

    4 rated contests?

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

      It's including tomorrow's contest! I'm sure that it will not go unrated! And ya 4 rated contest for div 2 XD

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

How many problems in Round #464 ?

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

    I think 5.

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

      If it is 5,generally saw that div2 C problem is solve more than 1000. if it is more than 5,C is solve besides 1000.

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

if someone will become div. 1 in this round .. Is (Educational Codeforces Round 38) will become unrated for him ?

UPD: Sorry i didn't see that Hack is opened 12 hours only in this round xD

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

    No, because hack period for this educational is only 12h length so the rating will be updated until the cf 464 will start

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

      yeah , i didn't see that xD .. Thanks

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it +26 Vote: I do not like it

        Hey, your expectation was justified!

        Participiant MiteshAgrawal became Div.1 on Educational Codeforces Round 38 (rated for Div. 2) and got +139 on Codeforces Round #464 (Div. 2).

        Here is the link to standings: click.

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

          "Just take advantage of bug :v"

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

          Oh, there is also somebody who became Div.1 on Educational Codeforces Round 38 (rated for Div. 2) and fell to Div. 2 on Codeforces Round #464 (Div. 2).

          Look!.

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

It is rated for Div.2.4 days 4 amazing rated contests!!

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

Will the scoring distribution be announced soon?

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

Look at the first line of the announcement — It should be "Hi, Codeforces". I'm afraid that the author should be a litle more careful.

»
4 months ago, # |
  Vote: I like it -28 Vote: I do not like it

Can you please extend time for half an hour.

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

Perfect time for Chinese users!

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

    But it could be better! ---- I'm having dinner during this time.

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

    It is very good to have a contest when I am working, not sleeping!

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

Finally a contest when I'm not working :)

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

Back to back contests. Passed a great weekend.

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

What a pitty! I hava to have dinner when the contest starting.

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

4 days 4 rated contests for div.2... perfect ending of valentine's week...xD

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

When will be the rating updated for "Codeforces Educational round#38"???

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

Probably it is the first time for Div-2 users when their ratings will be updated twice a day.

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

    But in December ratings of Educational round 35 updated at the same time with Goodbye 2017.

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

      This because the Goodbye 2018 is held for two division (div1 + div2 combine). However, this contest is only for div 2.

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

to newbieeeeeee

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

Could you please update the information about the number of problems and their scoring distribution?

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

Seldom to see so friendly a round time for East Asia and Southeast Asia participants!

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

How many problems are there in this round?

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

For technical reasons, system testing of Educational Codeforces Round 38 (рейтинговый для Див. 2) is delayed until the end of this round. After the round, the following sequence of events will happen: system testing of Round #464, system testing of Educational Round #38, rating updates for the Educational Round, rating updates for Round #464, in that order. Ratings for Round #464 will be updated for participants who were in div. 2 prior to the Educational Round.

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

    So rating updates for Round #464 will be ready by tomorrow???

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

For problem A, do A,B,C need to be distince planes?

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

When local time in the 1-st timezone is 1 hour, local time in the i-th timezone is i hours.

How 3 hours (in first timezone) is equal to 1 hour (in the second timezone) and 2 hours (in the third timezone)?

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

    Please ask questions with "ask a question' button on the page with problem list.

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

Did someone notice? They added the feature to copy the sample test cases of a problem. Thank you Codefroces, keep going!

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

    a bit buggy, but still very wonderful feature

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

How to solve E?

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

    Ternary Search!

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    My solution is this:

    It's easy to prove that we will always pick the max element in the sequence, and then we can ternary search for which prefix should we use.

    Hope I won't FST. (UPD: AC in system test)

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

      It can be done faster: notice that if we pick new max element, amount of elements in answer can't decrease, so we can use 2-pointer algorithm

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

        Great idea, I didn't found that in the contest, lol.

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

      Why ternary? I'm fine with binary search:)

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

        My implementation is doing binary search on the slope.

        However, I am used to call it ternary search because I'm ternary search on the value.

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

      How can we update prefix' sum fast?

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

        Things are given in non decreasing way, so we can simply maintain prefix' sum like this:

        int x; cin >> x;
        pre_sum[n] = pre_sum[n-1]+x;
        n += 1;
        
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Is n the size of multiset?

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

            yes(maybe size of multiset+1), my bad

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

          Omg, dude. I've just looked through the statement and noticed that:

          1 — Add a positive integer to S, the newly added integer is not less than ANY number in it.

          During a contest I thought that the newly added integer is not less than minimum number in it.......

          Now I understood how easy the problem is :(((

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

      I don't see why it's true that we always pick the max element. Also why is there only a single peak for the prefixes?

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

        I figured out why there must be one peak. But still don't see how it's always optimal to pick the overall max.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
          Rev. 2   Vote: I like it +3 Vote: I do not like it

          Let’s assume that we have an optimal choice, where max element is m1 and sum of other elements is S.

          So we can conclude that (M is the max element in the original set)

          nm1 - S + m1 ≥ nM - S + M

          m1(n + 1) ≥ M(n + 1)

          m1 ≥ M

          We know that nothing could greater than M, so m1 must be M

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

            I still don't see it. For m1 it's possible that the optimal choices for S and n are different from the optimal choices for M. (so we can't assume that the S and n on the left side are the same as the S and n on the right)

            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
              Rev. 3   Vote: I like it +5 Vote: I do not like it

              m1, S and n is optimal, so any subset won’t greater than it.Then, I simply replace m1 with M trying to get another subset, but we can prove that it’s the same subset containing m1

  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    You needn't use binary search or ternary search. You can first choose the biggest number, and then choose some small numbers to make the average value as small as possible. If you use C++, you can use priority_queue. (upd. AC in system test)

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

      Thanks , your solution was helpful . pity that i missed the trick during contest

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

      You don't need a priority_queue, too. You can just use an pointer pointing the last element you choose. (This one)

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

How to solve F?

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

    Wondering too.

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

      Just a DP with segment tree is ok. dpi, j stands for the minimum times of flipping, if the face now is cooked j seconds at the end of interval i (i.e. ri).

      It's obvious that we don't need to flip more than two times in an interval. So just consider how long every face get fried, this yields a Θ (n2·k) dp.

      Notice that the points that a state affects is always an interval, so we can use a segment tree with interval-minimum modify and single-point query(or single-point modify and interval-minimum query).

      This yields a solution, which suits the time limit. (Actually it runs very fast, because there are lots of useless states in the dp, ignoring these can make this solution run in about 200ms)

      Hope this will help.

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

        Sorry, what's minimum times meant for? It's time for what?

        我怕我英文說得不好,這裡用中文寫一下我的問題:可不可以跟我解釋一下反轉魚的最小時間(也就是DP的意義)是什麼,我的理解他是j,可是這就很奇怪了

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

          Sorry, the time means the number of operations. (I don't know a better explanation) It doesn't mean the time when you flip it.

          我怕我英文說的不好,這裡用中文回答一下你的問題:DP的意義是翻轉魚的最小次數,不是時間。英語中time做不可數名詞的時候是時間,可數的時候是次數(可能還有其他用法)。j是當前被烤的那一面,被烤的時間。dp就是說,考慮了前i個區間,被烤的那一面烤了j秒,所需要的最小翻轉次數。

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

            Oh!!!! Great Thanks.

            My English is so poor, I didn't notice the 's' after "time".

            Thanks for your wonderful explanation.

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it +6 Vote: I do not like it

      An alternative solution:

      Still, use dynamic programming, and dp[i][j] stands for stands for the minimum times of flipping, if the face now is cooked j seconds at the end of interval i.

      It's easy to get dp[i][j] = min(dp[i — 1][j — r[i] + r[i — 1]], min(all elements within dp[i — 1][(j — r[i] + r[i — 1]) ... (j — l[i] + r[i — 1])]) + 2, min(all elements within dp[i — 1][(r[i — 1] — j)...(r[i — 1] + r[i] — l[i] — j)]) + 1).

      Notice that: 1. dp[i — 1][(j — r[i] + r[i — 1]) ... (j — l[i] + r[i — 1])] is an interval. 2. As long as j0 < j1, (j0 — r[i] + r[i — 1]) <= (j1 — r[i] + r[i — 1]) and (j0 — l[i] + r[i — 1]) <= (j1 — l[i] + r[i — 1]) (Either of the terminals of the interval 0 is on the left of the corresponding terminal of the interval 1).

      So it's not hard to see that two pointers + deque trick can be used to optimalize this algorithm.

      More detailed: 35414333

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

    Try to use the fact that in each l[i] to r[i],whatever possible can be achieved with atmost two flips. So use seg tree(or sparse table or multiset) to update dp values of each level based on previous level,
    Now we need to find what all states contribute to i using len length segment we can get from i+len%2,i-len%2,i+2+len%2,i-2-len%2, and so on till within limits. So segment tree on odd and even positions should be maintained.
    My solution took 2500ms but some solutions took 61ms. So I believe some other nice way exist.Can someone explain???

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

      you can update the dp in O(N) using a deque,so it becomes O(N * K)

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

Hope that I handle the output criteria of C more careful. Half an hour wasted with 4 wrong submissions because of the mistake.

Anyway, the problems and pretests are good. Thanks :D

P/s: Is problem E solvable with a greedy approach and two (but technically one)-pointer(s)?

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

    I have written such solution in E and it have passed pretests

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

      Same with mine. However I feel quite uncertain — like Is it that easy, or there is a trap, or it was just me thinking that the problem is easy?.

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

        I am quite confident that it is a solution, even if mine will fail sys.tests, cause I am bad at coding without bugs :D

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

          Well just give yourself a faith. Good luck. ;)

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

    Yeah I wrote such a solution and it passed system tests. There is a proof sort of for it.

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

      Can you elaborate the proof? ;)

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

        Yeah. Initially when you consider adding all occurrences of a number and you find the difference between the current and the previous one, and if it is positive then you can take that number into account.

        Consider n/sum — (n+occ*ai)/(sum+occ)

        If difference is -ve you can stop.It is beacuse:

        a/b<(a+occ*x)/(b+occ) for all x>1

        Hence the greedy approach works.

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

          It's clear enough ;) also by reading this I know that my thought during contest time was equivalent ;)

          Thanks! :D

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

Was F just dp but instead of having an O(n) transition you change it to O(1) by choosing whether or not to flip at some time (if valid) and return the number of seconds one side is cooked for (and then keep the minimum number of moves in a different dp table)?

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

What's pretest 5 in problem C, if someone was stuck there?

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    I think pretest 5 involved the wraparound condition. Where people of last x timezones and first f-s-x timezones participated Edit: f-s-x, not s-f-x

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

    I think is something like that:

    Input: 3 3 1 5 1 3

    Output: 2

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

no chances for problem hack a and b...."pretty straightforward"

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

Any idea what was the pretest 5 in C??

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

I solved E literally 2 seconds after the contest got over :(

I hope it doesn't get accepted when I submit later.

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

    I solved that 5 minutes after the contest lol

    Don't feel upset if it gets accepted, though. Whether or not we are able to solve a problem is more important than "the ratings we could've gotten," in my opinion.

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

When I realize that only one digit '1' needed to be changed to '0' in the code to get AC...

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

problem E would have been a much better problem had the numbers been not in increasing order.

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

    How to solve it? Use some Data Structure to maintain it?

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it

      The only way I can think of is binary search +segment tree

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

        Maybe some kinda ternary search tree?

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

      binary search and Prefix And,I thinnk (前缀和加二分) (倍增法也可以)

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

    There are data structures which allow you to emulate an array with the possibility of insertion in the middle (complexity changes to O(logn) instead of O(1)). Treaps are an example of such a structure. So the problem wouldn't have changed much. Just had to use a data structure instead of an ordinary array.

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

    whoa, I totally didn't notice that numbers were given in increasing order. I overkilled my solution :')

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

      same :D so during contest I implemented ternary search + segment tree but time wasn't enough :D

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

Does failing a pretest during the contest affect your rating? I've looked through contest rules etc couldn't see that part discussed.

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

    I don't get exactly what you meant, but this is what I think.

    If you haven't submitted any solutions, and then you submitted a "WA/TLE/etc. at pretest X", your rating would start to be affected, since from this point you're set as really participated in the contest.

    If not, then it's similar to any failed submissions — just a minus 50 points of penalty.

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

      Apologies, I see what you mean the question wasn't clear enough.

      That makes sense. Is there a difference in the penalty between a "WA/TLE/etc. at pretest X" and failing on system testing? Or are they both just considered a failed submission -50 points?

      Thanks for the reply.

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

        Well, technically, they both mean -50. But that penalty is considered only when you managed to have a correct solution after.

        And in this case, system test failures are assured to not gaining or decreasing your points at all (since you have no chance to re-submit oficially and get points).

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

          Oh I see! I think this is what I was missing. I thought the penalty was -50 from your overall points for the contest, but it is a penalty on the total points that you can gain from submitting the correct solution for that particular question.

          Thanks Akikaze

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

WA in D(pretest 6). can anyone check whats the problem?? link to my solution of Problem D

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

    Using this test case

    3
    aaa
    bcc
    

    your code gives an incorrect answer. I'm not sure what's wrong though.

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

    return dfs(graph[i][j], fd); This line of code gives you the error. You are not considering all the adjacent nodes and just returning the value from the first adj node you visit. Eg. the graph consisits of: (a, b) (a, c) if you search for a c again it would return false as first 'b' is visited in adjacency list of 'a' and thus it returns false

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

Light-speed System test. Amazing!!!!

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

what could have been the pretest 4 for problem C?

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

    I failed on that one too (several times). From my observations, it's the first test with s>1

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

Before the announcement on B, I submitted B and locked it.

For any case where we can not take any box, I printed -1 0 because I have no idea what to print in such case as the question is unclear.

But my solution failed in System Test.

This should be got AC because, at first the statement was not clear.

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

    Your solution probably failed somewhere else. My code also printed 1 0 in case of using no box and I have got an AC.

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

    Printed a random number too.Luckily got hacked after which i noticed that it should be a valid index 1<=i<=n .

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

    I think that was clear even without the announcement. It's technically not different from any other case.

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

      but, what is the meaning of taking zero box of a specific type? nothing logical here before the announcement!

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

The fastest system testing ever!

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

For D, was there a better method than finding the edges of the minimum spanning forest of the graph?

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

    You can find the connected components of the letters. In each component, all letters have to become the same. So a single DFS or BFS is enough

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

    dsu p[26]

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

Worst pretest ever!!

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

After how much time of the system testing can we submit the solutions in Practice? Cant now

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

How to solve C?

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

    I used a sliding window kind of approach.Passed the pretests but my solution failed on last system test due to silly mistake. It was just because of using < instead of <=.

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

      I also thought of the same solution as you but just couldnt implement it properly :(

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

What's wrong with my solution of C?

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

    cant see ur sol. post here or give another link.

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

    For N timezones : 1, 2, ... N, and contest length = 4.

    We may end up with the best answer by letting these timezones participate {N-1, N, 1, 2}

    Also, answer should be in range [1, N]

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

    an6285 what's wrong with my approach?

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

something going wrong in test case 20 in the problem B.

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

    I got WA in test case 20 because I used "%d" instead of "%lld" for long long in scanf() function

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

When will the contest be available for virtual participation?

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

Can anyone prove this? 35412837

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

What is pretest 13 of problem A?

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

As its not possible to view the test cases currently did any one else get a runtime error in test case 19 of B? If yes then do you know why?

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

    I managed to hack a few solutions by forcing RE with the following tests:

    19999999999999 1
    362143000000
    

    and

    3 1
    4
    

    For the first case the typical mistake is that maxValue is initialized to INT_MAX or LONG_MAX instead of LLONG_MAX or the equivalent, which is >=n.

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

why cant we submit the solutions to the problems now??

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

is this contest is rated?

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

System test is finished and still we can't submit ?!

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

    We probably need to wait until yesterday's educational round finishes its testing.

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

What would happen if a participant with rating above 1900 participates in div2 contest? Does it effect his/her rating ?

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

Can someone please post the questions asked in the Nizhny Novgorod Olympiad, that this contest was based on ?

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

    Problems were same as of Codeforces Round #464 (Div. 2).

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

      It is written that the problems are not identical in the announcement thread.

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

    The problems are in Russian, so it won't work if I just post them. Let's go through problems of Codeforces Round:

    • A: prepared specially for the round,
    • B, C, D: same as on the olympiad,
    • E: on the olympiad time limit was 1 second.
    • F: on the olympiad the constraint on n was 500 000.
    • there was one more easy problem on the olympiad.
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much for your reply !

      Can you tell what the easy problem was ?

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

      So why in the Codeforces round, the constraint on k of problem F was 100, but in the test data it never exceeded 20? I think if it became 100, a lot of solutions will get TLE(but mine will not :P). Can you explain it a little bit? Is it a bug or a feature? Thx a lot.

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

        Why will nklogn solutions get TLE? The time_limit is enough for nklogn when k is 100.

        but.. I still don't know why my O(nk^2 log32 /64) solution can pass the testcase within 62ms.

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

          But the segment tree runs a little bit slow... Those who runs more than 1s will likely get TLE, actually there are a lot of them.

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

"The round is based on XIV Nizhny Novgorod Olympiad in Informatics for high school students named after V. D. Lelyukh, which will take place on Saturday in Nizhny Novgorod."

Wow, there is an Olympiad for high school students that are all named after V. D. Lelyukh? That's amazing!

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

What's wrong with my code of problem A?

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

    if (n==2){ cout<<"NO"<<endl; } probably, i printed YES for that case.

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

      There have to be "NO", triangle with two elements can't exist

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

        my comment was incorrect.

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

          your solution is right, it works correctly with two elements. And remember that plane can't love himself:)

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

      It's supposed to be NO. I think the mistake is because for the case n=2, the line NO would be printed twice.

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

    3 1 2 2 try this input data

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

      Since the problem states that f_i != i, I don't think that would be a valid test case.

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

    You should return 0 from the if condition after printing NO.

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

Feeling sad my C failed on the last System test :( By the way nice contest.

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

It's 13:45 UTC now and we still can't submit solutions.

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

My B is hacked :( ...

can anyone give me some test case...

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

Apparently the succesful hacks have not been added to the final system tests. What is the reason for this?

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

    Hacks are only added to final system tests in Educational Rounds.

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

Enable upsolving please!

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

Why is the right answer 4 in fourth C test? 10 7171 2280 6982 9126 9490 2598 569 6744 5754 1855 7 9 If we begin round at 4, only participants from 4, 5 and 7 time zones take part in it, and if we begin round at 10, participants from 1, 8 and 9 time zones take part, so in first case we have 9126+9490+569=19185 participants, and in second case 7171+6744+5754=19669 participants. ???

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

    The time zones which has time f will not participate. It's said in the problem statement.

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

      But I consider it. In first case 6th zone has f time, and in second one 10th zone has it.

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

        So why does time zone 7 take part in it in the first case? !

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

          The round start at 10 and finish at 1. It starts later than 7, finish earlier than 9 and it doesn't start at 9. What's wrong?

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

For E Can we pick max and min element get their average and then pick all less elements than Average?

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

    I don't think so. As you add more small elements the overall average decreases. At a certain point adding new elements will start to increase the average, even if it's less than the original average.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I solved it using this idea but changing the average as I insert the elements... This way is very simple and doesn't need ternary/binary search.

    Take a look: my submission

    We always use the max and a prefix of the elements, and this prefix always increases, so it's very easy.

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

When will the ratings be updated?

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

    I have a tremendous fear of kidney stones. Why on earth have you chosen such a handle, may I ask??

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

      Because I actually have them in my kidney.

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

        Well, I don't understand why you would "love" them, but hope you stay safe!

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

How to solve C?Anyone please explain .

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

    Let's find the max sum on each segment with the size of (f-s). First segment will be s...f-1, second s-1...f-2.

    Ok. But there is 1 detail: the beginning of the segment can be in the end of our array and the end of it can be in the beginning of our array.

    I hope my code'll help you to deal with it

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

      10

      7171 2280 6982 9126 9490 2598 569 6744 5754 1855

      7 9 Why here answer is 4? Please explain :)

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

    This problem can be solved in O(n). Initialize an array with value 0 of size n. Consider 1st timeline as the starting point and can be represented as 1 2 3 4 ... n. While, 2nd timezone can be represented as 2 3 4 ... n 1 (wrt to 1st timezone) and so on... Replace the indices with the participants. And then do an array addition from s to f-1 for each timezone in the initial array. The index corresponding to max value is the answer.

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

Before this round my rating in div 2 But after by education round my rating was 1954. Is calculate my rating this round?

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

    Oh no. Now my rating 1816 :(

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

    I think rating has been updated without considering performance of educational round. This should be fixed.

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

In problem C, why this test case is 4 and not 5

10
7171 2280 6982 9126 9490 2598 569 6744 5754 1855
7 9
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because (9126 + 9490) is maximum

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

      Explain,he knows that is maximum.

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 4   Vote: I like it +1 Vote: I do not like it
         4    5    6    7    8    9   10   1    2    3
        7171 2280 6982 9126 9490 2598 569 6744 5754 1855
         N    N    N    Y    Y    N    N   N    N    N
        

        I think he can understand

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

          Thank you brother :) got it properly . But when there are many answers,how do i select the best? Upd : Solved

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

    Obviously the maximum is 9126+9490. So we want the contest to start at 7 hours in the region with 9126 to cover the two. Now we need to find at what hour it will start in the first timezone.

    Timezone / People / Hour
    1 7171 4 <-
    2 2280 5
    3 6982 6
    4 9126 7
    5 9490 8
    
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In 8th hour,answer is being maximum which is 5 in timezone.So,why the answer is 4 ?

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

        If we start when it is 5 in the first zone, we will actually get 9490 + 2598 which is not maximum. Because in the zone with 9126 it will be only 6 hours the time which is too early to participate (<s)

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

Some people who became div-1 in the Educational round was rated in this round. If you go to the rating changes of this round you can see some purple guys got their rating updated which shouldn't happen as this round is for div-2. This should be fixed.

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

    List:

    MysteryGuy2, RCG, Timsel, WORLD_OF_TANKS, winner, andrew, faustaadp, furys, Chefer, levapnilirbuz, smusmu, killer_god, Trote_w, hands_yhy, Sugardorj, Gorix, win11905, kzyKT

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

35423572 can someone debug this solution for problem C?

EDIT : My approach for the problem: I made the array of twice the size so that round or wrapping condition for the end & beginning timezones is considered. I calculated prefix sum for 2*n +1 size array. Then, I searched for maximum diffrence of (a[i+f-s-1] — a[i]). Then calculated corresponding value for the time in the first time zone.

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

    ayu111, I had this exact problem. In case there are multiple subarrays with same (max)answer, you have to output the one which leads to minimum start time in timezone 1.

    For everyone failing on Pretest 9 of problem C, Try this: 6 1 3 4 1 3 4 1 3 correct ans : 3 your ans : 6

»
4 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

More than 20 Candid Master have there rating change in this Div 2 round.

This should be fixed.

MikeMirzayanov

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

Can someone tell me, what's wrong with my approach in C?

I used range updates to add a[i] to (s + i — 1 , p — 3 + i), and then checked the maximum.

Here's my code.

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

    The only thing you needed was to find the segment with max sum in.

    First segment is [s,f). Second — [s-1,f-1); If segment number two has the max sum, answer is two. If segment 3 has the max sum, answer is three, and so on.

    Look through my solution. At least it looks easier than yours ;)

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

In problem A, why starting the loop from 0 instead of 1 gives a wrong answer !?

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

    If you start from 0 you should read a[i] and then decrease it (a[i]--).

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

      yeah I know, but I don't understand why what's the difference

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

        "There are n planes on Earth, numbered from 1 to n, and the plane with number i likes the plane with number fi," Here's the sample:

        3

        3 1 2

        You consider that person number 0 likes person number 3. But if you start from 0 there is no person #3. (a[0],a[1],a[2])

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

Can somebody explain what's wrong with my solution of C? 35398638

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

Will never use cin and cout in my life again! Problem E. :/

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

When the universe just sided with you..

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

    ??What is the difference between Educational Codeforces Round and Codeforces Round?

    I always thought Educational Codeforces Round wouldn't change the rating......

    so after Educational Codeforces Round24 i didn't take part in it any more

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

Suddenly became frozen when I realized my E got WA just because of the precision problem:

35399314

UPD: get accepted after adding "fixed" and "setprecision(10)" : 35434902

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

    That's why I always write cin.precision(25); in any task with floating numbers.

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

What's the wrong with problem F? The problem statement shows the maximum k is 100 that I think the algorithm can't solve this problem, but among all the testdata the maximum k is 20.

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

There are many cheat passed D

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

Excuse me , but where is the tutorial of Codeforces Round #464 Div.2 ? Can someone give me a link?

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

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

What is wrong with my solution (Problem C)?

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

Where is the editorial? I look forward to getting the solution of problem E

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

    I think you can understand the other people's code. There are many ways to solve the problem.

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

    Yeah,there is already 24 hours and we still can't find any editorial.

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

Why does problem 939E - Максимизируй! have to give numbers in non-decreasing order? This makes it much easier than usual.

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

    I didn't see this phrase so decided not try to solve this in 20 minutes before ending :P

    i am not used to E and D tasks easier (in some way) than C...

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

Excuse me but editorial?

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

editorial please?

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

24 hours passed,but we still don't have the editorial.

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

Editorial ?

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

may be editorial?

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

Editorial?

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

Editorial please?