Hello Codeforces,
I invite you to participate in Codeforces Round 785 (Div. 2) which will be held on Apr/30/2022 17:35 (Moscow time). The round will be rated for participants of Division 2 with rating strictly less than 2100. But as always, the participants of Division 1 are welcome to take part out of competition.
You will be given 6 problems and 2 hours to solve them. Moreover, there will be atleast $$$1$$$ and atmost $$$1048576$$$ interactive problems. So, you are advised to refer to the guide on interactive problems in case you are not familiar with them.
I would like to thank the following people for their contribution to the round:
- Artyom123 for his amazing coordination, helping me throughout the preparation of the round and translating the statements.
- Um_nik, Monogon, kclee2172, TheScrasse, yash_daga, Sad_reacts_only, AlperenT, Utkarsh.25dec, abhidot, PR_0202, towrist, Rubalien, hritik31, snowysecret, alok_k6618 and harsh2804 for testing the round and providing their feedback.
- MikeMirzayanov for the great Codeforces and Polygon platforms.
- NEAR for supporting this round, details can be found in this post.
- You for participating.
This will be my second Codeforces round and based on the feedback by participants on Round #730, I have implemented the following changes:
- The round will have no theme. I have tried to keep the problem statements as short and to the point as possible.
- The pretests have been made stronger (specifically, more pretests have been included).
- I have tried to keep the samples and their explanation as useful as possible.
- No floating-point precision issues this time.
- The I/O constraints for the interactive problem(s) have been kept low to provide a fair ground to the languages with slower I/O.
The score distribution will be released strictly before the round and the editorial will be released strictly after the round.
Good luck and have fun!
UPD: The score distribution is $$$500-750-1500-2000-2750-3250$$$.
UPD: Editorial
UPD: Congratulations to the winners
Div. 1 + Div. 2 -
Div. 2 -
First solves -
| Problem | Participant | Time |
|---|---|---|
| A | A_G | 0:02 |
| B | Geothermal | 0:05 |
| C | quailty | 0:03 |
| D | BalintR | 0:16 |
| E | zsxdcfv | 0:27 |
| F | ksun48 | 0:11 |
As a taster.. I want to assure the round is well balanced, sweet and spicy
By looking at your pfp, i can confirm that you are a taster :P
Yes I do.. "easly morning dream" is always right!
As a tester, problem statements are short and all have expected rating less than 1048576.
Do you mean delta <= 1048576 but > 0?
:)
As a tester still waiting for jay to set a round without an interactive problem
As a tester, I agree that no powers of 2 were harmed.
JaySharma1048576 orz
As a tester, I must say that it was quite hard to solve those 1048576 interactive problems.
As a tester, I solved at most $$$1048576$$$ interactive problems.
I care about tags :)
Oh no, mathforces again. Btw how did Mike let the "cheater" set a round again?
As a tester, good luck.
No powers of 2 were harmed but testers were harmed with the powers of 2.
The number 1048576 still haunts me :P
Debugging interactive can be hard. Need this feature(google code jam has this) : https://codeforces.com/blog/entry/102256
This most probably will not be implemented on codeforces as their team is small and this feature is not very important. Better to setup your own environment. -is-this-fft- blog will be helpful for this.
It seems to be interesting contest
I really liked all your interactive problems. Looking forward to this round as well.
Indian Round Let's Go!...
Hey Jay! Good to see you back again with your interesting rounds!
No powers of 2 were harmed during the making of this round.Not even $$$1$$$?
Why is 1048576 occursed frequently?
Excited for an Indian Round !
Hoping to retrieve my lost rating :)
Hopefully I reach specialist today
Hopefully I reach specialist today
You did actually. Congrats :yayy:
.
.
Super excited for this round !!
good luck everyone
Problem D IS SUCH A PAIN
Congrats for expert
I really dislike Problem B. Problem B took me more than 1 hour, while I solved Problem C in less than 20 minutes. Proving that you algorithm works for Problem B is not straightforward, and while I got the main idea after a few minutes, I spent the entire hour trying to prove that it is true. I was extremely tempted to try proof by "accepted/try and see" vs mathematically proving a solution actually works, especially looking at the number of accepted submissions. At least I feel this shouldn't be encouraged for div2AB.
One might argue that I just suck/am slow at proving things, which is fair, but I honestly don't think I'm that much worse than an average Div2 contestant in my proof skills.
Tf were you proving?
Let $$$prev(i)$$$ denote the maximum index $$$j<i$$$ such that $$$s[j]==s[i]$$$. Then $$$s$$$ is balanced if and only if $$$s[prev(i), ..., i]$$$ is balanced for all $$$i$$$.
shit happens. i solved ab in 14 mins and couldnt handle with c lol
You can just check for all pairs of letters that condition is satisfied with prefix sums in n * 26^2, and there is nothing to prove there.
Did that pass? The time limit was $$$1$$$ second for $$$2*10^5*26*26 = 135200000$$$ which I thought wouldn't pass. I ended up with $$$O(26n)$$$ by noticing a counter example can always start and end with the same character.
C++ is very fast so it will probably pass.
I'll try it once system tests are done. I thought of this idea literally 2 minutes into reading the problem, but since I thought the general rule was $$$10^8$$$ ops/second, I thought it wouldn't pass..
it passed i tried it
Can I get a link to your submission? I'm getting TLE
Edit: nvm, Got it AC by doing some low level optimisations. That's pretty surprising that it passed.
https://codeforces.com/contest/1673/submission/155416119
another way was calculating total number of distinct letters in the string (let it be) k, and for all 1 <= i, j <= n, s[i] == s[j], j > i you can check if j — i >= k. it must be true for all such pairs
my solution was to count the number of distinct characters. Now let's say the string s has 4 distinct characters. Then the first 4 characters must be some permutation of these 4 characters, and every set of 4 consecutive characters after must be the same permutation. EX: abdcabdcabd
That passed the pretests? I thought of that and then realized the counterexample, what if the string doesn't have a permutation of the $$$d$$$ distinct characters as a prefix of length $$$d$$$ and instead has something like $$$abbabcabcabc$$$.
but for this case, the answer is NO, obviously, isn't it?
It's no because of the substring 'bb'. Here the difference between the number of b's and a's is 2
only need to check if distance of two adjacent same characters is the number of distinct characters in s.because each of them should appear exactly once in this substring.
Thanks, I didn't think of that. I ended up checking adjacent same characters, but brute-forcing the count for characters in the range using presum table.
How to implement that in O(n)?
Check out my solution, if you want. I had the same approach. 155410182
UPD: It is very bad implementation probably, but idc :D
I like your implementation. Here is another way to do the last part of your code.
Oh yeah... This looks much more easier, thanks :D
Probably, you choose a harder approach. My approach:
Let's say the string has k distinct characters. Then the first k characters of a must contain all distinct characters, otherwise frequency of at least one letter in first k characters of string will be >= 2, making it imbalanced. Then, this substring of prefix must repeat, if it doesn't you can take [2...k+1], it will be imbalanced.
How can I solve problem D?
How do you solve problem C. I tried to do a knapsack variationy sort of thing, but it counted the solutions 1 3 1 and 3 1 1 as different.
you can probably google it by searching "unbounded knapsack"
similar problem: CSES Coin Combinations II
This is simply solvable. Assume $$$p$$$ is a set of weights. Then usual knapsack algorithm is
Do instead
Could you please explain why this works though?
The idea is that once you pick a weight w[i], you make sure that you pick all possible amounts of it now so that you don't pick the w[i] again in the future. That way you wont have a case like 1,3,1.
Also instead of
for (int i = 0; i < n; i++) if (i + j < n) { ... }you can do
for (int i = 0; i+j < n; i++) { ... }(not important for correctness or speed)
Backpack Counting.
Perhaps I overcomplicated the casework in D but come on... This problem was just painful. On another note, does anyone know why mixing
putsandcoutresults in a wrong answer?Probably, you did not use flush in $$$cout$$$. Then they alternate flushing and produce mess in output. For $$$cout$$$ it is $$$cout.flush()$$$ and $$$cout « endl$$$. $$$puts$$$ always flushes.
That's probably it (since I'm not using
endl). I'll be more careful next time (thank god I was able to suspect thatputswas the problem).always use same output method.
You are using
ios_base::sync_with_stdio(false), which does not preserve the order of output streams.I literally submitted problem D 2 seconds before the contest ends but it said the contest is over... I forgot to take the answer mod 1e9 + 7. So sick of crap like this...
ModuloForces
In problem D, let say for a common difference d and first number c, how do you find smallest number in that sequence which exist in sequence B but not in sequence C?
Trash Indian Round. Terrible problems : C , D . Maybe F is a good one , but generally a trash round.
C wasn't that bad actually, albeit a little standard.
littlecompletelyTotallllly standard
I'm confused, are Indian rounds trash in general? or this particular round is trash among all the Indian rounds?
how to solve E and F? E: I know from one index, at most 20 power could be extended. But don't get how to deal with K.
F: The goal is to find a good way to assign 0~1023 to all the cells, and edge connecting u and v is u^v. Gray code will do.
$$$2^5$$$ x $$$2^5$$$ gray code is yielding a sum of approximately 84k
You should use the 0, 2, 4, 6, 8-th bit for one dimension and 1, 3, 5, 7, 9 for the other dimension.
For problem E, consider for a certain $$$(i, j), i \le j$$$, how many times does $$$A_i ^ {A_{i + 1} \cdots A_j}$$$ contribute to the final answer, when putting XOR both between $$$A_{i - 1}$$$ and $$$A_i$$$, and between $$$A_j$$$ and $$$A_{j + 1}$$$.
We just have to count the number of times $$$pow(l,l+1,\ldots,r)$$$ appears in the final expression. As you said, $$$r-l \leq 20$$$ holds since we take the answer modulo $$$2^{2^{20}}$$$, so we can brute force all pairs.
The sequence will look something like $$$\ldots A_{l-2} ~?~ A_{l-1} \oplus A_l ~\hat{}~ \ldots ~\hat{}~ A_r \oplus A_{r+1} ~?~ A_{r+2} \ldots$$$. We just need to count the number of ways to fill in the $$$?$$$ such that we satisfy the number of $$$\hat{}$$$ being more than $$$k$$$. This is simple combinatorics and we get some expression of the form $$$\sum\limits_{k=0}^m \binom{n}{k}$$$.
Remember we only need this expression under modulo $$$2$$$, also we will only require the value for about $$$20$$$ values of $$$n$$$ since $$$r-l \leq 20$$$, so just do prefix sums.
Btw, you can find $$$\binom{n}{k}$$$ under modulo $$$2$$$ easily as $$$\binom{n}{k} \pmod 2= 1$$$ iif $$$(k \& n)=k$$$. We can show this using Kummer's theorem, Lucas's theorem or just staring at an image of a Sierpiński triangle
Found where I was stuck...Thanks very much.
Problem C is similar to this problem
Tests for problem B is very weak. My submission https://codeforces.com/contest/1673/submission/155406728 fails on test
of which the answer should be NO, but this code prints YES.
The pretests have been made stronger (specifically, more pretests have been included).Are you sure for problem B?:(
:(
So much 2 in problem E...
Can somebody please tell me what's wrong with my approach in C:
I made an array of all palindroms from 1 to 1e5 (v) (v[j] — j-th palindrome starting from 1) I also made a 2-dimensional array dp, when for each i<=4*1e4 and j that j-th palindrome (lets say v[j]) (starting from 1) is no more than 1e5, dp[i][j] = number of different sums of palindromes which are equal i and in each sum all the palindroms used are equal or less than v[j]. I filled this array for i from 1 to 40000
for each i I found certain l that v[l] (l-th palindrome) <=i, but v[l+1]>i;
Let's notice that dp[i][j] (v[j]<=i) = dp[i][j-1]+dp[i-v[j]][j], because for each sum of palindromes equal i, and each palindrome <=v[j], either in this sum is included v[j] as a palindrome, and all the other palindromes are <=v[j], (dp[i-v[j]][j] sums in total), or v[j] is not included => all the other palindromes are <=v[j-1] (dp[i][j-1] sums in total).
since dp[i][0] = 0, then for each 1 <= j <= l dp[i][j]=dp[i][j-1]+dp[i-v[j]][j]. if j>l, dp[i][j] = dp[i][l], because i < v[l+1] <= v[j] (therefore in each possible sum of palindromes equal i every palindrome is <=v[l], and dp[i][j] = amount of all possible sums of palindromes equal i = dp[i][l].)
After filling our array for each 1 <= i <= n, we can print dp[n][r], if n < v[r] <=1e5 and it will be our answer, (dp[n][r] = number of sums of palindromes equal n, and therefore each palindrome <= n < v[r], so dp[n][r] = amount of all possible sums).
I will be glad if someone can explain what's wrong with my approach. Or is it correct and my realisation is wrong?
I looked at your solution. Your dp is correct, but you output the dp[n][i], such that it has the maximum value (since it's in modulo 1e9+7 that would be wrong). Just output dp[n][590] and that would pass the testcases
Thank you so much, AC now)
(OMG i can't believe I made this mistake, i'm such a moron. No words for that)
Technical question: The API was unavailable while contest. I this something that will happen now more often intentionally, or a coincidence?
I use some tooling that uses the API to parse problem statements, tests etc.
I met the same situation: cf-tool warns
Cannot find csrf, and I can neither login nor parse problem statements.What's an upper bound on the number of divisors of $$$n$$$?. I mean, is it something like $$$2$$$ to the power of [number of smallest prime numbers with product up to $$$n$$$]? For example if $$$n = 10^9$$$ I can take up to $$$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29$$$ so is $$$2^{10}$$$ a safe upper bound? I was a little bit confused about iterating divisors in problem D, so I didn't even try, but I guess that's what I had to do.
It's $$$2 \sqrt n$$$ but on average it's much lower
Ok, I get it, for some reason I was trying to do better unnecessarily, we just iterate from $$$1$$$ to $$$\sqrt{n}$$$ and check if it's a divisor, that's enough here. I feel a bit dumb now but happens. Thank you.
Cubic root is also okay: https://codeforces.com/blog/entry/651
It's $$$O(log(n))$$$ on average.
look up OEIS
Just asking: what is the point of making F interactive? I don't think there exist offline solutions since you can just ask all cells anyway.
Even if I ask the queries offline, the grader still needs the length of the roads to generate the queries which itself needs the problem to be interactive.
I found problem C very hard to solve. At first, I tried to formulate the number of ways to create the integer using only 1-9, but got stuck there. Can anyone please tell me how to approach this kind of problem and solve it?
You have to realize that there are only ~500 palindromes less than 4e4. So you can simply do dp on this where dp[i] is the number of ways to get sum i. The dp method is mentioned somewhere above.
My submission: 155444840
My thought process (and I think pretty much everyone else's) was, 'This $$$n \le 4 \cdot 10^4$$$ constraint is a bit weird, surely there must not be too many palindromic numbers anyway', so I quickly generated the palindromes and saw there were around $$$500$$$, so the constraints were enough for a knapsack, and I just had to be careful to first iterate the palindromes in the knapsack to count only ordered sums.
You can find all the palindromes less than 4e4 with a simple python script. There are less than 500. after that, Visit the land of CSES Problemset, and find the one named Coin Combinations II. It will guide you.
Generating all palindromic numbers for C was available online on GFG https://www.geeksforgeeks.org/generate-palindromic-numbers-less-n/
I'm pretty sure that you can use google, also it's not even that hard to generate palindromes
oh
Although your submission outputs the correct answer, it has a non-zero exit code, with stack smashing errors.
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
Glad to be green again :D Thanks for this amazing contest!
If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.
If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
The problems were so interesting and fun. Unlike other contests, AB was really good. I like them
When you find out that all div2 winners are alt accounts
Really? just 2 seconds? Humans can do that?
That's what she said :(
in this submittion: https://codeforces.com/contest/1673/submission/155426364. I write vector cnt(26,0); in line 23. then I have Runtime error on test 11 but I write int cnt[26]; for(int k=0; k<=25;k++) cnt[k]=0; then there is no error. I want to know WHY???
x[s[i]-‘a’]++
cnt[k+'a']
I am avinash204, I am writing about the C problem of the contest. It happens that my solution coincides with another solution. The C problem was similar to a problem that I have done before on CSES (https://usaco.guide/problems/cses-1636-coin-combinations-ii-ordered/solution) and I happen to use the some part of the solution which I submitted last time on CSES. The AI has detected my solution to be coinciding with another user. Please look into the matter.