awoo's blog

By awoo, history, 6 months ago, translation, In English

Neapolis University Pafos

Hello Codeforces!

The series of Educational Rounds continues thanks to the support of the Neapolis University Pafos.

On Apr/29/2024 17:35 (Moscow time) Educational Codeforces Round 165 (Rated for Div. 2) will start.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

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

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

Waiting for a good contest!

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

Make this comment most disliked comment in CF

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

    I guess this is one of the most downvoted comments. I wanted someone to nominate me tho :(

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

I hope there will be an interactive problem soon

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

    Usually, I do not find interactive problems in an educational contest. Have you such an example where it happened recently?

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

    If the contest has an interactive problem they should say in the announcement.

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

    I would like to give you a downvote but because we are in the same community take an upvote.

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

Edu time I hope A-E is data structures problems , or 2 of them at least

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

All the best guys :) ;

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

The penalty for each incorrect submission until the submission with a full solution is 10 minutes. what this line means, how penalties are given in this case. I know only -50 for wrong submission is a type of penalty.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    • in Edu rounds the leaderboard is sorted Depending on how many problems you solve there is no score

    • but what if there is 2 people have the same number of problems solve they will sum the times of them and sort it by the person who have less time

    • but if person got 2WA on a problem then AC the sum of time will increase by 20 which will give him bad leaderboard place
»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Hope able to solve ABC

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

I hope I don't get negative delta...

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

I wish high rating to participants

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

Good luck everyone

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

1800 plz!

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

Best of luck everyone.

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

Very long time no see, Educational Codeforces. I wish this contest teach me a lot.

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

pls no guessforces

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

My first Educational round. Hop to get positive delta for everybody.

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

GLHF

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

"I wonder how you folks (BledDest, adedalic, Neon, Roms, awoo) come up with so many tasks. It's like you've been holding Educational Rounds since the invention of sliced bread=)

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

Will the 12-hour hacking part give any additional score? Will it be possible to hack the solutions of your room during the contest?

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

Hope everyone will not get stuck in A, B and C.

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

Please no stupid constructive/guesswork/made sense only to the author type problems like the last two contests.

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

Please,I want to pupil

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

Good luck && have fun!!!

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

It was kinda shitty contest tbh

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

C>>>D. 10 minutes for D and 1hr+(multiple WA) for C.

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

    Isn't C just a standard dp?

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

      ah yes because 2D is standard DP. Someone who actually solved C & D

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

    what logic you apply while solve d ?

    I can not solve c and d !!

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

      C : 2D DP with n and k. Where DP[i][j] is maximum subtracted from sum in first i elements with j operations. DP[i][j] = max ( DP [i-q-1][j-q] for all q between 0 and j).

      D: Sort all for minimizing Alice's cost. Then, look at all items where Alice pays less than what Bob could pay. Store all of Bob's costs in a min heap priority queue. Bob gets k minimal costs for free. answer = max(sum(Bob) excluding top k elements — sum(Alice)).

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

        Thank you bro, I make you my friend! I star on your profile in order to add in my friend list. To be honest, I am not good in heap priority queue and dp. if you have good material to study then please share it with me. my mail id is : [email protected] my linkedin is : https://www.linkedin.com/in/jayambe

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

    How could you solve greedy problem more easily than the DP problem ?

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

    do you know how to find the testcase which went wrong? as if there are many testcases it is not shown in the submission

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

can C be treated like the stack of plates problem where you need to take the top plate before taking any plate under it , and you can only take k plates in total ?

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

D <<< C

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

    If you don't mind me asking, what was the solution for D?

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

      Well, firstly sort things by Bobs cost, if equal sort it in decreasing order by Alice cost. Let's say we want to buy first $$$t$$$ things. For all of them we will get max(0, $$$b_i-a_i$$$), if we will additionally buy any $$$k$$$ things (so Bob will choose them). We just need to maintain sum of $$$k$$$ smallest numbers of $$$a_i$$$ to the right of $$$t$$$ and brute-force $$$t$$$ from left to right.

      Maybe it's a little bit messy, but this is what i have...

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

    C was easy DP, maybe a little tricky to implement.

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

      DP itself was not intuitive for me, as we are able to replace $$$a_i$$$ not only with $$$a_{i-1}$$$, but also with $$$a_{i+1}$$$.

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

        Maybe it's easier if you think about the operation as "choose a subarray [l,r] and replace all elements with the subarray minimum".

        Then dp[i][j] = minimum sum of subarray [0,j] after applying i operations, and you can iterate over the size of the subarray including the element j (can be 1, 2... k).

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

          yeah, that is the observation I needed to solve this.

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

      It's a dime in dozen occasion, lol. I usually manage to solve more complicated problems, rather than easier ones. IDK why rly...

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

orz

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

Aaaaaaa, I couldn't debug C in time.

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

why my solution is failing for C ?

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

    It's hard to use greedy for C, or even impossible (I actually think about a lot of ways to use greedy but I found lots of counter examples either, so just use DP is a better approach).

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

      Hello DuongForeverAlone sensei, how are you? and plz Can you tell me what is the best way to start DP, so that i can cover all the standard problems of it? and from where? Answer my question Greedily sensei ;)

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

        Just do it LOL. I have no idea what is the best way to start. Until now there are much topics in DP I haven't covered yet (some DP optimization techniques for example). Heading to codeforces, leetcode, cses, spoj, ... or any other online judges you know and sort to do DP.

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

    I tried difference (Greedy) too, in quite different ways, making array of differences, modifying original array and difference array on each iteration, counting max difference and keep on deleting from the sum. But there is one thing greedy doesn't account for ie repetition in similar differences. Example --> n = 4 k = 2, a = [4, 8, 5, 1] the differences are 4, 3, 4. You chose the first 4 to change, new array is [4, 4, 5, 1] next you choose last 4. final array --> [4, 4, 1, 1], sum = 10 Now in case you choose last 4 to change --> [4, 8, 1, 1] now you choose the difference 7 which gives --> [4, 1, 1, 1], sum = 7.

    I haven't practiced DP but as far as I can see from solutions, people tend to be doing similar thing using DP ie a 2D array to keep track of all changes. (I might be wrong on the DP logic since idk how to use DP). But the problem in greedy you faced is same as mine and I presume many more got stuck here.

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

Good contest, I liked the problems.

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

Idea for D?

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

    Hint: Think in reverse operation order. Suppose you include N elements and want to remove one, what's the optimal strategy for Alice?

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

    The model approach is the following one:

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

      ah nice explanation, thanks broski

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

      Why Bob will take for free most expensive for him, if his goal is to minimize Alice profit? I sorted by $$$b_i-a_i$$$ and got different answer on pretests.

      Upd: Think I got it, Alice already paid for entire subset, so it makes sense to sort by $$$b_i$$$

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

      I sorted the lists based on the decreasing differences in values and it WA on test 3. Basically sorted a list of pairs $$$(b[i]-a[i], i)$$$. Why does this idea fail?

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

      I believe I have a more "elegant" greedy solution which utilizes different observations so I'd like to share it.

      First observe that if Alice selects fixed $$$M$$$ elements, Bob will take the $$$K$$$ with the largest sum of $$$b_i$$$.

      Next, observe that Alice never wants to take an element if $$$a_i>b_i$$$. Just consider both cases (Bob takes this element and Bob does not take it) and the answer never becomes worse if Alice excludes it.

      Now that we know this, suppose that Alice chooses all elements such that $$$a_i<=b_i$$$, let the count of such elements be $$$l$$$. Let's denote the elements selected by Bob by $$$(a_1,b_1),(a_2,b_2),...,(a_k,b_k)$$$ and the remaining ones by $$$(a_{k+1},b_{k+1}),(a_{k+2},b_{k+2}),...,(a_l,b_l)$$$. We know the total sum for this choice, because Bob chooses greedily the $$$K$$$ largest $$$b_i$$$'s.

      Now what happens if Alice wants to choose $$$l-1$$$ elements?

      We never want to remove an element that is not already chosen by Bob, because it will just reduce the total sum. If we remove an element $$$(a_p,b_p)$$$ that is chosen by Bob, the total sum increases by $$$a_p$$$ and it can trivially be proved that we can never add $$$b_p$$$ to our total sum in the future by performing removals. So it's always optimal to remove the element with the largest $$$a_p$$$ and instead of it insert the one with the largest $$$b_q$$$ such that $$$(a_q,b_q)$$$ is not present in Bob's set.

      We can easily simulate this process using two multisets.

      I didn't write the proof in a formal way here, because it would be lengthy, but one can derive it if they want.

      Here's my submission 258749293

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

    If Alice chooses some subset of elements, then Bob will pick the $$$K$$$ elements with the highest values of $$$B_i$$$. If we sort the items by $$$B_i$$$, then this just means Bob will always pick the rightmost $$$K$$$ elements in any subset. Therefore, our array will become split into 2 partitions: the left partition's elements go to Alice, and $$$K$$$ of the elements in the right partition go to Bob (we can choose the ones with lowest $$$B_i$$$).

    We can do the following: Iterate over the size of the right partition from size $$$K$$$ to size $$$N$$$, and maintain the sum of the smallest $$$K$$$ values of $$$B_i$$$ using a multiset. We then calculate Alice's profit as $$$\max(0, B_i-A_i)$$$ for all elements $$$i$$$ in the left partition, which we maintain with a prefix sum array.

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

      I skip the problem because I thoug the profit can be negative and that's why I never understood the 3 example, that should be specified in the statement. Upd: now i see you can buy an empty set :(.

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

        Was buying empty set not mentioned during contest?

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

Best contest ever!!! I very much enjoyed it :)

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

great contest, even tho idk how greedy works in D

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

I bruteforced sorting criteria for D and resulted in a +7 AC... what a way to live... XD

Anyway, anyone can prove the validity of D? My (greedy) approach is to sort everything, first on Alice's buying cost in increasing order, then Alice's theoretical profit (assuming Bob doesn't take anything for free) in decreasing order.

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

    Let's think of a strategy for Bob. If I take s elements (s>k) then he will choose s-k elements with the minimum b. That's obviously true because sum of a is fixed and to minimize the profit Bob will choose the smallest bs. Now, I'm Alice and I know that. Then I wiill check each b. If I fix some b[i], then for all b[j] such that j>i I will choose minimum k as from them. I know that since they are k and Bob will choose minimum bs, he will not choose from them. So now remains the elements in the prefix of i. Any element I will choose in this prefix, Bob will choose it too. So I want all positive profits in this prefix. I'm not sure if this is kind of a proof, but this was my though process.

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

can someone please tell why is this giving WA on 3 is there any logic error or bug

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

    I also had WA on 3, does someone have a counter example which I may have overlooked?

    "wrong answer 14th numbers differ — expected: '14', found: '13'"

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

    try for this test case:

    4 1

    1 1 3 9

    3 4 5 15

    here you will get 0 but answer is 2

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

TFW you get a WA a couple minutes before the contest ends and out of supreme luck, you unknowingly click "Mobile Version" on Codeforces and instead of debugging your code, you end up debugging what just happened 🙃

Icing on the cake
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Tip (to self, others):
    Whenever changing limits like this for debugging purposes — it's probably best to add print statements alongside (so that you remember to fix this as well)
    Alternatively, in languages where there is support for compiler-warnings, add those :)

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

I got AC on problem E one minute after the contest ended. The problems were really nice, thanks

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

https://codeforces.me/contest/1969/submission/258748770 How to memoize this recursive approach to C ? Or any other recursive solution ?

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

what's the idea for c? I couldn't debug my dp solution in time, with mp[j][val] standing for j operations used and the last value being val. since val could be huge, i used unordered_map to store the status. and to avoid space overflow, status with the values that aren't possible to be at the end for current moment need to be erased. or is there a much easier solution?

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

    k is less than 10 so you can solve with 2D DP.

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

      bruh I thought $$$k \leq n$$$ and couldn't come up with anything. can't believe I have misread that

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

        I can't believe that I missed it. regretting a lot now.

        knowing the constraint k <= 10 makes the problem way easier.

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

    I did the same but got WA 5 times

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

It seems like the time limit of E is too tight. Submission https://codeforces.me/contest/1969/submission/258765134 got TLE on test 25 by using BTreeSet, however, submission https://codeforces.me/contest/1969/submission/258766945 got AC by using HashSet (it was simply replaced BTreeSet as HashSet)

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

Can anyone please explain me the DP approach to solve problem c?

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

    do dp range and the cost is the min element in range * length of range

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

    $$$dp[i][j]$$$ = the minimum sum when we only consider the first $$$i$$$ elements, and perform $$$j$$$ operations. We can do $$$dp[i][j] = dp[i-1][j] + A_i$$$ to do nothing. Suppose we perform $$$x$$$ moves: we convert elements $$$A_{i-x}, ..., A_{i}$$$ to the minimum element in this range (call it $$$min$$$), and the new sum of this range is $$$(x+1)*min$$$. The minimum sum for the remaining elements can be obtained with $$$dp[i-1-x][y]$$$, where $$$y$$$ is the # of moves performed beforehand. Therefore, we do $$$dp[i][x+y] = (x+1)*min + dp[i-1-x][y]$$$ for all pairs $$$(x,y)$$$ where $$$x+y \le K$$$.

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

      thanx for explaining the states and transitions

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

      If I define dp[i][j], the maximum sum of elements I am able to delete, if I am at index i and perform j operations. Then I subtract the maximum value of dp[i][j] from the total original sum of the array, why am I getting wrong answer ?

      Edit — Resolved. Should have used long long.

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

My second educational round, and again not solve C. So educational round means high difficulty??? Both two my edu round solve only AB and rank 3600+ (:_;)

I'm going to be specialist and hope to get my rate back in div3 round a few days later X(

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

    C is not too hard, but not too easy in this round. If you take a look at previous Edu round, it is something really different, so it doesn't mean high difficulty

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

      Maybe I just to weak in 2D or 3D dp (:_;).

      And I determined to try to come up with a greedy solution, till the end of round. Although I've imagined this is probably a dp, I refused to go ahead because I thought I have little chance to solve a 2D dp problem (x_x;)

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

    Or you could do tmrw's Div. 2 and somehow solve A-D :)

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

    why u lying?? ur 1. edu u solved ABC

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

      Oops, it was two rounds that were really close and I mistakenly remember this, sorry. It was actually the round right after that edu round:(

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

Fantastic Edu round as always. Thanks a lot BledDest awoo adedalic Neon Roms and all testers!

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

I posted my code of problem D in the last 10 seconds, but the evaluator didn't receive it.

After the contest finished, I reposted my code, and then it was accepted.

Now I wanna die right now.

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

Can anyone please check the error in this code for C?

Solution

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

    we pretty much used the same approach , but the problem meant to be solved using DP and not greedy

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

    are you using greedy? well, this case doesn't work for greedy

    5 4
    999 999 2 3 1
    
»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

C was bit hard for its position.

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

    I believe it's my skill issue:) it was a good problem actually

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

    hard to implement. Not hard to solve.

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

C was obvious dp don't why some people found D easier than C is it because there is some standard idea / technique if so please tell me. Thanks!

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

Many solutions to problem A, including mine, are hacked, because of set.

How is it possible? The time complexity is $$$O(t∗n∗(n−1)/2∗4∗log(4))=O(5∗10^7)$$$ which should not work longer, than 2 seconds.

I have solved ABCDE, and would become a master, if my solution to A wasn't hacked :(

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

    We'll stay forever this way You are safe in my heart And my heart will go on and on

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

    Pardon me if I'm mistaken, The time complexity of your code is O(t∗n∗n∗O(n)) = O(6∗109). As inner clr(set) takes O(n) in every iteration.

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

      He always just pushes 4 elements to the set and clears it, so clearing the set doesn't take o(n). It takes o(4).

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

    std::set has a lot of overhead as it uses a tree structure, so you end up using a lot of time allocating and deallocating memory, rebalancing the tree, etc.

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

    My solution is the same, but the only difference is that you clear the set, I define a new one each time. I think this is the reason why you take more time on the original tests and got hacked.

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

      i'm surprised that your solution din't get hacked. this one did get hacked tho. He also created a new set.

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

        maybe because he's declaring vectors and calling a solve function? I think the smallest differences can make my 1968ms get tle

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

          i found the place or the hole in the code which gives allows the hack to give TLE. Its the fact that the code does n^2 iteration, still no proof how tho. you code does $$$ \frac{n(n-1)}{2} $$$ iterations. I think that can make a proof. I tried both. Your approach just passes with 1999ms. The others don't. and that too if we don't use function call and stuff. A normal while(t--) loop passes barely but doing anything other that will not work. even if you do $$$ j = i+1$$$ it still gives TLE on test 4. creating a vector also doesn't make any different if we do $$$\frac{n(n-1)}{2}$$$ iterations.

          I tried finding the issue but I couldn't and this is the information i was able to discover. any details would be really appreciated by some experienced coder.

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

why my solution for problem C 258776010 getting Runtime Error

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

For problem E 258747661 should be hackable. I have no proof on the bound of the no of iterations.

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

Hi! can someone please point where I'm going wrong in task D. Any help is appreciated :)

258782796

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

Can anyone tell me where this approach for q3 is going wrong? I'm maintaining a last variable which is what was the last element in vector I'm iterating 258774405 aryanc403 can you help me with this ?

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

Can anyone explain what does it mean "Generator is not determinate [the verification run produces different output, cmd =7 4956565656565656564512121], [1100006 bytes, '1000 300 6 151 55 114 76 65 24 12 86 135 38 98 2...290 266 282 34 73 297 245 5 118 261 79 200 35 ', sha1=f0a1c17d87899a11c1db8f805df18da45b1251d5] vs. [1100006 bytes, '1000 300 2 151 55 114 76 65 24 12 86 135 38 98 2...290 266 282 34 73 297 245 5 118 261 79 200 35 ', sha1=a2117fdfb95eb249f578f57f01f328e2a91fc766]."

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

    It's a RTE

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

    A generator must be deterministic, that is, it must produce the same output every time it's run. If you use RNG, you must set a random seed.

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

I solved only one question A will I get rating

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

Could someone help me understand how my reasoning for C is wrong? I'm failing cases but I can't understand why 258783884

My thought process was to: keep indexes grouped and sorted by max(a[i]-a[i-1], a[i], a[i+1]) (max diff between its neighbours). Then for each K get the current maximum difference, update the element at i with min(a[i-1], a[i+1]), and keep track of how much the sum is being reduced by. Finally, update diff for (i-1) and (i+1) since arr[i] has been modified.

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

I really liked problems D and E!

»
6 months ago, # |
  Vote: I like it -8 Vote: I do not like it
Solution on C using DSU

can anyone provide counter example? I don't see any reason why this not working.

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

    You are applying a greedy algorithm, i.e. merging the immediate best, rather than doing a deeper search.

    For example,

    1 5 2 20 10 19 28

    Your algorithm will see the largest difference (20-10) and merge them, and then merge 19 together, totaling 10+10+10+28 = 58. but the optimal solution would be 20+10+10+10 = 50

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

I just spent quite a while debugging my solution to C, which I was confident was correct but failed on test 5 due to a runtime error. It turns out that it was a stack overflow error, and after I increased the stack size, my solution passed (original, with increased stack size). I feel that I should have gotten credit for my original solution during the contest since it would have passed within the given time and memory constraints and only failed due to a restriction in the judging environment.

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

I have solve the problem E by Monotonic Stack in O(n).

The submission

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

Idea for c ?

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

looking forward to the tutorial

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

How to solve E?

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

    let st[i] be the largest j so that j < i and the subarray [j, i] is not unique (if j doesnt exist, st[i] = inf).

    Now, if st[i] < i (for i = 1 -> n), we have a segment [st[i], i], now the problem becomes: calculate the minimum number of black points so that each segment contains at least 1 black point. It's easy to solve using deque and dp.

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

do we have penalty for wrong hacking attempt?

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

Could someone explain why this solution was hacked in problem A? Here's the link to the submission: link. It's supposed to be ( n^2 ) and should pass. Can someone verify if the test validator is working correctly?

awoo adedalic BledDest Neon Roms

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

    made a mistake, but set has a high overhead for each operation.

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

Good edu round :)

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

Can someone please suggest problems that are similiar to Yesterday's 2C

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

specialist in this contest, only able to solve A and B but in 10 mins so i got descent rank.

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

Could someone please tell me why this contest didn't count towards my rating? I did the registration as usual

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

    We just need to wait for the update of the ratings. It usually takes a few hours after the contest end.

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

where's the contest?

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

Until the editorial gets published, can anyone provide some help regarding problem F? I've been thinking of some DP, where $$$dp_i$$$ = number of coins you can get if you start with a full unique deck and have the last $$$i$$$ cards in the stack. I tried to come up with the transitions but I am missing something. Thank you in advance!

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

    Assuming “full unique deck” means one card of each number, you’re on the right track. In terms of transitions, here are some questions to think about:

    1. Suppose you want to transition from turn i to turn j. How can you determine which cards to discard on turn i in order to end up with cards 1..k on turn j? (Try writing out a few small cases.)
    2. How does discarding cards affect the number of pairs you can make? (It helped me to think about your DP state as minimizing the number of pairs you eliminate from the deck. How does discarding a card with an odd number of occurrences differ from discarding a card with an even number of occurrences?)
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Thank you very much, the confirmation that I am on the right track motivated me to keep going. I just got AC on it

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

Congrats to OliviaRodrigo who did very well on the contest! Big fan of your songs here!!

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

For problem B pre-test did'nt include overflow cases. :cry

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

    you using long long for ans i dont think its overflow

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

      its overflow check my new submission.

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

        yeh i see now , next time make sure use long long everywhere. thats the same thing happened to me one time now i use long long mostly.

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

Why are these two codes the same, but one Ce and one Ac? When the hack ended, it was still Ac, but now it looks like it has changed to Ce. 258710579 and 258844106. I need some help.

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

Will the rating changes before 942??

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

Could someone explain me why this https://codeforces.me/contest/1969/submission/258724763 code for B got AC on pretests and now is getting WA on test 1? I understand why it fails but why didnt it got WA on the same test during the contest?

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

    i think they know there is some problem thats why rating still not updated

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

    It's probably cause by ub(undefined behavior). You tried to get the front of an empty deque in int first=v.front();. And maybe in the pretest, this behavior somehow get a value that can pass test 1.

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

      How does undefined behavior work? Because it had to give a correct answer for every case formed only by '0's, and if it was so, why not after pretest?

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

        As it's name, it's undefined and we can't predict how it works. It's up to the compiler. Maybe you have extreme luck in pretest and passed temporarily, and your luck disappeared in main test.

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

          I had understood it works like that but seems I just had incredibly bad luck. Thanks for replying and have a good day

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

I realize that the optimal answer for C was 2D DP, however many contestants came up with 3D DP n*k*k, leading to MLE Any suggestions on how to remove the MLE

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).