Hello Codeforces and welcome back to another div2 round.
YeongTree and I are excited to invite everyone to participate in Codeforces Round 851 (Div. 2), which will be held on 09.02.2023 17:35 (Московское время).
This round is rated for the participants with ratings strictly lower than 2100. You will be given 6 problems and 2 hours to solve them. All the problems are authored and prepared by YeongTree and me.
We would like to thank
- Arpa for excellent coordination and help with prepration.
- Alexdat2000 for Russian translation.
- blobugh, as_dfsdf, Kawaii2DIdolOfGSHS, nlog, Ryute, Konijntje, hanbyeol_, Physics07, jjang36524, OctaneC8H18, ahgus89, DELTARUNE, FD..LH..lloyJ, andyandy, PUFL, Pratyush1606, PUPA, Justice_Hui, garam1732, windva, culver0412, nor, maomao90, MagentaCobra, dorijanlendvaj, RetiredPlayer, mejiamejia, AquaMoon, mjhmjh1104, qwexd, ayhan23 for testing and feedbacks.
- MikeMirzayanov for great systems Codeforces and Polygon.
The score distributions will be updated later.
UPD1: Score distribution: $$$500−1000-1500-2250−2500-3000$$$
UPD2: Congratulations to the winners!
Overall:
Rated participants
AC submissions at the last second
UPD3: Editorial is out
Auto comment: topic has been updated by azberjibiou (previous revision, new revision, compare).
Auto comment: topic has been updated by azberjibiou (previous revision, new revision, compare).
as a tester, qwexd ORZZZZ
As a tester, the problems were really good.
Participants, please enjoy the contest!
Similar names (ᗒᗩᗕ)
thanks aftors
Problem C is trash. Change my mind...
The problem with number C is that it's not called "trash", it's called "high quality".
As a tester, I enjoyed the round and the statements were brief and clear. I hope to see you on the scoreboard!
As a tester, this was the best contest I have ever seen.
as a tester, this was the best contest I have ever seen.
As a participant , hoping this would be the best contest of [Contests I have ever seen + this contest]
As an apparent tester (I don't remember testing this round recently), I'm sure the problems are good :P
Good luck to everyone!!!
Good Luck for every Candidate Master to promote to Master!
OMG South Korean setters, good mathematical problems coming on the way :)
Hahaha as a tester I cannot say about that now, but good luck if you participate!
hahaha haha hahaha haha hahaha haha :(
Haha nicely predicted.
Omg announcement shorter than tourist round
This contest may be a bit late, I guess I fell asleep at that time.
good luck everyone!
As a tester, I tested this round in the period about when I was orange for the first time.
Problems are nice tho!
My first contest was tourist round. I solved 1st 2 problem and earned 389 rating. This will be my 2nd contest .
I will skip an academic seminar in my university and participate in this round.
As a participant, I confirm that i will participate.
Sometimes I really want to skip school.
Please down me, thx.
As a tester, I enjoyed this round. Good luck!
Thanks for your excitation to invite us to participate in round !
Auto comment: topic has been updated by azberjibiou (previous revision, new revision, compare).
Good Luck and Have Fun!
I will skip an academic seminar in my university and participate in this round
Wishing you all a positive delta!!
Best wishes for everyone
Worst Contest I have Ever Seen. What are these strict time limits !?!?
Me after solving C
Same lol
Can you please tell your approach on C?
same
is that a pattern finding round?
Mo
Starting with problems A Motivation 100 to 50 B Motivation 50 to -100 C Motivation -100 to +50 Depression enters :)
How to solve E? Is this some dp? maybe we can precompute the maximum index, i can jump to from index j while keeping the sum of elements from i to j >= 0 . Am i thinking in the right direction ?
no you need to solve A+B first
I thought of doing a segment dp like:
dp[L][R][0] — ans for [L; R]
dp[L][R][1] — ans for (L;R]
dp[L][R][2] — ans for [L;R)
dp[L][R][3] — ans for (L; R)
But had some troubles with calculating dp[L][R][0]. Other states are easy to calculate
DP on segment tree with coordinate compression on prefix sums. Iterate from 0 to n-1, then answer for $$$[a_0, a_1 .. a_i] = max(DP_{minprefixsum}....DP_{prefixsum_i}) + i$$$. Then update $$$DP_{prefixsum_i}$$$ to $$$currentanswer - i$$$ if $$$DP_{prefixsum_i}$$$ is not better than the current answer.
Might be an unpopular opinion, but I think all problems were very good and interesting. Congrats to the authors for a beautiful contest. I enjoyed doing the contest very much. Thanks!
Did someone constantly get wrong answers on problem B?
it's me, huh! My final ratings will be negative. But next contest, i will gonna hit harder..
You probably converted the number to string and left a leading zero on during the output (not converting it back to int). It would fail for 101, where you would output 01 and 100. Just my guess. You would have to delete all the leading zeroes instead of just the first one
How to solve C?
How to solve B?
Distribute digit by digit.
Divide n into 2 numbers evenly. One number may be 1 greater than the other. Compare the 2 numbers digit by digit. The digits are either (1) same, (2) 1 vs 0, or (3) 0 vs 9. Keep track of the sum of digits of the 2 numbers so far. In case 3 above, distribute the 9 as 4 and 5 or 5 and 4 depending on the current difference of the sums of digits so far.
E looks standard. Can it be solved by dp with d&c?
upd: i think i overcomplicated it
dp[i] = max(dp[i — 1], dp[j] — j + i) while sum(j + 1 ... i) >= 0 (j < i) using map to keep (sum[i], dp[i] — i) increase.
C is too hard
The difference between C and D was massive.
did anyone else also got wrong answer on test 5 in E
yeah me
What was your approach.
I used binary search on previous minimas of sum<=sum[i] if sum[i]<0 for getting subsegment with maximum length ending at i.
Yes, i did the classic dp like LIS but get WA on test 5 don't know why
I know now i forgot about dp[i] = max(dp[i], dp[i — 1])
Hello i am also doing same mistake in other method but not getting ig as i am getting same 126 as answer in test case 5. It will be a great favour if you please look into it
I think that this round had very interesting problems with pretty beautiful possible solutions. Thanks for the contest!
My solution to problem E:
First, create the prefix sum array $$$p_0 = 0, p_i = a_i + p_{i-1}$$$ and compress it. Let $$$dp_i$$$ denote the best answer for the prefix upto element $$$i$$$. Suppose the last segment we take containing $$$i$$$ goes upto $$$\ell+1$$$ and misses $$$\ell$$$. Then $$$\ell < i$$$ and we must have $$$p_i \geq p_{\ell}$$$, and the best possible answer in this case would be $$$dp_{\ell-1} + (i - \ell)$$$. To efficiently compute these values, create a max segment tree over the compressed $$$p_i$$$ values and each time we compute $$$dp_i$$$ as $$$i$$$ plus the maximum over the segment $$$[0, p_{i}]$$$ in the segment tree and after performing $$$dp_i = \max(dp_i, dp_{i-1})$$$ (in case we don't take $$$i$$$ in the optimum answer) we update the $$$p_{i+1}$$$th location by maximising it with $$$dp_{i} - (i+1)$$$. That's it, done. Overall solution works in $$$\mathcal O(n \log n)$$$.
https://www.youtube.com/watch?v=1jbhevleu-Y Copy of Problem B...Do Something
ABCforces
how to solve C
assume consecutive sum of n pairs is : k, k + 1, k + 2, ..., k + n — 1. If u add everything u have k*n + (n — 1)*n / 2. Which should be equal to 2n * (2n + 1) / 2 (sum of 1, 2, ..., 2*n). Equate both terms and you will get k = (3n + 3) / 2. Now figure out the pairing part by yourself, it's not that hard.
Asks for a solution, gets "figure out xyz by yourself, it is not that hard".
Hint: If you cannot figure out the pattern, try to write a brute force solution for small cases.
haha, I did until this step, it's intuitive. I couldn't figure out the pairing part.
I brute forced for n=7 and the find the answer (4,8) (5,9) (6,10) (7,11) (1,12) (2,13) (3,14) then we are done.
hello sir, I am unsure of how to write a brute force algorithm for this question. Do you think you could help me? Thanks.
my total score : 390-8*50.. It looks very difficult, was this contest really hard?
It's normal for a new account to solve only the first (or even zero) problem is the first contest. You just need to take more contests to get familar with the process of CF contests.
Problem D cost much time for me and I didn't have enough time for E.
2D dynamic programming with 6 different arrays to maintain (RL, RL_sum, LL, LL_sum, LL_cnt, LL_cnt_sum) is too easy to make mistake at some details. I've spent much time to find a bug that I allocated too much space on the stack for 2D arrays (using something like ll RL[n][n], where n=3000) instead of declare them as global variables.
define 6 2D arrays for DP:
RL[j][k]: The answer consider the cases that the rightmost 2 dots are j, k, and j moves to right (when there are only 2 dots, or the i-th dot is on the left of j, and dist(i,j)<=dist(j,k), which is equivalent to, x[i]>=2*x[j]-x[k]).
LL[j][k]: The answer consider the cases that the rightmost 2 dots are j, k, and j moves to left (when there are more than 2 dots, and the i-th dot is on the left of j, and dist(i,j)>dist(j,k), which is equivalent to, x[i]<2*x[j]-x[k]).
LL_cnt[j][k]: The number of sets which containing more than 2 dots, and the rightmost 2 dots are j, k, and j moves to left.
XX_sum[j][k]: sum(i=0...j)XX[j][k].
Then for each pair of (j, k) where j<k, we use binary search the smallest i0 that x[i0]>=2*x[j]-x[k] (if there's no such i0 then i0=j),then the DP formula is:
LL[j][k]=sum(i=i0...j-1)(RL[i][j]+LL[i][j])
RL[j][k]=1+sum(i=0...i0-1)(RL[i][j]+LL[i][j]+LL_cnt[i][j])
LL_cnt[j][k]=2^i0*(2^(j-i0)-1)
The final answer is sum(i=0...n-1, j=i+1...n-1)(RL[i][j]+LL[i][j]).
Dynamic programming, where the formula is
, which is equivalent to
$1$
where $$$sum[j]$$$ is the prefix sum of $$$a$$$. Then we can solve the problem by segment tree (since $$$sum[j]$$$ can be large, we need to sort $$$sum[j]$$$ first, and give them a new identifier from $$$0$$$ to $$$n-1$$$).
Update: Now my submission 192969220 has been accepted.
Observe that the answer is equal to the number of adjacent points which moves toward each other.
We may check every two points $$$x_l,x_r$$$ and count the number of subsets in which $$$x_l$$$ and $$$x_r$$$ are adjacent and move toward each other, which is equal to $$$2$$$ to the power of $$$(L_{l,r}+R_{l,r})$$$, where:
$$$L_{l,r}$$$ represents the number of points satisfying $$$x_r-x_l<x_l-x_p$$$;
$$$R_{l,r}$$$ represents the number of points satisfying $$$x_r-x_l\le x_p-x_r$$$.
for a fixed $$$l$$$, $$$f(i)=L_{l,i}$$$ is monotonic. Similar for $$$R$$$.
The code for the solution above is very easy to implement.
[deleted]
Why are you not considering point which can possibly lie in between xl & xr in the subset? For ex: If x[]={1,13,14,20} and if l=1 & r=4, then by your soln ans would be 1 ({1,20} would be the only such subset), however there could be one more subset ({1,13,14,20}) as well, here also 1 and 20 would meet each other.
for {1,13,14,20}, although 1 and 20 meet each other, they end up in the same place as 13 and 14's. So it is calculated when l=2 and r=3.
Ok, so when two particles collide, they just stop there. I thought that the colliding ones just disappear!
It's the sum over all $$$(l,r)$$$ such that $$$x_l$$$ and $$$x_r$$$ meet each other and are adjacent.
Same approach. It is a miracle that this came to my mind during the time of contest. Finally i can see some improvement.
Thanks to this contest i reached specialist rating.
I didnt use DP. I just iterated over every pair $$$(i,j)$$$ and found the number of subsets of points such that $$$i$$$ and $$$j$$$ meet each other. The idea and code are both simple.
Excellent solution. Comparing to yours, my solution can even be regarded as wrong answer.
I see that you've used this header file
#include <atcoder/modint>
Is it supported in codeforces?
No, it is only available in Atcoder, not in codeforces. My actual submission looks like this
But the AtCoder Library GitHub repo provides a python script that takes a C++ file and replaces the atcoder header file with the atcoder library, enabling it to submit to all platforms. I also use the VSCode extension called CodePal which automates this process.
Thank you. I'll take a look
Can you please explain your dp approach for D . I tried doing this by dp but failed and my obervation skills suck , hence wasnt able to do the question the other way too.
We consider what would happen if we add a new dot at right. We call the previous 2 right-most dots i, j (assume there's >=3 dots in the set, because set with only 2 dots is trivial). In the previous set j would move left since it's right-most dot, and i could move left or right. If j still move left after we add a new dot, the number of final points will not increase. But if j move right, there's 2 situations: if i moves left (we call this situation LL), then it would like RR...LL --> RR...LRL, we can see there's one more final point (by the "RL" we've created), and if i moves right (we call this situation RL), then it would like RL --> RRL, where number of final points remained same. Therefore we can get the transition formula. (don't forget to consider situations of RL when there's only 2 dots in the set)
Also this DP approach need to store prefix sums for optimization. See this comment for a simpler solution.
Was D just a DP on pos[previous][current] then looping through [current+1, n) to try placing the next particle?
The observation there I believe is that for all values <= a[i] + (a[i] — a[p]), the direction is left, while the rest are right, so you can do some casework there to add on that subarray after precomputing prefix sums (the number of dots is equal to the number of adjacent RL's that show up in the final subsequence), but I had a stroke implementing ;-; does anybody have a simple enough implementation of that idea?
Wouldn't this be $$$n^3$$$ ? Each of your $$$O(n^2)$$$ values take some $$$O(n)$$$ time unless there is a trick I am missing.
I couldn't even get the n^3 working cuz I'm bad but I think that the recurrence would look like
Then since every single transition is just solve(i, j) + (a bool) in either case, then you split it up into the ranges whether the bool is true or false with bsearch. The second range never gets added to, and the first range you would casework and then multiply by the length of that range.
So in the end the transition is DP += (sum of everything from DP(i, [j+1, n) )) + (len of good range) * (caseworked boolean)
(though again I didn't get the casework working so I'll still need to work out the conditions)
Though it seems like other people had easier solutions ;-;
had a similar observation but could not come up with the implementation ;(
I have a simpler approach, iterate over i,j (i<j), for every i,j find out a,b such that a<=i,j<b and if every element between [a,b) is not present in a subsequence (except i,j) then $$$a_i$$$ moves towards $$$a_j$$$ and vice versa. Also, $$$b-a$$$ should be minimum so that we exclude minimum elements. Now add $$$2^{n-(b-a)}$$$ to the answer.
Code: 192957360
Let's assign directions to the dots in some subset, they will look like:
(RR...RRLL...LL)|(RR...RRLL...LL)|......|(RR...RRLL...LL)
So the number of distinct endpoints is the number of "LR" adjacent pairs + 1 (to account for the first block). So we can iterate on every pair $$$(i,j)$$$ and count in how many subsets they can exist as an adjacent LR pair.
Based on $$$x[j]-x[i]$$$, we can know how many dots before $$$i$$$ can be directly before $$$i$$$ in a subset and how many dots after $$$j$$$ can be directly after $$$j$$$ in a subset. If $$$[l, i-1]$$$ is the left range and $$$[j+1, r]$$$ is the right range, then the left subset counts can be $$$2^{l-1}$$$, $$$2^l$$$, ..., $$$2^{i-2}$$$, and the right subset counts can be $$$2^{n-r}$$$, $$$2^{n-r+1}$$$, ..., $$$2^{n-j-1}$$$.
So, add $$$(2^{l-1}+2^l+...+2^{i-2})\cdot (2^{n-r}+2^{n-r+1}+...+2^{n-j-1})$$$ to $$$ans$$$. Make sure to initiate $$$ans$$$ with $$$2^n-n-1$$$ to account for the first block in all the subsets.
Submission
B was much more difficult than C In B only case we need to worry about is n%20==19 but even after that it was more of implementation problem than maths which it seemed to be initially
you can solve B with binary search
Could you tell how please?
Since the guy with more elo literally posted the same answer as mine and my comment is being ignored because of it, I might as well just remove it.
you're too sensitive for these things
Yes I am, because it's happened before. Good thing it was a 5 minutes comment and not a full editorial.
$$$B$$$ can be implemented simpler. Iterate over digits. If digit is even, split it equally for both answers. If digit $$$x$$$ is odd, add $$$x / 2$$$ to first answer, $$$x / 2 + 1$$$ to second answer and then swap them.
At the end remove leading zeros.
Example: 16934 -> 1**** + 0**** -> 13*** + 03*** -> 035** + 134** -> 1342* + 0351* -> 13422 + 03512
Feels like massive cheating on C, I might be wrong but it feels like it.
Cheating is happening too much nowadays..
i guess it is for both B and C, B was much harder than c
In what universe is B harder than C, only if you cheated cause code might be more trivial for C. To figure out idea for B it takes less than 50 seconds.
What is test 2 for B?
i think it could be 100,1000,10000 etc
i think its easy to guess for these nos n/2,n/2=> {50,50},{500,500}....
different emplementation
guessforces
more like observation forces
Any proof for C I solved it by just some observations
if n is even then "NO". else sum of first pair should be (3*(n+1)/2). proof: S1 + (S1+1) + (S1+2) + ....... + (s1+n-1) = 2n*(2n+1)/2
The worst round
I also wanna say this... but to be honest the problems are fine and I'm just unlucky.
For me too :(
why? D was alright but maybe D > E. I guess A,B were easier than usual for sure.
Imagine asking how to solve D and getting -13 ^D
It was great PatternForces Round <3
I wish C was 1500-1600, but unfortunately it's more likely to be 1200
Anyone know why my sol for D is wrong?
dp[i] stands for sum where i is chosen, and tot[i] is total of chosen & not chosen
I wast stuck in problem C for approximately 2 hours, In problem C multiple kind of pairing was possible so it must be mentioned in the question that we can output any valid answer. I am not talking about order of pairs... actually you can pair any number with 2 values and accordingly I found 2 valid answer exists for each odd number.
Any Hints For D? I Was Thinking In A DP Direction :(
the main observation is that the distinct points increase when $$$ith$$$ index moves left and $$$i+1th$$$ index moves right. Now try to figure out the contribution of each $$$i$$$ seperately by fixing the position that moves left and the position that moves right.
Toooooooooooooo much Cheating
Why do you think so?
Can anyone explain E for noobs?
Why is answer no for even n in C?
s, s + 1, ..., s + (n — 1) are sums. So s * n + n * (n — 1) / 2 = 2n * (2n — 1) / 2, so s = (3n + 3) / 2 => n % 2 == 1
Looks like I need to get some sleep. Thanks tho
s, s + 1, -- s + n — 1
suppose they are sum of pairs as given in problem
if we put
s + s + 1 + s + 2 — = 1 + 2 -- 2n
we get
n * s + n * (n — 1) / 2 = n * (2n + 1) we get
s + (n — 1) / 2 = 2n + 1
s = 3 / 2 * (n + 1)
for s to be integer n + 1 should be even
An unbalanced round. I got ABC very quickly, but couldn't come up with a fast enough solution for D in time and didn't attempt further problems. I won't say that the problems were bad because they weren't (C was just guessing a pattern, didn't like it that much; others were good). I just think that there should've been a 1600-1800 rated problem between C and D. But the round was still nice.
yea, I agree. Maybe A,B,C could've been made slightly harder to ease up the gradient.
Actually had more trouble with C than F haha.
solved D during the contest, but forgot that modular arithmetic template takes $$$O(\log n)$$$ to calculate $$$2^n$$$... So got TLE couple of minutes before the end after simply rewriting formula I got on paper :(
contest submission: https://codeforces.net/contest/1788/submission/192959799
upsolve submission: https://codeforces.net/contest/1788/submission/192968394
Great contest with good problems , thanks!
Great contest, and super fast rating changes, wow! Absolutely loved all the problems that I read (A-E)!
Also, while I understand the need to have tight TLs on D, as $$$n^3$$$ solutions were to be rejected, I'm slightly irked by the fact that my Java submission failed despite being $$$n^2log(n)$$$. Anyway, that was to be expected since I was using TreeMaps, and Binary Search is understandably faster. So yeah, happy to have learned one more thing :)
Great contest with very clear statements!
ok thanks
The product of the array can go up till pow(2,1000) which is way too large to even fit in long long
Ac submissions at the last second is very nice , but i am pretty sure that last second submission of problem D by gsmdfaheem is copied. i have seen exact same code that is leaked at just 10 minutes before the contest end.
he just changed the variable names.
In B if i print 1 as 01 it consider it wrong but both are equivalent integers and no intructions are provided regarding leading zero .
stupid testing got WA 2 times.
According to me my E is working but my solution gets WA on test 5 can anyone please help me where i am lagging https://codeforces.net/contest/1788/submission/192944044
GOT AC LAST SECOND
D just 3 seconds before!!
The time limit of F is too tight. I wrote the correct solution but got TLE on pretest 58. I think it's better to decrease the value of $$$n,q$$$ to 1e5 or increase the tl to maybe 5 secs.
Problems are fun! thanks to authors :)
Can someone give a small test case on which my solution 192923926 fails?
Very very very standard problem E and F. I cannot accept that.
Weak testcase in B no. In the statement, given 1<=n<=1e9. Unconciously, I used int(as datatype) and passed the pretest. After the contest I noticed my mistake and expected to get wrong answer. But, after final judgement , my solution passed all the testcase :)
192907426
What do you think range
int
has in GNU C++17 7.3.0 (your used compiler)?You can always check in Custom Invocation smth like this:
Great contest! you can find the video editorials for problem C and D here .
hope this helps you! happy coding!
Hello! I submitted two implementations of treap in E, and the "faster" version works 5 times longer! Can anyone explain it? "slower": 193052447 "faster": 193052503 I know that "faster" gets TL on a test with
a = {0, 0, 0, ..., 0}
, but I can't realize the reason ofO(n)
height of a treap.hopeforces
Problem B. Sum of Two Numbers ***** my solution get wrong answer on test case 8, my solution is true and that makes me sure that I take this code copy and submit it again and get accepted, plz check it for my. the solution which gets wrong answer during the contest the same solution gets accepted after the contest !!!
Lately I receive a message that my submission 192896600 is same as 192935411.I cheked it and find that his solution to the problem is different from mine.I guess may be comments at the end of the code is the reason why two submissions is thougt as same.
In addition, I can give evidence that I used this template before him. mine:188824606 his:189071540
[user:KAN][user:MikeMirzayanov][user:azberjibiou]