peti1234's blog

Codeforces Round #783 (Div. 1, Div. 2)
By peti1234, 3 years ago, In English

Hello Codeforces!

I am happy to invite you to Codeforces Round 783 (Div. 2), and Codeforces Round 783 (Div. 1) which will be held on, Apr/19/2022 17:35 (Moscow time)! This round is rated for both divisions.

I would like to thank the following people who made the round possible:

In each division there will be 6 problems and 2 hours to solve them.

Score distribution:

Div. 2: 500 — 500 — 750 — 1500 — 2000 — 2500.

Div. 1: 250— 1000 — 1500 — 2000 — 2750 — 3500.

Good luck!

UPD: Editorial

UPD2: Congratulations to the contest winners:

Div. 2:

  1. HenHenHenAAAAAAAAAAAAA

  2. QiangBro_ShuDe

  3. MarioPariona117

  4. Moomer

  5. SpadeA261

Div. 1:

  1. djq_cpp

  2. tourist

  3. maroonrk

  4. Um_nik

  5. Rewinding

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

Comments Comments (123)
| Write comment?
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

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

As a tester, good luck and have fun!

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -34 Vote: I do not like it

Am I the only person who is surprised from low points in score distribution?

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

As a tester, good luck and have fun! Problems are interesting and well prepared.

→ Reply
»
3 years ago, # |
  Vote: I like it -54 Vote: I do not like it

GoodLuck everyone!!

→ Reply
»
3 years ago, # |
  Vote: I like it -67 Vote: I do not like it

Maybe it will be like that: A(500), B1(500), B2(750)

→ Reply
»
3 years ago, # |
  Vote: I like it -75 Vote: I do not like it

Why does it take place on Tuesday?????

→ Reply
»
3 years ago, # |
  Vote: I like it -80 Vote: I do not like it

Judging from the score distribution, it seems like a speedforces round for div 2. Hoping for +ve delta for everyone.

→ Reply
»
3 years ago, # |
  Vote: I like it -79 Vote: I do not like it

As not a tester, good luck and have fun!

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -52 Vote: I do not like it

.

→ Reply
»
3 years ago, # |
  Vote: I like it -43 Vote: I do not like it

I will participate in this contest with my favorite electronic cigarettes.

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +74 Vote: I do not like it

ocean of downvotes >_<

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

downvotesforces

→ Reply
»
3 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Anybody here who can help me to change my username in codeforces id ??

→ Reply
»
3 years ago, # |
  Vote: I like it -58 Vote: I do not like it

People who are downvoting for no reason, may their girlfriend and wife cheat on them

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Jesus christ, I did not know someone takes contribution so seriously to a point where they pray on someone's downfall when they get downvoted. I get the sentiment that getting bombarded with downvotes is unfair, but I feel like you should not be that extreme when it comes to some internet points

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -46 Vote: I do not like it

      Chill bro. Its a joke

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

      OTOH consider that people who focus on dropping someone's internet points aren't gonna be super nice IRL to balance it out.

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

        Solid point, but man why can't everyone just be nice to each other :(

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

          Limited resources, both physical and abstract. Personality conflicts arising simply because we're not bots or a hivemind, but individuals. There's a balance to strike, everyone being perfectly nice would suck in other ways.

          tl;dr conflict's normal

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

thanks to ones for making this round possible

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

I'm afraid that people would be happier with 1000-1000-1500-3000-4000-5000 scoring in div2

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

    Dude is a prophet

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

      Huh? You know, that the real scoring and the one that I wrote are exactly the same in terms of relative difficulty, yes?

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

Am I the only one who can't focus on solving the fourth problem just because there are too less successful submission.

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

    I see it as a opportunity to improve my problem solving skills, headbutting hard stuff mid contest.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces Round #783 (Div. 2) in one photo:

Spoiler
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +189 Vote: I do not like it

Div.1 C is weird. I dislike it very much.

It's not that I failed to solve it, but such problem should appear in MO instead of competitive programming.

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

How to solve Div2 D?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    I just went with two maximum segment trees, one storing $$$dp_i - i$$$ and the other just storing $$$dp_i$$$ and as you iterate through the array, update the values at the relative prefix sum order (so just coordinate compress all the prefix sums and then use the order as indices)

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

      I even did it with 3 segment trees... looking for an elegant way to solve it.

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

        I did the same 3 segment trees sorting dp[i]-i , dp[i] and dp[i]+i. Although spent like 50 minutes debugging my solution :)

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the segment tree idea in D? I was thinking for any element e in the prefix sum array, we need to find the rightmost element in the suffix that is greater than prefix[e-1] in log n, but I couldn't figure out how to encode this into a data structure.

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

It is discouraging to see C was leaked like half an hour ago before the contest ended on same youtube channel that leaked answers during the last contest. It has around 350 views.

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

How to do Div.2 C? I did an $$$O(n^2)$$$ way and it was too slow.

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

    maybe you should consider what index should be "0", near the index should be "1", and ans+=a[i]/a[i+1]+1

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

    Check for each i (put that i 0 then form a decreasing sequence in the first half and an increasing sequence in the second half).

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

    My $$$O(n^2)$$$ was accepted. For each element, suppose the final value for $$$b_i$$$ is $$$k_ia_i$$$ for $$$k_i$$$ which is integer (and could be negative). Then you want

    $$$k_1a_1 < k_2 a_2 < ... < k_n a_n$$$

    Since $a_i\geq 1$, we bruteforce over the last index $$$i$$$ where $$$k_i$$$ is non positive. Set $$$k_i=0$$$. Then greedily assign $$$k_1, ..., k_{i-1}$$$ so $$$k_{i-1}a_{i-1}<k_ia_i$$$, $$$k_{i-2}a_{i-2}<k_{i-1}a_{i-1}$$$. Same thing for $$$k_{i+}, ..., k_n$$$. The choice of $$$i$$$ with the minimum $$$\sum_j k_j$$$ is the solution.

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

    the solution is in the testcases explanation, just find number of operations required when a[i] is kept 0, try for every index and output the minimum

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

    Okay, apparently, I did the same thing. For each $$$i$$$, I set $$$b_i = 0$$$, then I went through to the left and the right finding out the no. of operations to make the left decreasing and right increasing. Then, I output the minimum no. of operations. But then this $$$O(n^2)$$$ didn't work. I am using Python 3 btw. Is that why?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yeah. Even pypy3 was giving TLE. Pypy3 — 64 worked for me in the end.

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

        Ahh, thanks. I thought the problem was my solution.

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

For problem $$$D$$$, I tried having a DP of $$$dp[i]=\max_{j<i} { dp[j] + sgn(PS[i]-PS[j])*(i-j) }$$$ where $$$PS$$$ is presum table and $$$sgn$$$ is the sign function. I was wondering if we can use a DP speedup (convex hull) on it, but couldn't prove monotonocity. Can I get any hints if this is an ok approach/what I am missing?

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

    Hint: use segment tree to speed up computation of your dp (maybe more than one).

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Hint 1
    Answer
    Hint 2
    Answer
    → Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

For Division 2 The problems rating is not appropriate. First and second problem should have rating of 1000.

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

Guys i am confused https://codeforces.net/contest/1668/submission/154129473

above submission is passing pretest but

https://codeforces.net/contest/1668/submission/154104345

this doesn't. Although both are exactly same except that gans in first one is initialised to LLMAX. does answer in any test case exceed LONG_MAX? I wasted one hour on this :(

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

    the answer can be greater than the INT_MAX value and since your are taking min then your result will be capped by INT_MAX and the possible result greater than INT_MAX will not be taken.

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

It's been a long time since I've received so many negative emotions from the C div 1 solution....

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it
Struggle

TAT

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +76 Vote: I do not like it

Feedback on the problem set:

  • A: Very good problem. I had seen something similar recently and this was immediate.
  • B: Standard problem, still enjoyable. I thought a bit in order to find a way to avoid a segment tree, but couldn't find any way. In the end, coded a segment tree.
  • C: Spent quite some time trying to prove a lower bound (without success), then I found a reasonable construction and guessed that it was correct (hinted by the number of ACs). The statement and the solution are nice, but I don't really like to encounter this kind of problems in a competitive programming competition.
  • D: Not read (skipped since the ranking suggested that E could be a better choice).
  • E: Okayish problem. It is rather easy for being an E. After few minutes I had the main idea, then I spent a lot of time getting indexes right (it was a miracle that I managed to submit it before the end of the contest).
  • F: Not read.

Thanks to the authors for the contest!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    Proving the lower bound in C is actually very easy.

    Let $$$k$$$ be the minimum value such that there are $$$k$$$ columns and rows without a queen. Then $$$n - k \leq Q$$$, where $$$Q$$$ is the number of queens you place.

    Since there are $$$k$$$ columns and $$$k$$$ rows without a queen, there are $$$k^2$$$ squares you need to cover with diagonals. These squares appear on at least $$$2k - 1$$$ distinct diagonals. Thus, we must have $$$2k - 1 \leq Q$$$ where $$$Q$$$ is the number of queens you place. Thus, $$$\max(2k - 1, n - k) \leq Q$$$, thus $$$\left\lceil \frac{2n - 1}{3} \right\rceil \leq Q$$$.

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

    For B, the segment tree can be avoided by maintaining two monotonic sets (one for positive-sum, the other one for negative-sum) and a map(when the sum is 0). Ugly code :/

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

    It is quite surprising to me that one might solve C in the way that does not immediately prove its correctness, hence I believe criticism on this aspect is unjustified. Here is how my line of thoughts looked like: https://codeforces.net/blog/entry/102013#comment-904940

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      You are right when you say that once one finds the construction, then the proof is straight forward.

      I am not criticizing the problem because one can guess the solution. I don't like it because it contains zero computer science.

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

Let me try it: AtCoderForces

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

any hints for b and c ??

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

    For C iterate over each element and assume it to be 0 , calculate the number of moves to make all the elements after it to be increasing and all elements before it to be decreasing . Take the minimum answer for after iterating over every element.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

And thanks to the authors for the exercise on DP with Segment tree

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

I hate this round.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    In every contest there will be someone who hates contest and may call it "Insert_a_topic_here" + forces . Instead we should focus on our skills and appreciate the efforts of problemsetters.

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

https://codeforces.net/contest/1668/standings/page/3

kirya_molodec

→ Reply
»
3 years ago, # |
  Vote: I like it -54 Vote: I do not like it

The comment is hidden because of too negative feedback, click here to view it

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

Don't look at ranks 160-200

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +24 Vote: I do not like it

enjoyed a lot solving CDE, solved only C, but anyway, great problems, thanks

(but B was a non-sense and stupid, such problem just SHOULDN'T be in div1)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

is greedy + segTrees possible for D?

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

  image-2022-04-19-T16-22-07-267-Z

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

Places 160 — 200 of div2 have the same code for ABCD.

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

Some feedback:

I really liked ACD!

During the contest, I liked B, because I used the observation that there are no segments of size at least $$$2$$$ with sum $$$\le 0$$$, but as it can be solved entirely without this observation (with more segment trees), it's not a very good problem :(.

Also, E is pretty standard, but it's okay.

Anyways, thanks for the contest, I enjoyed it!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my solution for problem C

https://codeforces.net/contest/1668/submission/154109773

what's wrong?

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

    I think ans is not large enough, LONG_MAX is the same for INT_MAX

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

      I DON'T UNDERSTAND, WHY LONG_MAX CAN CHANGE ITS VALUE TO INT_MAX

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

        Because long is int in another name (It returns to the history of language)

        LLONG_MAX is the maximum long long in c++

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Got a question about time constraints for PyPy 3. In Div.2C after coming up with O(N^2) solution I was reluctant to submit it for quite a while, because 25mil operations seemed like a certain TLE. What would you say is an appropriate op/s limit for PyPy here? Or are there some time adjustments and n=5000 should be an instant hint that O(n^2) is fine anyway?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me the test case fails for this code 154119937

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

i request the setters and testers to find out the same codes and penalise them

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain test case 2 of problem C of Div2? Shouldn't the answer be 8?

Spoiler
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    No you need $$$3$$$ steps for the first and last element. You can only change $$$b_1$$$ with $$$a_1$$$.

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

Can somebody help me find out why my solution get TLE in pypy3, but accepted in pypy3-64 with only 514ms? 154083919

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

    I guess it's because division is an expensive operation and 64 bit pypy3 was able to handle the large number divisions better than the 32 bit version. This is what I thought before submitting my solution again after 2 TLE verdicts, but honestly I was surprised that it actually passed the pretests!

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

    Same here, and what a shame that I only realized the pypy3-64 existence in the last 10 minutes of the contests

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

I think it was on of the better recent rounds. I think that all problems were quite good and I have no significant points of criticism. Thanks for preparing it!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    Totally agree that all problems were good (maybe B was too standard and it were tempting to find a simpler solution). As always, this doesn't mean that the round was good too.

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

I unnecessarily wasted time in B thinking that they'll sit in order. I know that it was there in the explanation for a sample test case, but still could have mentioned that in the problem statement Peti chod.

→ Reply
»
3 years ago, # |
  Vote: I like it -19 Vote: I do not like it

SmallscoreForces

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice round, thank you!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

sus!!!?? His/her previous solutions got skipped and this contest's solutions also look sus! MikeMirzayanov

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

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

I think there are a lot of cheaters(aside from the videos that get uploaded on youtube during contest). And who is downvoting normal comments?(like 50+ downvotes for a lot of comms). Please ban their ip's because they can always make a new account)

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

Cheaters in div2 160-200 places. I checked about 10 accounts, all of these registered five days ago, all have the same code

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

here comes the cheaters on page 2 HtePhANA_ affianced.leon claudette_thomas_00

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

peti1234 for div2 problem B, my solution get an AC.

solution

but It should be wrong based on this test case:

1
1 4
3
→ Reply