cry's blog

Invitation to Codeforces Round 962 (Div. 3)
By cry, 5 months ago, In English

Hewwo Cowodeforcers!

sum and I are overjoyed to welcome you to participate in Codeforces Round 962 (Div. 3) on Jul/26/2024 17:35 (Moscow time). This contest is the last stop on our mission to problemset for every division. We hope you've been enjoying our stuff so far!

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks. After open hacks all accepted solutions will be rejudged on successful hacks.

You will be given 7 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for each wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third 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 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

We would like to orz the following individuals for making the contest possible:

Thank you for reading and we hope you have a fun and educational interstellar adventure :3

UPD: Editorial

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

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

Heyo, for those who are reading this, I highly recommend you to participate in Codechef Starters 144. Even though I was never a big fan of CodeChef contests, I watched satyam343 pour his heart, sweat, soul and tears into the contest. Even if you don't usually do CodeChef, you should totally make an exception just this once!

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

Congrats on doing a problemset for every division!!!

Your contests are great :)

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

Solid problemset as a tester

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

:3

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

As a tester, satyam343 tyr0Whiz :orz:

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

Hopefully pupil this time!

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

Congrats sum & cry for becoming cf grandwriters ! ( wrote rounds for all divisions)

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

Another cry 's contest! I am glad to be a participant!

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

potato

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

hoping to have loads fun participating. The first div 3 that is not rated for me)

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

Wishing to become a specialist this time

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

As an out-of-competition participant, I wish I was tester.

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

18o3 Orz.

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

cry and sum contest are the best!!Always enjoyed their problems.

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

where is 74TrAkToR ?

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

Hoping to rise from the trauma of last div2.

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

I have small question, can we give more rated contest to people below 1899 ?

  1. Div-2 is rated for 0 to 2099

  2. div-3 is rated for 0 to 1599

  3. div-4 is rated for 0 to 1399

technically, purple and violet can take part in same number of contest. I guess there is a small room for improvement in rated contests distributions.

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

    What rank is violet?

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

    yeah, maybe they can make all contests rated for everyone such that the high rank holders don't affect the new comers that much.

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

    so for every rating distribution there should be different division?

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

GOOOOOOOOOOOOOOOOOOOOOOD LUUUUUUUUUUUUUUUUCK GYUS

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

Hoping to reach pupil this contest. Been practicing quite a few amount of hard problems for me. Hoping to not mess up like a dumb ass. Ideone f ed me up and leaked my solutions :(

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

As a participant, I want +ve delta :/

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

hope i dont bottle to get +8 :)

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

c825f6ed560288d59b75e853b3cbdc2e.png

why writers of this contest ain't listed

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

1"

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

First contest as a pupil let's go :)

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

    Last div 2 was my first contest at pupil. I hope to become a pupil again

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

hope back to expert:)

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

This contest is the last stop on our mission to problemset for every division. Does this mean they sum and cry won't be writing more Div3s (Ó⁠╭⁠╮⁠Ò)

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

Sorry to say that Bangladeshi can't participate due to network issue in Bangladesh.

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

cowodeforces ?

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

Finally, a div 3 round :)

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

Why are Div 3 contests so rare?

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

cry sum!

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

i want to be tester

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

I've always wondered... Will there ever be a Div 3 round where it's not extended ICPC style? Not that I don't like the current format, but it would be very interesting...

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

    There's one if I recall. It's a Div 3, 2, 1 done simultaneously.

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

Please give some easy and good questions :)

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

this time my target 50 plus delta

→ Reply
»
4 months ago, # |
← Rev. 3   Vote: I like it -7 Vote: I do not like it

Inshallah going to be expert today

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

As a tester, I can confirm that the problems are high quality, and this is probably one of the best Div-3s I've ever seen. I highly recommend participation.

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

Cry orz always the best contests.

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

All the best!!! -Beijing·China

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

FINALLY. DIV 3.

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

GL evbdy !

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

bro, is the queue infinite?

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

slow judge

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

in queue

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

queueforces

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

queueforces :(

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

It's my honor to play the main role in problem A! Tks the problem setters!

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

Counting is Elation!

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

    based

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

      What happened to submission?

      Please fix it, as a newbie i can't move to problem D,E without confirmation whether my C is AC/WA. Longer delay will lead to more penalty if get WA.

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

Should i move to next problem or wait for WA :(

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

My post contest discussion stream discussing all problems

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

Love references to Honkai Star Rail LMAOOO.

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

Dude the D problem is so tough, the constraint is so tough to deal with

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

E,F,G all had HSR references wow

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

countforces!

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

E was FUN!!!!!

But D was ####

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

Cheater top 30

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

queueforces

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

Is $$$O(n \sqrt n)$$$ not intended to pass in G? Or are my data structure implementation skills just trash? I had to do a ton of optimization to get it to pass.

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

    nope

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

    What have you wrote for $$$O(n \sqrt n)$$$ lol, why not $$$O(n \log(n))$$$

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

      Honestly, I have no clue how to solve it with a segtree. I can't really do anything with a segtree beyond copy paste a template for standard point / range addition / assignment with point / range queries.

      So I just implemented the obvious sqrt decomposition idea of dividing the array of "number of segments covering the $$$i$$$-th edge" into blocks of size $$$\sqrt{n}$$$ and store the minimum value and its count for a block.

      For an update that covers an entire block, the minimum of all elements is updated by the same value, so we can store this value in a separate integer in $$$O(1)$$$ time. For the starting / ending blocks just update the specific elements recalculate the minimum. So an update takes $$$O(\sqrt n)$$$ in total.

      Then you can just calculate the number of uncovered edges by adding the number of min elements for each block that has a minimum (including the block additions integer) value of $$$0$$$ in $$$O(\sqrt{N}$$$ time. Turns out this has a slower constant factor than the updates for some reason, so you can just calculate the relative effect during the update and store it in a integer which can be queried here in $$$O(1)$$$ time to squeeze it into time limit.

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

        Mindblowing, 2200+ guy doesn't know segtree but knows sqrt decomposition.

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

        Btw, segtree and sqrt-decomposition are basically the same structure: they're B-trees with branching factors of $$$2$$$ and $$$O(\sqrt n)$$$ respectively. So idea is the same, just different implementations.

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

        the segtree used here to maintain query (min, frequency of min) and range add is the same as the one used to solve area of union of rectangle, which is a quite standard problem?

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

Well now that the round is over... This was very sad.... TLE everywhere (and one MLE)... I couldn't get C to not TLE on case 6, and F I couldn't get past test case 4... Today felt like SegmentTrees and prefix sums, but clearly I'm just trash...

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

    if you're thinking segment tree for a div 3 C, you're too far gone brother.

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

    try some div4 contests or "easy problems". sometimes i feel like that with many complex topics it's harder to solve easy problems because i think of complex approaches

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

      Yeah I think you are right, I need to fill in those gaps to think of simpler approaches. The editorial made me realize how I quickly jumped to more complex solutions too quickly (though I do think my approach may have passed with c++)... Thanks for the feedback.

      → Reply
»
4 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Anyone else had trouble taking inputs as numbers in B? Had to take each line in the matrix as a string.

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

I spent so much time to realize that I forgot to take modulo on E

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

Guys what was it??? a nightmare for me.

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

Fucking python, my $$$O(n \log n)$$$ with segtree for G fails by TL.

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

F is an excellent problem, kudos to authors

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

Hints for F : Bomb

  • Solve the problem for $$$k \leq 10^6$$$. You'll realize that the greedy strategy of picking the largest $$$a[i]$$$ is correct. However, this greedy must be applied in a simulation, because the largest element will change at each step.

  • Split each $$$a[i]$$$ into multiple elements, with values $$$a[i]$$$, $$$a[i] - b[i]$$$, $$$a[i] - 2b[i]$$$, etc. This is an Arithmetic Progression, so we won't store these values explicitly.

If you consider a number line as $$$[0, 10^9]$$$ (where each point denotes a term of the arithmetic progression , it's clear that you will always take a suffix). Therefore, you can do a Binary Search on Answer.

Assume that the smallest element that you picked is $$$> mid$$$. Then, for each $$$a[i]$$$, you can compute how many terms will it contribute to the answer, and what is the sum that it would contribute to the answer. If the count is $$$< k$$$, you update the result, and look in $$$[low, mid - 1]$$$. Else, you look in $$$[mid + 1, high]$$$. Keep in the mind that you don't necessarily need to take all terms == mid.

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

    It's very interesting how CF ratings have evolved. When I set exactly this problem 10 years ago, a lot of purples couldn't solve it. Today 300 Div 3 guys did it and a grey guy writes an editorial.

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

      Haha, true (although arguably my true rating is around specialist, but I don't participate in contests these days).

      The binary search idea was immediately obvious to me, but didn't have the courage to implement it (I thought the values == mid might have some pesky corner cases).

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

      truly fascinating

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

      Today 300 Div 3 guys did it

      I think Many of them didn't );

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

In problem D , can we apply binary search on all three dimensions simultaneously ??

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

    What do you mean

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

      I was thinking the search space in a 3D matrix, where dimensions represents value of a,b,c. matrix[i][j][k] represents (i*j + j*k + k*i <= N && i + j + k <= X), And onto this matrix I try to apply BS from all three dimensions to calculate answer.

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

    I did BS on c my sol

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

Hey everyone, how did you approach problem 1996C - Sort? I initially had an O(nq) solution which was too slow, and ended up using prefix sums for an O(q) solution. I'm wondering what other approaches I could have taken, as my code was quite long so I wanted to know if there was an easier way of approaching the problem.

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

I desperately submit problem D in last 5 min thought it was gonna TLE but accepted. Feels very lucky tbh

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

Easiest solution for E — 272838782

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

    Liar, mine's easier:

    for _ in range(int(input())):
    m = [[-1, 1][ord(c) - 48] for c in input()]
    a, o, b = len(m), 0, 0
    mp = {0: 1}
    for r in range(a):
        b += m[r]
        if b not in mp: mp[b] = 0
        o += mp[b] * (a - r)
        mp[b] += r + 2
    print(o % 1000000007)
    → Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

doesn't judge ignore '\n' symbols between answers for every test in test case?

Here's my "wrong" solution for B — https://mirror.codeforces.com/contest/1996/submission/272741233 Here's fixed version, but I lost 10 minutes because of the slow queue — https://mirror.codeforces.com/contest/1996/submission/272756934

Also I tried that for C and it worked — https://mirror.codeforces.com/contest/1996/submission/272781207

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

    Same man.
    272749737 New line between output for each test case. WA
    272764930 Without new line between output for each test case. AC
    WHY ???
    Last line of statement says : "output ... on a new line."
    Is that why I get WA for this.
    Will I get 10 mins of penalty plus 10 mins of waiting time in queue to get the WA in the first place for this reason which I am not sure is even a mistake ?
    sum
    cry
    (Apologies for pinging)

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

      it means output on a new line, not output a new line between each test case

      Also it fails samples, so no penalty

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

        I don't mean to say that I did this extra new line because of the statement. I mean to ask did the output format require no new line between outputs and I should have paid attention to that ?

        edit: Oh okay no penalty is better and nobody can do anything about the queue. Thanks for quick response, orz.

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

Was e based on a prefix array with maps and time complexity O(n)?

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

How to E?

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

Nice contest, thanks to the authors. Can't believe I couldn't AK today :\

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

I was unable to submit it went into a continuous loop of cloudfare verifying you as a human

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

How to solve problem G?

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

    Remove one edge -> every path between two friends is unique -> add 1 for all edges in the path for every pair of friends. Maintain segtree over the resulting array for minimum and its quantity and support addition on segment. $$$O(n \log n)$$$

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

    Supposed that we fixed a certain road. Then, between each pair of friends, there is exactly one path which does not contain that road, and say we choose that path. We shall iterate over all roads and for each road and for each pair of friends, we choose the unique path which does not contain that road, and find the total number of roads used. To find the total number of roads used, we use a range update segment tree. In each segment tree node, we keep track of the minimum value in that sub tree as well as the number of occurrences. See my solution.

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

    For any edge between $$$a$$$ and $$$b$$$ there are exactly two possible paths:

    • Path $$$1$$$: $$$a \rightarrow a + 1 \rightarrow \cdots b$$$

    • Path $$$2$$$: $$$a \rightarrow a - 1 \rightarrow \cdots \rightarrow 1 \rightarrow n \rightarrow \cdots b$$$

    Notice that deciding to delete an edge $$$i$$$ excludes exactly 1 of these paths, i.e., all edges covered by the other path cannot be deleted.

    Let edge $$$i$$$ be the edge between nodes $$$i$$$ and $$$i + 1$$$ (or $$$1$$$ for $$$i = n$$$). Then the optimal path between $$$a$$$ and $$$b$$$ if edge $$$i$$$ is deleted will be:

    • For $$$1 \leq i \lt a$$$, the ideal path will be Path $$$1$$$

    • For $$$a \leq i \lt b$$$, the ideal path will be Path $$$2$$$

    • For $$$b \leq i \leq n$$$, the ideal path will be Path $$$1$$$

    So if we iterate on the edge to delete in increasing order of $$$i$$$, the total number of edges "switches" required is only $$$2n$$$.

    So if we have a data structure that can:

    1. Perform range updates to increase or decrease the number of covering segments for a range $$$[l, r]$$$ in $$$O(x)$$$ time.

    2. Identify the number of edges that are not covered by any segment in $$$O(y)$$$ time.

    Then we can solve this problem in $$$O(n \cdot (x + y))$$$

    One such way to do this is using sqrt decomposition which allows $$$x = O(\sqrt{n})$$$ and $$$y = O(\sqrt{n})$$$ / $$$O(1)$$$ depending on implementation.

    It is also apparently possible to do this with a segtree in $$$x = O(\log{n})$$$ and $$$y = O(\log{n})$$$

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

    Ough, I thought the solution is smarter than this

    → Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

.

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

I hate when testers lie

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

a lot of cheating going on in D and E i believe

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

Hello, for problem 1996D - Fun, how did you guys manage to optimize it? I only had time to find a mathematical formulation of the problem, resulting in the following python code: 

import math

n = int(input())
x = int(input())

total = 0
for a in range(1, min(x-2, math.floor((n-1)/2))+1):
    for b in range(1, min(x-a-1, math.floor((n-a)/(a+1)))+1):
        total += min(x-a-b, math.floor((n-a*b)/(a+b)))
        
print(total)

I can mathematically deduce the result of min(x-a-b, math.floor((n-a*b)/(a+b))), the issue is that if the result is the latter i don't know how to optimize summing those values.

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

    $$$a,b,c\leq{\sqrt{n}}$$$

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

      It is possible that $$$\max(a, b, c) > \sqrt{n}$$$. The minimum two of $$$a, b, c$$$ are less than $$$\sqrt{n}$$$.

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

        Oh yeah actually thats right I am lucky I implemented correct solution.

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

    The trick is you #print(a, b, (n-a*b)//(a+b), x-a-b) on the first brute force. Then realize (n-ab) // (a+b) >= 1. Then solve the equation

    Here's my python code:

        for a in range(1, min(n,x)):
        for b in range(1, min((n-a)//(a+1)+1, x-a)):
            res += min((n-a*b)//(a+b), x-a-b)
    → Reply
    • »
      »
      »
      4 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      272847061

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

      How did you calculate the range for b? Specifically the (n-a)//(a+1)+1 part

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

        I kinda brute force the b first (run from 1 to x-a). Print the (n-a*b)//(a+b), x-a-b. And see the redundant part (when n-a*b//(a+b) = 0, the for loop should just be stopped).

        Then we can assume n-a*b >= a + b. Then b+a*b <= n-a. Then b <= (n-a)/(a+1)

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

272848365 why my code wasn't working for problem c?

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

    according to your code

    for (long long j = 0; j <= 25; j++)
{
   mpa[queries[i].second - 1][j] = mpa[queries[i].second - 1][j] - mpa[queries[i].first - 2][j];
   mpb[queries[i].second - 1][j] = mpb[queries[i].second - 1][j] - mpb[queries[i].first - 2][j];
}

    if $$$l$$$ in the query isn't 1, then you will change the range answer [1 ,.., R] to [L ,.., R] so then when I will ask you to get me the answer of[1 ,.., R] your code will give me the answe of [L ,.., R] which is wrong

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

      If L is 1, then their is if block which gives answer for 1 To R

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

        this test case

        1
5 2
abcde
edcba
2 3
1 3

        the right answer is

        1
2

        but your code output is

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

          I got it, Basically, i was modifying my map for case where L != 1 which were affecting my other queries. I created new vector for that case and it worked. Thanks for the help

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

How to solve E

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

    Don't try to count number of pairs $$$(x,y)$$$ for every $$$(l,r)$$$.

    Instead, for every pair $$$(x,y)$$$ try to count the number of possible pairs $$$(l,r)$$$.

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

No hacking phase? edit : Oh, it just started.

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

is this the solution for Question E

https://pastebin.com/CYYQNq7h

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

please open upsolving

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

    There seems to be one stuck submission: 272840297

    This needs to be addressed before we can upsolve or start hacking.

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

one day the earth will be not suitable for living, because temperature is increasing and people are greedily using resources. So why people fight for short term materialistic contest?

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

how this is TLE on problem E

    string s; cin >> s;
    int n = s.size();
 
    map<int, vector<int>> freq;
    freq[0].push_back(-1);
    
    int count = 0;
    modnum ans = 0;
    for (int i = 0; i < n; ++i) {
        count += (s[i] == '1');
        int diff = count - (i + 1 - count);
        for (auto x: freq[diff]) {
            ans += countValidPairs(x + 2, x + 1 + (i - x), n);
        }
        freq[diff].push_back(i);
    }
 
    cout << ans << "\n";
→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider test case 10101010101...01010, then your time complexity becomes quadratic because there are O(n) occurrences of the diffs 1 and 0.

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

    when the string is like this 0101010101.., then your code will have $$$O(n^2)$$$ time complexity

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

In queue

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

upsolving this one is gonna me mad, one of the best contests i stumbled across

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

Top $$$5$$$ in the official standings are all Vietnamese LOL.

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

    2nd place has 4 skipped contests out of 24 participated. 4th place has 5 skipped contests out of 9 participated. I'm sure it's legit kek.

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

Countingforces

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

First contest in almost 3 years. And the quality of problems is as good as ever!

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

So many cheaters lmfao, for problem D(maybe more), I can see lots of similar 3 liner submissions !!! Doesn't Codeforces have plagiarism check?

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

    The code for problem D is literally that simple, so solutions with the same code is expected I guess, especially with this large amount of participants (I don't deny that there are cheaters though)

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

please hack my solution of Problem D : )

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

Really liked the idea of Problem F. Kudos to the authors.

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

Only I tried to solve the $$$G$$$ problem randomized?(Note that if we do not take an edge $$$(x, x + 1)$$$ in the answer) then all others are recovered unambiguously. 272831028

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

Screencast with commentary

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

Problem C was nice I was dumb that carry map of map instead of vector of vector :(

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

Losing rating continuously. Should I take brake or any tips

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

    dont take break more than 1 week or less than 3 months.

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

codeforce was hanging , i solve problem E and i cannot submit it :(:(

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

I really liked the short statements.

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

I never do good in this man's contests

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

Note that the penalty for each wrong submission in this round is 25 minutes.(15 min in queue)

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

hope to become green

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

Hey. So this was my first contest on Codeforces and I dont know how this works but I assume I am an unrated player. I thought that this round was Rated for me and I managed to solve 5 out 7 questions. Now the contest shows in my Contests section as Unrated. What is the issue? Why was it Unrated for me?

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

    Ratings will be updated soon

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

      Oh so till the Ratings get updated, the contest will stay in the Unrated Section? Thanks for the reply.

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

        just went through your code. Seems like your question 5 solution is copied.Its gonna get hacked after system testing since the code you got had a bug put in there by really smart people to catch idiots like you. Next time use your own brain to solve the problem.

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

the problems are very easy

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

RANT!!! Looking at the number of submissions in C, D and E, it was clearly evident that a lot of cheating took place the last contest. The endless waiting queue just made it worse. Needed just a +2 to get back to pupil... and here I am, standing terribly low at the standings!

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

    For god's sake, it's high time that strict measures are implemented to just ban these people from the platform. Been doing CP for quite some time now, and cheating has never been this great a concern. It gets very demotivating to see your ratings going down inspite of you trying your level best to keep up :(

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

Good contest I learn a lot about math and binary search .

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

can anyone help me findout why it's giving TLE in test 6??272771836

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

seriously, i got 1599.

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

Good contest!

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

I can prove that I have encountered almost the same question as Question F before. This question is Question 9 "Skill Upgrade" of the C++ Group of the 13th Lanqiao Cup in 2022 in China, and I have seen the solution to this question before.I hope you can change your judgement of my code.Please reply to me within two days.

This is the link to that question.

https://blog.csdn.net/m0_62609939/article/details/128653128

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

    My solution is 272848252 for the problem 1996F

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

Hi, in the contest "Codeforces Round 962 (Div. 3)", my solution 272814471 for the problem 1996F significantly coincides with others, but this solution was written by me in https://www.acwing.com/activity/content/code/content/7949410/ on March 5th, 2024, in other words, this is my own code, so I didn't break rules, I sincerely hope that my solutions in this contest won't be skipped.

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

Problem F is similar to https://www.acwing.com/problem/content/4659/

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

Hello,my solution has been skipped,due to the problem 1996F coincides,The problem 1996FIt is an original question from a competition called Blue Bridge Cup(lanqiao) for Chinese university students two years ago, only the data range is different.Here is the link to the original question for this question,which came from the 2022 Provincial Contest in C++ category Group C:https://www.lanqiao.cn/problems/2129/learning/?page=2&first_category_id=1&second_category_id=3&tags=2022 I have participated in this game, it is relatively high in China, I found that after I sloved this question, I just will be just the solution of this question to modify the input format and data range will be passed this question, this is the link to the solution of the problem!:https://www.acwing.com/solution/content/160566/ The date is 2023.01.06; I hope you can restore my submission and ranking

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

Hello, you told me in a private message that the F question is highly overlapping with other people, but because the idea of this question is the same as the skill upgrade question in the 13th Blue Bridge Cup C++ Group C, and I wrote this question, plus I learned someone else's code at the time, it is very likely that the code will overlap significantly. I hope you'll be able to keep my code from being skipped. Here's the address of the topic:https://www.acwing.com/problem/content/description/4659/ Wait for your message！

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

I guess these people need to rework on their website

It taking too long to test my solutions

My questions were in queue literally for 2.5hrs

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

The E question is almost exactly the same as the "skill upgrade" of the 13th Provincial Competition of the 2022 Blue Bridge Cup, and I have done this question before and memorized the answers in the solution, but I said that I checked the duplicate with other codes, but I don't know those people at all

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

The F question is almost exactly the same as the "skill upgrade" of the 13th Provincial Competition of the 2022 Blue Bridge Cup, and I have done this question before and memorized the answers in the solution, but I said that I checked the duplicate with other codes, but I don't know those people at all

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

Heyo,my F question has been skipped,but I didn't plagiarize the code.I once wrote a similar question,Here is a link to this question:https://www.acwing.com/problem/content/description/4659/ .I've learned the solutions in it so I write the F by this solutions.Here is a link to the solution:https://cdn.acwing.com/solution/content/231750/ .I hope you can re-adjudicate the verdict,thank you! 1996F - Bomb

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

1996F - Bomb

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

The F question is almost exactly the same as the "skill upgrade" of the 13th Provincial Competition of the 2022 Blue Bridge Cup, and I have done this question before and memorized the answers in the solution, but I said that I checked the duplicate with other codes, but I don't know those people at all

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

Don't pass info to my country, they are not talking with me

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

Dear Codeforces Team,

Thank you for bringing this matter to my attention. I understand the importance of maintaining the integrity of the competition and take these rules very seriously. I would like to explain that the solution I submitted for problem 1992D was developed independently. I did not use any public or shared sources, and I have always been cautious about adhering to the competition guidelines. I understand that similarities in solutions can occur, especially for problems that have standard approaches or well-known algorithms. I assure you that I did not intentionally copy or share my solution with others. To further demonstrate my commitment to fair play, I can provide the development history of my solution, including timestamps from my local environment that show the progression of my work. Moving forward, I will be even more diligent in ensuring that my work remains private and follows all competition rules. I am dedicated to maintaining the highest standards of integrity in all my participation. Thank you for your understanding and consideration. Please let me know if there are any additional steps I can take to resolve this matter. Best regards,

Abdulrahman_Gaball.

→ Reply