mesanu's blog

Codeforces Round #806 (Div. 4)
By mesanu, history, 2 years ago, In English

Hello Codeforces!

SlavicG, flamestorm, MikeMirzayanov and I want to invite you to Codeforces Round 806 (Div. 4).

It starts on Jul/12/2022 17:35 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

  • 5-8 tasks;
  • ICPC rules with a penalty of 10 minutes for an incorrect submission;
  • 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
  • after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
  • by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

Many thanks to the testers: TimDee, Gheal, Max_Calincu, qwexd, _Vanilla_,sandry24, jampm, haochenkang, tibinyte, Etherite.

We suggest reading all of the problems and hope you will find them interesting!

Good Luck!

Update: Editorial

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

Comments Comments (194)
| Write comment?
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

As a tester, I tested.

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

No more div4 please!

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

    Why

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

      In the end, it's only their time being "wasted". Also, it makes some people happy. Why do you want to infringe on that?

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

        Which of your eye have seen that I infringe on that, left or right?

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

          For Christ's sake, don't do semantics on me.

          I specifically said why would you want to, indicating the fact that it appears to be a desire of yours to discontinue this brand, not a thing you already did (the latter indicating that you would have infringed, the former describes your intention to infringe). My formulation was correct, as much as your comment stated: "(*Please*-- It hurts to be polite?), no more div4 please!", indicating a request, as per some beliefs of yours I do not yet understand, that, if taken seriously, would eventually lead to the discontinuation of this sort of rounds. As such, and I repeat, it clearly shows how it is your intention to do so, but not that, quote "[You] infringe on that,..".

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

    No more your comments please!

    barbarian_clash_of_clans

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

Thanks to System testing of last Div3 I will be giving this round :)

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

Offtopic:

It would be good if there was an option at contest standings,to check country-wise standings. Like,I will select a country,it will show the ranking of all people only from that exact country.What do you think?

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

As a noob, Div 4 is the only time i solve at least 5 problems

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

As the first tester in post, I strongly recommend this round to all participants, even high rated users can find harder problems interesting, and beginners will find all problems interesting and relevant =)

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

why there isn't div 5 :)

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

I wish you all good luck.

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

tested

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

Waiting for specialist to comment: Finally my first unrated round ;-;

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

Hope for some positive delta

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

Excited, I hope it won't have repeated problems like the last round.

Wish all the rated participants high rating!!!

Wish all the participants high ranks!!!

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

deleted

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

my code 163576300 was accepted and didn't show up "time limit exceed on test 19" while the contest was running. Then why this happened to me after the final testing?

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

      got it thanks. But I wonder why they didn't show the error while the contest was running. If they showed the error before instead of showing accepted then I could have fixed the code.

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

As a tester, I recommend you to participate. The problems are really good!

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

    Dear KrowSavcik,

    This the first time I am participating in a round, I am a beginner, the problems which I am solving is between 800 : 1000, I want to know :

    1- Div 4 is good to me or not? 2- If it's not good to me what Div shall I participate?

    Thanks

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

      Even though I am not KrowSavcik, I can tell you that Div.4 is the best division for you as a beginner (like me). It has the easiest problems among Div.4, Div.3, Div.2, and Div.1. You will see that you can solve more problems in some previous Div.4 round than in some Div.2 round. As the division number is decreasing, problems difficulty is increasing, and 4 is the highest possible division number.

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

        Thanks

        I saw your reply after the contest, I solved 3 problems and the fourth is correct but the I get Time limit, and one I finished after the contest finished some minutes,

        but really it was a good contest, in the future I have to manage the time.

        Hope all will keep continue in this good things

        Best wish for all.

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

    why downvote ?

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

hope to turn green

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

As a non-VIP tester, I non-VIP tested :(

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

Div.

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

As a tester, the problems were very interesting and educational. One of the best Div. 4 by far. Orz SlavicG.

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

I registered in this contest before the rating change of the last round i.e when I was under 1400. So, will this round be rated for me? Somebody, please confirm.

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

First unrated Div.4 for me, yay

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

as a pupil, i hope that this will be my last rated div. 4

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

Is there any dynamic-programming or greedy expected in div. 4?

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

    greedy will almost surely show up.

    DP might provide alternative solution paths to some problems, but I don't believe that it's suitable as a necessary tool to solve a div. 4 problem.

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

Nice

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

Is there any interactive problem?

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

Thanks for creating div 4 contests

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

Finally my first unrated round lol

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

my first unrated contest !

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

Im hoping to reach pupil, good luck everyone!

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

As an OOC contestant, I OOC registered.

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

As a tester, I tested, and I have to tell u this contest is great!

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

My top 5 finish was ruined by having to wait 2 minutes to open the problems and submit A

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

My rating is 1455 and I'm still showing a contestant int this round. Please fix this

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

    I think this is because you were under 1400 when you registered for the contest. It marked this contest as rated for you then.

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

Hurrah! Mission A.K. accomplished!

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

My first rated round which i Aked.

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

Can't believe I'm that dumb, F was so simple. I hope someone hacks it.

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

I can see some contestants which did not have any rating and this is their first contest and they are ranked in top 10 or so. What happens to those contestants?

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

    They'll not be rated as it is written in the announcement blog that the participant must have participated in at least 5 rated rounds to have this round rated for them!

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

      They will be rated. They just won't be in the official standing table.

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

MikeMirzayanov, 3mara is telling you #unrated_plz_mike_im_sorry_ill_join_next_time.

So please make it unrated :)

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

Informing everyone in advance that G will be having a lot of hacks. My simple n^2 passed instead of prefix I used simple iteration and still passed lol.

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

    Thanks for letting me know it's hackable. It's time to be a hacker ^_^

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

Lot of people created new accounts just to take part in this round like meyi_will_win_NOI2023, wesaco... Here I mentioned just those in top 20. Do something about it, MikeMirzayanov.

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

    I don't think it illegal?

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

      It isn't illegal, but if it's for example tourist with his new account or any other participant whose rating is higher than 1400 (contest isn't rated for him), then I'm getting less rating points than I should.

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

        Yes, I agree with you, but there are so many new accounts created like this, what can we do? How can you judge if an account is specially created like this?

        Sadly, this cannot be controlled.

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

        Only trusted users can be listed in official standings, if tourist create a new account, he needs to participate at least 5 times to be included in official, otherwise he will not be included in ratings calculation. If he behave normally in his new account, he will reach red after 5 contests. The only situation that you are defeated by "fake tourist" account in div 4 is that he crashed the first five contests on purpose.

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

          untrusted participants whose rating <1400 is rated.

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

    Of course most of them are smurf, but some might be legit strong participants that join codeforces for the 1st time, so it's very hard to deal with this problem. Btw it also happens in higher div contest

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

Any hints for problem D?

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

    First we store all string in a map, then for each string $$$s_i$$$ with length $$$k$$$ there are at most $$$k-1$$$ way to concatenate it into 2 string, and if both string exist in the map the answer is yes

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

Please explain me how to solve problem E 1703E - Mirror Grid

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

    Each field is in one class together with the other fields that get rotated onto the position of it. For most fields that are 3 other fields. The center field of an odd n grid is allone.

    Each of these classes can be made same by 0,1 or 2 flips.

    So, we need to count the 1s in the 4 fields of each class. Thatfor we can iterate one quarter of the grid, and foreach such cell calc the position of the three other cells.

    But we need to be carefull here what is a "quarter". For me it worked fine to iterate the rows from 0 to (n+1)/2, and the col from 0 to n/2.

    That is, in an even size grid exactly a quarter, in an odd sized grid the rows up to including the center row, and the cols up to, but not including the center col. Also skip the center cell.

    Then the rotation is in zero based indexing: $$$(x'=y)$$$ and $$$y'=n-1-x$$$

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

Can anyone give hints for G?

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

    If a number is Ai, how many different values can that ultimately take? What does it depend on? Consider the question "what is the maximum score up to index i, such that I have used j bad keys so far?"

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

    dp, the time complexity is n * log (1e9)

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

      There is no need to use dp.

      Greedy Observation

      My Solution : 163889601

      → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    Hint 1
    Hint 2
    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint
    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    The only hint you need
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      wait, isn't it at most 30?

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

        Yup my mistake

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

        If all a[i]<k we want to use the bad operation n times for sure.

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

          But I think that won't affect the DP state

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

            It will give result 0 and you cannot get that result or better otherwise.

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

What is the motivation behind the problem E?

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

Problem E totally hanged my brain.Otherwise I would become specialist today. Damn!

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

    I don't think we have a chance to become specialists untill we solve all including G, so i would say don't feel bad :)

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

    same, so frustrating. Now it's time for us to learn about matrix rotation so this does not happen again

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

HOW TO DO F?

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

    read about ordered_set you need to loop starting from first element if the current element is smaller than its index add number of items in the set smaller than its index to the answer then add the item to the set ps : sorry i ment to add the index of the item to the set i know my english is poor as well as my explanation but feel free to ask for further explanation

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

      I guess their is no need of the ordered set (policy based data structure), the normal set works just insert all pairs {a[i],i} where a[i]<i and iterate on the vector. delete the first value of set until becomes greater than a[i] and just add the size of set to answer

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

AK-ed the contest. D, E, F, and G are the only ones I remember. D was brute force with maps, E was implementation, F was seg tree, and G was a nice greedy (kind of).

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

    F can be done using sets also.

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

      Actually prefix sum is enough, O(n)

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

        how prefix sum working??

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

          We go from left to right. Foreach element we check if a[i]<i, if yes add 1 in our prefix sum.

          Then find foreach element the number at position pre[a[j]-1], that is the count of a[i]<i numbers where a[i]<j.

          163884238

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

    F can be done with binary search

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

    am I the only one who used prefix sums for F lol

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

      I did with prefix sum too :). I saw most of the pro guys used seg tree or BIT.I wonder why they didn't use the easier approach!

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

        To come up with more optimal then current (nlogn) solution take some time, so they went straight to more familiar (nlogn) solution.

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

          Exactly my mental process. I saw that it could be done easily in nlogn with seg tree and decided not to tire my brain out further.

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

why my code for problem G always give WA on test 4 ,my idea is use dp with bitmasks, thanks in advance.

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

I hate when tutorial is posted like two days after the contest.

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

Can someone Explain the TLE for G on my solution. 163933925 I did a recursive memoization dp like recursive knapsack.

UPD- it worked after adding if(factor>=35)return 0; condition

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

Please check my blog, I have some questions. https://mirror.codeforces.com/blog/entry/104782#comments

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

My rating is 1388, and my official ranking in this contest is 1720 (excluding rating>=1400), can I get like +30 rating change from this contest?

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

    most likely you'll be specialist. Good job!

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

I just wonder how more people solved E than F,lol

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

    i had the same question but it turned out its a variant from an already existed problem in geeksforgeeks maybe there are alot pro_googlers xD

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

In dp solution for G, why does it fail when I take max over last column (WA on test 4) and passes when I max over all states? shouldn't the max answer carry to the last column?

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

In G I guess there are several nice ways to solve it. I used following:

Observe that if i divi operations are used, then it is allways optimal to use them on the last i elements. That means, we can build a prefix sum of boxes opened with k-operation, and a postfix sum of boxes openend by divi operation.

Calculation of prefix sum is streigth forward, $$$sum[0..i]-(i*k)$$$

Calculation of postfix sum needs more code. First I thought I can simply calc the sum, and in every step divide by 2, but that does not work out.

So instead I did bit counting the set bits in the postfix, and in each step move the count of each bit one position down. So I can calculate the cost/worth of the postfix in each step by the remaining count of bits.

163908470

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

    I used the same. But is there any proof for "if i divi operations are used, then it is allways optimal to use them on the last i elements" ?

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

      Consider one divi operation. If we use it on the last element, the costs are a[n-1]/2. If we use it on any other element, the costs are higher.

      Then by induction we would choose the second last element for the second divi operation, and so on.

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

Shitty contest, end Div.4!

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

Fuck Div.4

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

Problem G Why does my solution fail test 4 https://ideone.com/FptY9R

ll n , k;
cin >> n >> k;
vector<ll> v(n + 1);
for (int i = 1 ; i <= n ; i++)
    cin >> v[i];
vector<vector<ll>> dp(n + 1, vector<ll> (45));

for (int i = 1 ; i <= n ; i++) {
    dp[i][0] = dp[i-1][0] - k + v[i];
    for (int j = 1 ; j < 40 ; j++) {
        dp[i][j] = max(dp[i-1][j] - k + (v[i] / (1ll << j)) , 
                       dp[i-1][j-1] + (v[i] / (1ll << j)));
    }
}

cout << *max_element(dp[n].begin(), dp[n].end()) << endl;
→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Let's say k is big, and array a is small then after some steps it's always just better to take the bad key (it will add 0). You can just fix this by taking max of dp[i][x] over all array.

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

Another fun div.4 contest! Problem D, E contains a little bit of thinking and problem G is really interesting! The observation that we use good keys at the first i chests is actually not so easy to find.

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

I tried several ways to solve F problem, but I couldn't do it. How should I think about this problem？

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

It seems D: has most hacks

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

    Yeah, but what's the test case? I don't see any scope of TLE in the code.

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

      prolly people using unordered sets/maps

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

        I saw a few codes with map also getting TLE

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

          Some people didn't use break when their map checked two strings that can be successfully combined,so if hackers let strings can let their code check many times,their substr will make them TLE.

          For example: a aa aaa aaaa aaaaa aaaaaa aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa ...

          and the last string will be checked for 7 times but substr is so slow.

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

            Will it make any difference? because there can be test cases with no matches which will be having same complexity.

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

              Can you give an example?I hacked many people in this way and they all used map.

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

          i saw some that used string = string + character instead of string += character

          → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
If you use multiset in D and get FST or hacked by me
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can't hack this one , I did the same solution in the contest and it directly gave TLE in the contest itself .

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

When will be the rating updated?

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

    After 2hr ig............ first time my rating won't get updated xD

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

Nice but underrated contest.

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

    Rating will be updated after sys testing is done.... :)

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

The problems were great but I think the problem E Harder than all

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

I pariticipated in the contest, but it doesn't show up in my profile? My rating is below 1400, so it should have been rated for me? Can anybody explain or am I missing something?

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

    rating usually will be updated few hours after system testing. so you just need to wait for it.

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

      True. However, it's been almost 12 hours after the open hacking phase ended. I presume that there's no way to see if system testing is still ongoing?

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

        System test was ended.You just be patient for the rating changing.

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

Me checking every 5 minutes, if my rating is increased by 0 or rating has not updated till now

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

I really don't get cf's rating system. Mine was less than 1400 and I got downrated solving 3 of them. LOL

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

    It doesn't only depends on number of problems you have solved, it depends on your performance and other's performance including amount of time you took.

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

Why is my rating has decreased by 5 !

I solved 2 problems without any wrongs so what's wrong !?

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

    Rating change depends upon your performance (Rank) in the contest.

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

is it just me or anyone else also noticed that we have received almost half positive rating which was shown on cf predictor

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

consequence for wrong submission ?

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

    10 minutes penalty

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

      No brother, i have submitted 3 times wrong and forth tkme i solved. And got -75.

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

        I believe you are mixing rating points with contest points. The -75 you are referring to is how much your rating changed after the contest. Rating changes are based on your overall performance/rank on the contests. Your performance/rank in contests with ICPC rules, such as this, are based first on how many problems you solved and then on how fast you solved them. An incorrect submission adds 10 minutes to how much time you took to solve a problem, what makes your performance worse, but doesn't quite directly influences your rating change like this. You could have had zero incorrect submissions and yet a negative rating change, because although you didn't get anything wrong you had a bad performance, or you could have had 100 incorrect submissions and yet a positive rating change, because you had a good performance.

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

Why my standing's different from the official standing table than the "friends standings" table?

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

I just wrote this to make number of comments 300 (-_-).

→ Reply