mesanu's blog

Codeforces Round #806 (Div. 4)
By mesanu, history, 22 months 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 (190)
| Write comment?
»
22 months ago, # |
  Vote: I like it +14 Vote: I do not like it

As a tester, I tested.

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

No more div4 please!

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

    Why

    → Reply
    • »
      »
      »
      22 months 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
      • »
        »
        »
        »
        22 months 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
        • »
          »
          »
          »
          »
          22 months 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
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    No more your comments please!

    barbarian_clash_of_clans

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

why there isn't div 5 :)

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

I wish you all good luck.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

tested

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

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

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

Hope for some positive delta

→ Reply
»
22 months 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
»
22 months ago, # |
← Rev. 2   Vote: I like it -23 Vote: I do not like it

deleted

→ Reply
»
22 months 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
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    Spoiler
    Spoiler
    → Reply
    • »
      »
      »
      22 months 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
»
22 months 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
  • »
    »
    22 months 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
    • »
      »
      »
      22 months 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
      • »
        »
        »
        »
        22 months 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
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why downvote ?

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

hope to turn green

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Div.

→ Reply
»
22 months 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
»
22 months 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
»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

First unrated Div.4 for me, yay

→ Reply
»
22 months 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
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

Nice

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any interactive problem?

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

Thanks for creating div 4 contests

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

Finally my first unrated round lol

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

my first unrated contest !

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

Im hoping to reach pupil, good luck everyone!

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As an OOC contestant, I OOC registered.

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

Hurrah! Mission A.K. accomplished!

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

My first rated round which i Aked.

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

    I don't think it illegal?

    → Reply
    • »
      »
      »
      22 months 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
      • »
        »
        »
        »
        22 months 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
      • »
        »
        »
        »
        22 months 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
        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          untrusted participants whose rating <1400 is rated.

          → Reply
  • »
    »
    22 months 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
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Any hints for problem D?

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

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

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

Can anyone give hints for G?

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

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

    → Reply
    • »
      »
      »
      22 months 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
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    Hint 1
    Hint 2
    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint
    → Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    The only hint you need
    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      wait, isn't it at most 30?

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

        Yup my mistake

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

          But I think that won't affect the DP state

          → Reply
          • »
            »
            »
            »
            »
            »
            22 months 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
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint
    → Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What is the motivation behind the problem E?

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

HOW TO DO F?

→ Reply
  • »
    »
    22 months 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
    • »
      »
      »
      22 months 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
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Spoiler
      → Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    Spoiler
    → Reply
»
22 months 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
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    F can be done using sets also.

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

      Actually prefix sum is enough, O(n)

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

        how prefix sum working??

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

    F can be done with binary search

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

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

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Shitty contest, end Div.4!

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Fuck Div.4

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

    Think in terms of binary search

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems D: has most hacks

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

      prolly people using unordered sets/maps

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

        I saw a few codes with map also getting TLE

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

When will be the rating updated?

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

Nice but underrated contest.

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

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

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

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

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

consequence for wrong submission ?

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

    10 minutes penalty

    → Reply
    • »
      »
      »
      22 months 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
      • »
        »
        »
        »
        22 months 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
»
22 months 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
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply