Блог пользователя cry

Автор cry, 5 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • +423
  • Проголосовать: не нравится

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +116 Проголосовать: не нравится

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!

»
4 месяца назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Congrats on doing a problemset for every division!!!

Your contests are great :)

»
4 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Solid problemset as a tester

»
4 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

:3

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

As a tester, satyam343 tyr0Whiz :orz:

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hopefully pupil this time!

»
4 месяца назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

potato

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Wishing to become a specialist this time

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

18o3 Orz.

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

where is 74TrAkToR ?

»
4 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Hoping to rise from the trauma of last div2.

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится -45 Проголосовать: не нравится

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.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

GOOOOOOOOOOOOOOOOOOOOOOD LUUUUUUUUUUUUUUUUCK GYUS

»
4 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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 :(

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

As a participant, I want +ve delta :/

»
4 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

hope i dont bottle to get +8 :)

»
4 месяца назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

c825f6ed560288d59b75e853b3cbdc2e.png

why writers of this contest ain't listed

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

1"

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

First contest as a pupil let's go :)

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

hope back to expert:)

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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 (Ó⁠╭⁠╮⁠Ò)

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

cowodeforces ?

»
4 месяца назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Finally, a div 3 round :)

»
4 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Why are Div 3 contests so rare?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

cry sum!

»
4 месяца назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

i want to be tester

»
4 месяца назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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...

»
4 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Please give some easy and good questions :)

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

this time my target 50 plus delta

»
4 месяца назад, # |
Rev. 3   Проголосовать: нравится -7 Проголосовать: не нравится

Inshallah going to be expert today

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Cry orz always the best contests.

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

All the best!!! -Beijing·China

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

FINALLY. DIV 3.

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

GL evbdy !

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

bro, is the queue infinite?

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

slow judge

»
4 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

in queue

»
4 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

queueforces

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

queueforces :(

»
4 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Counting is Elation!

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    based

    • »
      »
      »
      4 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Love references to Honkai Star Rail LMAOOO.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

E,F,G all had HSR references wow

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

countforces!

»
4 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

E was FUN!!!!!

But D was ####

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Cheater top 30

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

queueforces

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    nope

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится -12 Проголосовать: не нравится

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

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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...

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
4 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

F is an excellent problem, kudos to authors

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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).

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      truly fascinating

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Today 300 Div 3 guys did it

      I think Many of them didn't );

      Spoiler
»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What do you mean

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I did BS on c my sol

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Easiest solution for E — 272838782

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)
    
»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

  • »
    »
    4 месяца назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

    • »
      »
      »
      4 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      Also it fails samples, so no penalty

      • »
        »
        »
        »
        4 месяца назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to E?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How to solve problem G?

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    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)$$$

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

    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})$$$

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ough, I thought the solution is smarter than this

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

.

»
4 месяца назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

I hate when testers lie

»
4 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится -19 Проголосовать: не нравится

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

    • »
      »
      »
      4 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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)
    
    • »
      »
      »
      4 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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)

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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
        
        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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)$$$.

»
4 месяца назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is this the solution for Question E

https://pastebin.com/CYYQNq7h

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

please open upsolving

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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";
  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In queue

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Countingforces

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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)

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

please hack my solution of Problem D : )

»
4 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Losing rating continuously. Should I take brake or any tips

»
4 месяца назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

I really liked the short statements.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I never do good in this man's contests

»
4 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hope to become green

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ratings will be updated soon

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
        Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

        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.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

the problems are very easy

»
4 месяца назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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!

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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 :(

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

seriously, i got 1599.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good contest!

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.