awoo's blog

By awoo, history, 5 weeks 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/12/2024 17:35 (Moscow time) Educational Codeforces Round 164 (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.

Big thanks to the tester shnirelman for his valuable advice and suggestions!

Good luck to all the participants!

UPD: Editorial is out

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

Hope it would be the best Edu round

Good luck for everyone!

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

After the contest I will be live discussion problems I manage to solve. stream link

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

No testers?

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

    It will be tested in production

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Testing complete. It's div $$$1\frac12$$$

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what does this mean?

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          =1,5 , that means it's harder than usual TT

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Disagree, It's the first time i did ABCD in a long time and I don't think D was on par with the usual div 2 D problem

»
5 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

BledDest round. les go

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope able to solve ABC

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Waiting

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Good morning ;⁠)

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

I'm just wonder why there are few Educational Rounds on Saturday...(They are my favourite) As a boarding school students, I only have space time to participate contests on each Saturday, so I can only vp it. :(

Wish there will be more Educational Rounds on Saturday :)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope this contest will be best for everyone. Best of luck guys.

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

This comment is in queue……………

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to become cyan

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
Hope for the best, Good luck to everyone!

hoping for no in queue difficulty :)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck for everyone

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

I wish, i would regain CM today.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I will pray for your +19

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My home was near the flood in our city, so i had to move on to my grandmother... Thus, I was late for the contest for one hour... So sad(

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

        Are you alright? Atleast now you can spend some quality time with your grandmother

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I am okay, thank you <3

          You are right!

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Hope to blue soon !

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

too much

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

cant participate :( hope everyone have a great time :>

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope for green today

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

sounds like it's mathforces time!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

"Single interger X" but it's a string XD, so tragic for me

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

B > A >= C

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

C is way too easy than B.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    both are very easy, there is little to no difference

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +2 Vote: I do not like it

      C is easy Gready problem and the solution can be noticed through the tests sample

      B is simple Sliding Window problem but this may be not clear as it is in C

      So B > C

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Bad C in my opinion

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

C was kinda easier than A, and definitely easier than B

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for me it took very long time to do C. i could not proof my approach for so long...

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Isn't it basically a^2 - b^2 = (a - b)(a + b)?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes, i knew i have to minimize the difference but i was doing silly stuff, i dont know why i am getting dumber by day... :(

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved A and B in-contest, having penalties on B, but solved C in a few minutes after reading it post-contest!

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Lmao, solved B,C,D in 30 minutes, but took 30 minutes and 5 penalties on A. Could have had 2100 perf instead of 1850.

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

what kind of data structure might help to solve problem like D, is this well known problem? like evaluate sum of value on every subset?

noticed value of a[i] is small must has something to do this, any hint?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice D but not C(I don't know how my code for C is true).

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

    if 2 numbers are closer to each other, their product will be bigger, e.g.: n^2 > (n — 1) * (n + 1) > (n — 2) * (n + 2) > ...

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Solution can be proved using induction. My first thought is using (x + y) ^ 2 / 4 >= x * y. The equal sign happens when x = y => Then we should make x and y closer

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you have 2 numbers $$$x$$$ and $$$c-x$$$ whose sum is a constant $$$c$$$, then their product is $$$x \cdot c - x^2$$$. Differentiating with respect to $$$x$$$ you get $$$c - 2x$$$, and differentiating again you get $$$-2$$$, which is always negative. Thus, setting the first differential at $$$0$$$ gives you $$$x = c/2$$$, which means that the original numbers being closer to $$$c/2$$$ will have the higher product. This is "kind of" common knowledge, but now you have a proof. Algebraic proofs are also common. This one's for the calculus lovers.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$xy = \frac{(x+y)^2 - (x-y)^2}{4}$$$ , and as $$$x+y$$$ is constant we should minimize $$$|x-y|$$$

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

I'm genuinely shocked so many people solved C (of course I might just be dumb, as everyone is saying it's easy). Any hints please?

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

    try to make numbers as close numerically to each other as possible 5*5 = 25 , 6*4 = 24 if numbers become equal product is maximum

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

    The intuition behind it is that if the sum of two numbers is fixed, their product reaches max when each of them is set to SUM/2 (you can easily prove this). Since the sum won't change your goal is to minimize the greater number and maximize the lower one, so just figure out the first different digit of each and put the lower of the remaining digits in the one where first different digit is greater and the others in the smaller one.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I remember seeing a proof like this. I was thinking something similar during contest, but I wanted to make the sum of x digits close as possible to sum of y digits (instead of actual numbers).

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    hint: compare prefix from 0 to n-1

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for the first index, you take the maximum of the two, then for the rest of the index take the minimum of the two. why that works? i dont really know lmao

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

    Suppose $$$1 \le x \le y$$$, then we can show that $$$xy > (x-1)(y+1)$$$. Try solving it from here.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Need to make the difference between the two numbers as less as possible. It's a general rule to maximize product of two numbers.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can any one look at my submission and see if it's correct I passed system test but after I read your comments I don't know if it's correct any more https://mirror.codeforces.com/contest/1954/submission/256352583

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

C is not at usual level at which C should be it is kind of easier than A

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

    yes I agree its way easier than A and B

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

solved C after 10 seconds of the contest because I wrote == instead of = it would have been the first time I solve 3 question in div 2 contest

»
5 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

Why the orange+ contestants are not out of contest (no asterisk before CF handle at least)?

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

    Asterisk = unofficial participants != unrated participants. Basically there are no unofficial participants in div1/2 contests. In div3 or below, some class of people must participate unofficially to give less motivations to cheat by making official standings consist of "cleaner" people.

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

      Got it, thanks! I think I still don't quite understand the difference between unofficial and unrated. Do you have a clear understanding of that?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Refer to the last div3 contest's announcement for the exact condition to be considered official participants, but in sum:

        • Difference between official / unofficial exists to make the official standings look nicer and discourage unsporting behavior, and only applies to div3 contests or below.
        • Rated / unrated is solely judged by participants' ratings -- people below a certain rating are always rated, regardless of their official / unofficial status.
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Unrated : When the contest will not affect your ratings due to your current rating range being out of the bounds from the contest. You will be shown in final standings. It depends on your current rating( & no of contests you have participated in for new users).

        Unofficial : You will not come in final standings unless you mark the check box with [] show unofficial. This also includes people who have submitted post contest or during virtual contests. It has nothing to do with your current rating.

        Please correct me if someone has a better explanation.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also think this is weird. In normal div2 contests they don't appear on the scoreboard unless you tick the "Show unofficial" option. For some reason in educational contests they appear even though the contest is unrated for them, and the option to filter for div2 appears only after the hacking phase (or sometime after the contest, anyway)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In early days educational rounds weren't rated for anyone, so it's not a surprise that everyone was official participant. It's just that at some point it started to be rated for Div. 2 people, among all 'official' participants.

»
5 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

Maybe I should only participate in educational contests

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you solve problem E? Your solution looks like it's O(n*logn) (or at least faster than n*sqrt), can you please explain it?

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

      In a few hours, if there is no editorial yet

      Idea: Ans for k is sum of amount of alive "islands' after 0, k, 2k, 3k hp deleted We can calculate this for every k' from 1 to 10^5. Then for each k just straightforward sum

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I love how you clearly explained it in a couple of sentences. Cool solution, could you share how you got there?

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

          visualizing an array like this helps me a lot in solving problems like this

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How to prove it, or at least how to see it?

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      Instead of basic chain attack we might consider the one that attacks all enemies at once but we pay $$$c$$$ cost for each attack where $$$c$$$ is number of maximal segments (segments that we cannot expand) of consecutive alive enemies (then we want to compute the cost instead of attacks count). One might notice that if we are able to quickly compute $$$c$$$ after some number of attacks in $$$O(1)$$$, then we can compute all answers in $$$O(MXlogMX)$$$ by simple simulation. To compute $$$c$$$ efficiently we can precompute how many maximal segments will remain after dealing $$$x$$$ damage to all enemies, which is pretty standard problem. My solution for reference

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe I really should :(

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i don't know why it took me more than 40 minutes to implement a simple knapsack!!!

knew the solution within a minute, i did so many implementation mistakes and so much shitty things, even tried to separate odd and even in dp and tried prefix sums in dp.

was simple knapsack!

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

    Me too lol I forgot to add the number of ways to the new state and got WA on pretest 5 three times lol

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

can anyone tell me why my solution for D doesn't work? (it failed tc 13)

my solution

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

    Had the same issue, tmp[{sum, mx}] += cnt; tmp[{tsum, tmx}] += cnt; You should take mod of them. Since they can get big.

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

      bruh, really :(? will try to fix that later. tysm for pointing that out. I forgot it can go as big as 2^n

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    tmp[{sum, mx}] += cnt;
    tmp[{tsum, tmx}] += cnt;
    

    you didn't use mod in this line. The wrong answer was because of overflow.

                tmp[{sum, mx}] %= MOD;
                tmp[{tsum, tmx}] += cnt;
                tmp[{tsum, tmx}] %= MOD;
                tmp[{sum, mx}] += cnt;
    

    I fixed it and resubmitted, but got TLE on testcase 16.

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

      yeah, maybe because i use both sum and max as a key. I thought it would work somehow XD

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

interesting D, thanks for the contest

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

7 penalties on A. What about you?

»
5 weeks ago, # |
  Vote: I like it -39 Vote: I do not like it

very classic problems. dislike

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

    It’s an Edu round
    “Useful, even well-known ideas will be reused in order to introduce them to a wide range of participants”

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it -36 Vote: I do not like it

      Oh man I didn't know that thanks!

      Don't click me if you are Indian
    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it +20 Vote: I do not like it

      you can read this comment from awoo him self where he says:

      I personally stopped treating edus differently from common div2s, and maybe you should too.

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

    Could you please tell me why were these classic and if yes where can i pratice problems like these, is there any archive or a filtered problem list?

»
5 weeks ago, # |
  Vote: I like it -77 Vote: I do not like it

awful wording in E. for 20 mins, I was thinking that each instance of the lightning propogates both left and right. should have just said "choose a subarray such that all elements are +ve and decrement it"

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Python users on C have a big advantage

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

    how?

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

    No language has any advantage, If The number can Go upto 10^100 then ofcourse you shouldn't even consider making it a number anyway, as the biggest number would almost take 300+ bits to be stored, If anyone even as to tries to store them in a int ( say someone stores it in a Big-integer in Java) then it just makes accessing individual digits harder, so a number isn't the way.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually, it's not really about large numbers, just the property that the product would be maximized when the numbers are closest to each other.

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

      I also had the same intuition(256377521) but I am not able to prove it, is there any proof of this property that you can provide?

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

        Let us call the constant sum of $$$x$$$, and $$$y$$$, as $$$c$$$. Then,
        $$$x = c - y$$$
        The product, $$$p$$$, can be written as
        $$$p = (c - y) \cdot y$$$
        Differentiating with respect to $$$y$$$, we get
        $$$p' = c - 2 \cdot y$$$
        WLOG, we can assume that
        $$$x \geq y$$$
        i.e., $$$2 \cdot y \leq c$$$
        $$$\implies p' = c - 2 \cdot y \geq 0 \ \ \ \forall y \leq x$$$
        Here, we see, that the first order differential (or the rate of change) of $$$p$$$ is positive over all valid $$$y$$$, i.e., $$$p$$$ increases with $$$y$$$, so we just have to maximize $$$y$$$ (while ensuring that it is less than $$$x$$$)

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

        A simpler proof without calculus:
        Let $$$c$$$, be the constant sum, and $$$p$$$, be the product.
        WLOG, let
        $$$x \geq y$$$
        For some non-negative $$$d$$$,
        $$$x = c/2 + d$$$
        $$$y = c/2 - d$$$
        $$$p = (c/2 + d) \cdot (c/2 - d)$$$
        $$$p = c^2/4 - d^2$$$
        Thus, on minimizing $$$d$$$, $$$p$$$ is maximized, as $$$c$$$ is a constant, which is effectively what you're doing

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

I don't see any point in adding the additional constraint on the number of balls in D.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You didn't use knapsack?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how did you solve it? I did knapsack and that is a pretty important constraint.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ehh? How did you do it without using the bound on the sum?

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

      The number of groups is max(maximum value, ceil(sum / 2)). So the sum values less than 2 * a[i] and greater than 2 * a[i] can be dealt separately.

      A rough inadequately explained solution:

      In the sorted array

      Let dp[i][j]: number of subsequences ending at i and having sum j

      f[i]: sum of ceil(sum / 2) over all subsequences ending at i

      Then the sum of values of subsequences ending at i will be:

      a[i] * (dp[i][0] + ... + dp[i][2 * a[i]]) + f[i] — sum(dp[i][j] * ceil(j / 2)) [j from 0 to 2 * a[i]]

      So I would only need sum up to 2 * a[i] to maintain the dp.

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

    If the total sum of $$$a_i$$$ does not have that constraint, then the maximum total sum will be $$$5000^2$$$. How you can deal with it?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    my solution was O(n * sum(a[i])) memory and time. is there a faster algorithm?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't see the additional constraint during the contest. I solved it for a[i] <= 5000.

»
5 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Any hints for E?

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

    Problem E. Let's call F[i] is the number of connected components when there were i damages dealt to all elements. We can find this by DSU or simple array. Lets for k from 1 to max(a[i]). Consider when the damage strike is k. At damage 0, F[0] = 1, so we need one strike. Next, when the damage is k, we need F[k] strike (because there were F[k] components). F[2 * k], F[3 * k], F[4 * k], ... is similar. The complexity is n / 1 + n / 2 + ... + n / n = n log n.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      when the damage is k, we need F[k] strike

      It is confusing for me. Maybe I misunderstand something. For example, a = [5, 2, 7] and k = 2. Then F[2] = 2, and the strike need to be done is 6. (2 != 6)

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

        I think what he means is that if k = 2, it takes f[0] + f[2] + f[4] + f[6] + ... + f[i] casts to kill all, where i is a multiple of k and i <= max(A).

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

      I don't understand, fuck you

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I spent all my time to solve B but it didn't work. But after the contest i realise that exercise C ist easier than B. It takes me only 5 minutes to solve C. I was so dumm !!

»
5 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Got 4 WAs and realized after contest that I was using the wrong modulo value in D :(

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Why there is not a bigger example for problem F? I took the wrong modulus (1000000007 -> 998244353), got WA verdict and did not realize it until the end, sad.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same mistake in D

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    just realised I was getting WA in E because I was taking mod.

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Heavy cheating in today's contest as solutions were released when the contest was running

Nullify this contest otherwise it will be unfair for everyone Here are the links to the cheater's videos' A: https://youtu.be/yXRyAn_SYXk?si=LbSIstKeOXdzgcb1 B: https://youtu.be/jDsYHXQJoWc?si=S4zptf35hazQqu6o C: https://youtu.be/3TrPpil9Xw0?si=BL35v3FAe8phfAID D: https://youtu.be/eJy82kVvRKg?si=ctsUvPCAI8vWN80T

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I see you draw attention to the channel

    And if this will be considered with less than 1000 watches then this channel can stop the rating for CF div2 till its owner die

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    is it possible to ban these cheaters IP address so that they can never visit codeforces website again with their device...

»
5 weeks ago, # |
Rev. 8   Vote: I like it 0 Vote: I do not like it

My Problem B submission 256318074

Can someone please help in finding out that what is wrong in my logic for problem B, Thanks!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When you want to "merge" 2 nearest numbers, neither of which is equal to a[0], you merge them using only v[i] — v[i-1] — 1 deletions. (However, you are correct in your count of moves, necessary to made first and last numbers in array differ from each over).

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      3 3 5 3 3 5 3 3 3 For this test case the answer should be 2 right ? I cannot exactly get my mistake And can you please guide me that how can I deal with this type wrong pretests as mostly my logic is correct but I am stuck by a small mistake

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, the answer should be 2. Your mistake is that between indices v[i] and v[i-1] there are only (v[i] — v[i-1] — 1) other indices, and not (v[i] — v[i-1]) (as you count in your submission). Essentially, you are deleting 1 more element than you really need.

        I can assure you, that the so-called "+-1 errors" are increadibly common for all programmers, and even after a years of programming you can still make this mistake. But i can afford an approach, which can probably reduce a chance of this mistake for you: in such cases, try to think about every index as a half-interval on the numeric line from zero (not inclusive) to i (incluzive), When you subtract one index from another, you get a length of half-interval from first index (not inclusive) to second (inclusive), meaning length as number of indices this half-interval cover.

        So, in that approach to get the number of indices between i and j, you should just remove 1 excess index from half-interval "j — i" (and that's how you get number j — i — 1).

        Not sure that this is exactly what you needed, but in my experience half-interval thinking often simplifies case analysis "where to assign an extreme value"

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot bro, I get my mistake I even came up with this test 3 3 5 3 3 5 3 3 3 during the contest but still somehow managed to mess this problem up. Anyways Thanks a lot for help

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is your code after the mentioned changes 256361851

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot bro, I get my mistake I even came up with this test 3 3 5 3 3 5 3 3 3 during the contest but still somehow managed to mess this problem up. Anyways Thanks a lot for help

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

D was simple Memoization.

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

    I think I'm the only one who didn't notice that line:

    Additional constraint on input: the total number of balls doesn't exceed 5000

»
5 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

Very nice contest. Problems were really good. Thanks for the round adedalic BledDest Neon Roms awoo and all testers.

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Perhaps E can be strengthened to $$$n\le10 ^ 6$$$

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think they set $$$n$$$ to only $$$10^5$$$ on purpose, letting $$$O(n^{1.5})$$$ solutions (easier to come up with) to pass.

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

Couldn't solve 'C', in 'C' i just realize multiplication works like Bits So greedily we'll allocate max of (s1[i], s2[i]) where (s1[i] != s2[i]) at the highest significant place of 's1' (at i) and then from there, iterate to the least significant side and allocate max of (s1[i], s2[i]) in place of 's2' (at i) and min of (s1[i], s2[i]) in place of 's1' (at i)

In contest, i knew to get the max multiplication possible, we have to do something such that difference of both numbers is less as possible.. but couldn't prove any soln for this. and ppl found 'C' the easiest LOL

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Bro, look at the "Announcement" again. It's 'Neapolis University Pafos' instead of 'Harbour.Space University'!!!

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

I CAN'T BELIEVE IT. This contest is going to pull me out of the swamp of 1790... but too strong.

My first 5 solves Div2, first orange Performance, and Candidate Master is on the way!!

D solution
E solution
  • »
    »
    5 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Can you pls provide a proof of "If the maximum of a subset is greater than the sum of the rest of the elements, the value is the maximum; otherwise, the value is ceil(sum/2)" for problem D (for the ceil(sum/2) part)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If one color accounts for more than half of the total, all the rest is not enough to pair up with it;

      Otherwise, you can repeat: group one of each of the 2 colors with the most balls and take them away. In this way, you will not get a 1-ball group except the final one.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This might also help:

      Let's assume we have three (you can assume more too) color balls with count: a a+x a+x+y such that a+x+y<a+a+x for the 2nd process => y<a

      This is what will happen with them as with repeat the process a a+x a+x+y a a a+y a-floor(y/2) a-ceil(y/2) a a+1 a a 1 0 0

      Hope this helps in understanding that at max 1 ball will be left only.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How well known is the trick to C? I couldn't solve it and was surprised how many other were able to. Is there a website they went to for tricks like that?

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

    Pretty well known. I guess high-school math covers such stuff

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

    I just wrote the samples on a paper in this form 73 = 7*10 + 3 31 = 3*10 + 1

    73 * 31 = (70 + 3) * (30 + 1) = 70 * 30 + 70 * 1 + 3 * 30 + 3 * 1 (Tried swapping numbers later)

    I noticed that after I find the most significant number in a that is larger than a number in b (assuming a > b), b is more important in making the product a larger number, so I need to maximize the numbers in b after that first different number.

    That's how I concluded it, not sure if everybody did the same.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you could have written a brute force solution and tried to find a pattern

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can easily see the trick by quantities, x*y and (x+1)*(y-1)

    here when y>x+1 its always better to reduce from bigger quantities i.e., y and and increase in smaller quantities i.e, x.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Do anyone have memoization solution for problem d ? if yes please provide.

I tried to wrote one but it is failing 256352960

»
5 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

A >> D

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What about D? describe main approach...Anyone pls

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could somebody help with D solution?

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

    simple recursive dp 256322429

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

      Bro, I need text solution) It's not hard for every one to find code for this problem

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you Please explain your recurrence ?

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

        sort arr 3 cases 1. pick element and stop (last picked element is max) 2. pick and continue 3. dont pick and continue

        base case return value will be max(sum/2,max_ele=arr[index])

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can't be pick element and stop will come automatically in pick not pick. Because pick not pick gives all 2^n possibilites. why it will not going to work in that case.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            if you do pick element and stop you will just get one element

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

Thanks you BledDest and all testers. It was a pure edu2 contest. I think all programmers are glad to participate.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Just 3 minutes off of E feels so bad

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can some1 give me hints in D on how to calculate groups for a certain set

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    groups will be max(sum/2,max_element)

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

    If you brute force over all possible sets, that would be $$$2^{5000}$$$, which is infeasible. A hint here would be to consider that the sum of all possible subsets is very small, and you can probably do just as much with a $$$CountOfSubsetsWith[SubsetSum]$$$ as brute-force.

    Tag
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

B > C, It was an easy problem No C.

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Good Edu Round!

»
5 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

In the third question it is not writtern that the length of the numbers will be same!!

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

    You are given two integers x and y of the same length

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But it has mentioned in the first line, "You are given two integers x and y of the same length"

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    mention in first line. read the statement carefully

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

How do you solve F? Initially it looked like a trivial application of Burnside Lemma, but the set of all reachable reachable states $$$X$$$ (here states are different in the usual string comparison sense) isn't acted upon by the cyclic group $$$C_n$$$.

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

    You can still apply Burnside Lemma here, but first you need to extend X to contain all shifts of reachable states. This is equivalent to making X contain all the combinations with no more than k+c 1s and having at least one (cyclic) contiguous segment of c 1s. After applying Burnside's Lemma, you'll end up with a similar subproblem for every divisor of n. Now every subproblem can be solved using inclusion-exclusion principle.

    I believe that this approach can be optimized to solve the problem in $$$O(n*\log\log(n))$$$ time

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What observation should I make on D?

/hint

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For a given subsequence, the value or the number of pairs we can form is the maximum element, if it is greater than the sum of remaining elements otherwise $$$\lceil sum/2 \rceil$$$

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

      But the only way to compute that would be to check each combination and calculate their sum. How does one incorporate dp in that to make it O(n^2)?

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

        You can calculate the number of sets that sum to a particular number using dp

        dp[i][k] = dp[i — 1][k] + dp[i — 1][k — A[i]] where dp[i][k] represents the number of subsets with sum k that can be formed using elements up to the ith index

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

          during calculation of ans,why did u multiply the VALUE with dp[i-1][j] and not dp[i][j]?also what does your dp[i][j] represent.

          edit:nvm,i got what u did

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Since we are dealing with subsequences, the order does not matter so sort the array.
        In this sorted array we can calculate $$$dp[n][sum(A)]$$$ in $$$O(n^2)$$$ where $$$dp[i][j]$$$ = number of subsequences using first i elements having sum j

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Invert the sum:

        sum over subsets f(subset) = sum over values v * (number of subsets with f(subset) = v)

        if you need a reference see Concrete mathematics chapter on sums.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what I'm doing wrong here? problem D 256376695 any help will appreciate

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

    You should sort array.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      unsure why it matter but got AC thank you.

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

        Consider array: 7 7 7 1 Without sorting when the sum is equal to 15 you are using 1 3 times and 7 0 times. With sorting you are using 1 0 times and 7 3 times.

        Your code assumes that the biggest number you are taking in this case is 1 because you consider it after 7. Hope this will help.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          that make much sense now, when update cnt any value less then 7 should be accounted otherwise will not counted but for greater number it doesn't matter because greater number will takeover.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved E but I don't know how to solve D >_<

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

This was a really good round (even if I didn't compete), the problemset was superb. I loved D and E. C was a little too easy to be in its position, but still entertaining nonetheless.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the system testing done?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/contest/1954/submission/256346898 this is my submission for B can anyone tell me a test case where it fails ,i tried but couldn't find one?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Tests Sample
    Your Code Answers
    The Right Answers
    The Deleted Numbers Order
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      okay got it i thought you can delete numbers from start and end only

      my bad!!

      how did you come up with the test cases?

      is there any tool for it?

      thanks!

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        These aren't (or may be) a part of the main tests.
        I put them as a sample of counter examples of your code.

        I think you can't know the exact test's input when its order become high like +80.

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

Is it unrated???

UPD:Now It's rated.=)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    May be, because cheating happened.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I chose two user randomly, and I looked so many users, all of them are unrated.And I can ensure that I didn't cheat.

      Why???

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it -21 Vote: I do not like it

        There were some YT videos with solutions during the live contest. That's y the contest might have been made unrated.(I am also not sure) U have not cheated but there are some guys who have cheated.

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

    Is it that Cf shows “unrated” when the rating hasn't been updated yet? I'm new to Cf and don't know if this happened before.

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

    System testing is pending. After that, the ratings will be updated. Till then, it will be shown as unrated.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

HELP HELP HELP

How can my iterative code giving Stack overflow it does not make sense

256427774

error

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

    Because you are declaring arrays ways and dp of size N*S which can get as high as $$$5000^2$$$.

    And since you are declaring them inside main function, it uses the automatic storage class, which is allocated in the stack frames.

    Stack frame's memory is quite limited and $$$5000^2$$$ integers is a lot.

    I changed the arrays to use static storage class with constant size 5000*5000 here 256430212 and your code passes :)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for pointing out the issue,

      I am coding in C++ for over 3+ years i did not know that this kind of limit exist.

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

        Note that Codeforces' compiler options make C++'s stack size unusually large. On Windows, the default stack size is 1MB but on Codeforces environment it's set to 256MB (see Codeforces Command Lines). On normal programming, you should never write that kind of code.

        (Small rant: large stack size gives advantages to C++ (and a few other compiled languages that has similar settings), which is kind of unfair to other languages. On C++, you can recklessly write deeply recursive functions thanks to the large stack size -- on the other hand, it's not possible to write deep recursion on Python.)

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      damn i'm tempted to switch to c++ , just so i can learn stuff like this

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

    You can not create such a big C array in function. The stack of a function is only several Megabytes and is only suitable for around $$$10^5$$$ integers. You can try to use a global array which can be much bigger or use std::vector.

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

When are we getting the final results? Have the submissions been rejudged yet?

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Is this unrated?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this unrated?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this unrated?

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

please provide an update on when the rating will be updated?

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

My rating is 609, will I be rated for it?? As im my contests section this round is regarded as unrated but here it says it's rated for all below 2100? #help__

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

It also not given editorial

»
5 weeks 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).

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

if you read the blog for latest div 2 contest it states that "UPD: The rating changes for Educational Codeforces Round 164 will be applied after this round." That means the rating will be given after the div 2 right?

blogpost link

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When are we getting rating updates? it’s been over a day already

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Rating are not updated yet ?? It is rated for div 2 still there are no updates yet.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain for me why l = ⌈a[i] / ⌈a[i] / r⌉⌉ in problem E?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello codeforces, my account is public so that the code can be accessible by anyone.It's not fault.Please save me for this time.