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:
- Aleks5d for coordinating the round!
- KAN for reviewing the problems.
- 4qqqq, YashDwivedi, k_balint, Riladavin, Peti, Akulyat, kclee2172, errorgorn, dorijanlendvaj, KAN, gamegame for testing the round and giving valuable feedback.
- MikeMirzayanov for great Codeforces and Polygon platforms.
- NEAR for supporting the Codeforces community! Details can be found in this post.
- You for participating!
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:
Div. 1:
Auto comment: topic has been updated by peti1234 (previous revision, new revision, compare).
As a tester, good luck and have fun!
Am I the only person who is surprised from low points in score distribution?
No
As a tester, good luck and have fun! Problems are interesting and well prepared.
GoodLuck everyone!!
Why so much downvotes?
Maybe it will be like that: A(500), B1(500), B2(750)
Yeah I also think so
Why does it take place on Tuesday?????
Judging from the score distribution, it seems like a speedforces round for div 2. Hoping for +ve delta for everyone.
As not a tester, good luck and have fun!
As not a tester ----< downvote
As a tester ----< upvote
.
I will participate in this contest with my favorite electronic cigarettes.
Can your ZhenZhu write a program?
Comedyforces
Nice DP
Thenks
ocean of downvotes >_<
Why people didn't downvote you?????
You are a little unsmart.
downvotesforces
Anybody here who can help me to change my username in codeforces id ??
Can only be changed in first 10 days of January each year
Ok, Thanks !
People who are downvoting for no reason, may their girlfriend and wife cheat on them
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
Chill bro. Its a joke
OTOH consider that people who focus on dropping someone's internet points aren't gonna be super nice IRL to balance it out.
Solid point, but man why can't everyone just be nice to each other :(
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
thanks to ones for making this round possible
I'm afraid that people would be happier with 1000-1000-1500-3000-4000-5000 scoring in div2
Dude is a prophet
Huh? You know, that the real scoring and the one that I wrote are exactly the same in terms of relative difficulty, yes?
Am I the only one who can't focus on solving the fourth problem just because there are too less successful submission.
I see it as a opportunity to improve my problem solving skills, headbutting hard stuff mid contest.
Codeforces Round #783 (Div. 2) in one photo:
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.
How to solve Div2 D?
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)
I even did it with 3 segment trees... looking for an elegant way to solve 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 :)
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.
try binary search bro
My implementation does what you want 154116565
But still gets wrong answer.
This one is the same but removed i > mid 154119937
Thank you it was instructive to read
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.
A dead wish to Coder who leak solutions
How to do Div.2 C? I did an $$$O(n^2)$$$ way and it was too slow.
maybe you should consider what index should be "0", near the index should be "1", and ans+=a[i]/a[i+1]+1
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).
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
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.
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
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?
Yeah. Even pypy3 was giving TLE. Pypy3 — 64 worked for me in the end.
Ahh, thanks. I thought the problem was my solution.
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?
Hint: use segment tree to speed up computation of your dp (maybe more than one).
What is the minimum possible length of negative and zero sum subarrays that are enough to reach the optimal solution?
Now that negative and zero sum cases are handled. Can you mould your DP function in a way that it becomes easier to compute?
$$$dp_i$$$ = $$$dp_j + i - j$$$
$$$dp_i - i$$$ = $$$dp_j - j$$$
$$$F_i$$$ = $$$F_j, j < i, pre_j < pre_i$$$
Form a similar $$$F_i$$$ for the case when current element is $$$0$$$ or $$$<0$$$. I think you can grasp it from here onwards.
Thank you!
For Division 2 The problems rating is not appropriate. First and second problem should have rating of 1000.
Guys i am confused https://codeforces.com/contest/1668/submission/154129473
above submission is passing pretest but
https://codeforces.com/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 :(
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.
It's been a long time since I've received so many negative emotions from the C div 1 solution....
TAT
Feedback on the problem set:
Thanks to the authors for the contest!
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$$$.
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 :/
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.com/blog/entry/102013#comment-904940
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.
Let me try it: AtCoderForces
ConstrForces
any hints for b and c ??
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.
And thanks to the authors for the exercise on DP with Segment tree
I hate this round.
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.
https://codeforces.com/contest/1668/standings/page/3
kirya_molodec
The comment is hidden because of too negative feedback, click here to view it
You should write something like "click here to view it" :)
I m noob
don't downvote it was just for fun
Yeah, people are probably continuing the fun by making it transparent, to look more realistic :)
Don't look at ranks 160-200
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)
is greedy + segTrees possible for D?
More or less, I used dp and segTree
Places 160 — 200 of div2 have the same code for ABCD.
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!
This is my solution for problem C
https://codeforces.com/contest/1668/submission/154109773
what's wrong?
I think ans is not large enough, LONG_MAX is the same for INT_MAX
I DON'T UNDERSTAND, WHY LONG_MAX CAN CHANGE ITS VALUE TO INT_MAX
Because long is int in another name (It returns to the history of language)
LLONG_MAX is the maximum long long in c++
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?
Can someone tell me the test case fails for this code 154119937
i request the setters and testers to find out the same codes and penalise them
can anyone explain test case 2 of problem C of Div2? Shouldn't the answer be 8?
7
1 2 1 2 1 2 1
b-> [−3, −2, −1, 0, 1, 2, 3]
steps 2 1 1 0 1 1 2
No you need $$$3$$$ steps for the first and last element. You can only change $$$b_1$$$ with $$$a_1$$$.
Can somebody help me find out why my solution get TLE in pypy3, but accepted in pypy3-64 with only 514ms? 154083919
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!
Same here, and what a shame that I only realized the pypy3-64 existence in the last 10 minutes of the contests
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!
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.
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.
SmallscoreForces
Nice round, thank you!
sus!!!?? His/her previous solutions got skipped and this contest's solutions also look sus! MikeMirzayanov
Obfuscation is bad
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
when will the cheaters be removed.
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)
Cheaters in div2 160-200 places. I checked about 10 accounts, all of these registered five days ago, all have the same code
here comes the cheaters on page 2 HtePhANA_ affianced.leon claudette_thomas_00
and sus?
peti1234 for div2 problem B, my solution get an AC.
but It should be wrong based on this test case:
$$$n \geq 2$$$, so this is an invalid test.