Hello Codeforces!
SlavicG, flamestorm, MikeMirzayanov and I want to invite you to Codeforces Round 806 (Div. 4).
It starts on Jul/12/2022 17:35 (Moscow time).
The format of the event will be identical to Div. 3 rounds:
- 5-8 tasks;
- ICPC rules with a penalty of 10 minutes for an incorrect submission;
- 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
- after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
- by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).
We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.
Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth 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 1400 or higher in the rating.
Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.
Many thanks to the testers: TimDee, Gheal, Max_Calincu, qwexd, _Vanilla_,sandry24, jampm, haochenkang, tibinyte, Etherite.
We suggest reading all of the problems and hope you will find them interesting!
Good Luck!
Update: Editorial
As a tester, I tested.
As a contestant, I registered
Solution was easily guessable though
thought F was the hardest. Did you solve without seg tree?
yes
I solved it with ordered_set
i solved it with a simple prefix sum array
yea I too solved it using that it was pretty cool approach
me2
But why?
As a responsible contestant, I gave you contribution.
As not a tester, I want to test too.
No more div4 please!
Why
In the end, it's only their time being "wasted". Also, it makes some people happy. Why do you want to infringe on that?
Which of your eye have seen that I infringe on that, left or right?
For Christ's sake, don't do semantics on me.
I specifically said why would you want to, indicating the fact that it appears to be a desire of yours to discontinue this brand, not a thing you already did (the latter indicating that you would have infringed, the former describes your intention to infringe). My formulation was correct, as much as your comment stated: "(*Please*-- It hurts to be polite?), no more div4 please!", indicating a request, as per some beliefs of yours I do not yet understand, that, if taken seriously, would eventually lead to the discontinuation of this sort of rounds. As such, and I repeat, it clearly shows how it is your intention to do so, but not that, quote "[You] infringe on that,..".
No more your comments please!
barbarian_clash_of_clans
Thanks to System testing of last Div3 I will be giving this round :)
same here
Offtopic:
It would be good if there was an option at contest standings,to check country-wise standings. Like,I will select a country,it will show the ranking of all people only from that exact country.What do you think?
As a noob, Div 4 is the only time i solve at least 5 problems
As the first tester in post, I strongly recommend this round to all participants, even high rated users can find harder problems interesting, and beginners will find all problems interesting and relevant =)
why there isn't div 5 :)
I think nobody needs that except for maybe 5-year-olds.
Looks of superiority from Chinese 5 year old children *
if there will be a div 5, you will ask for div 6. :{
Then there should also be a div-6 for negative rating folks.
I wish you all good luck.
clown mentality
tested
Thank you
barbarian_clash_of_clans
Waiting for specialist to comment: Finally my first unrated round ;-;
Finally my first unrated round ;-;
Finally my first unrated round... (It is)
Finally my nth unrated round (n=1):-:
Hope for some positive delta
Excited, I hope it won't have repeated problems like the last round.
Wish all the rated participants high rating!!!
Wish all the participants high ranks!!!
deleted
Overused
my code 163576300 was accepted and didn't show up "time limit exceed on test 19" while the contest was running. Then why this happened to me after the final testing?
unordered_mapRead this..
got it thanks. But I wonder why they didn't show the error while the contest was running. If they showed the error before instead of showing accepted then I could have fixed the code.
As a tester, I recommend you to participate. The problems are really good!
Dear KrowSavcik,
This the first time I am participating in a round, I am a beginner, the problems which I am solving is between 800 : 1000, I want to know :
1- Div 4 is good to me or not? 2- If it's not good to me what Div shall I participate?
Thanks
Even though I am not KrowSavcik, I can tell you that Div.4 is the best division for you as a beginner (like me). It has the easiest problems among Div.4, Div.3, Div.2, and Div.1. You will see that you can solve more problems in some previous Div.4 round than in some Div.2 round. As the division number is decreasing, problems difficulty is increasing, and 4 is the highest possible division number.
Thanks
I saw your reply after the contest, I solved 3 problems and the fourth is correct but the I get Time limit, and one I finished after the contest finished some minutes,
but really it was a good contest, in the future I have to manage the time.
Hope all will keep continue in this good things
Best wish for all.
why downvote ?
he's not in the testers list
I tested with my alt TimDee.
hope to turn green
As a non-VIP tester, I non-VIP tested :(
betrayal of the century
Div.
this explains why he is green
As a tester, the problems were very interesting and educational. One of the best Div. 4 by far. Orz SlavicG.
I registered in this contest before the rating change of the last round i.e when I was under 1400. So, will this round be rated for me? Somebody, please confirm.
First unrated Div.4 for me, yay
as a pupil, i hope that this will be my last rated div. 4
I overslept... unfortunate.
Is there any dynamic-programming or greedy expected in div. 4?
greedy will almost surely show up.
DP might provide alternative solution paths to some problems, but I don't believe that it's suitable as a necessary tool to solve a div. 4 problem.
You can solve G with dp)
Nice
Is there any interactive problem?
They didn't emphasize it, so probably no.
Thanks for creating div 4 contests
Finally my first unrated round lol
my first unrated contest !
Im hoping to reach pupil, good luck everyone!
As an OOC contestant, I OOC registered.
As a tester, I tested, and I have to tell u this contest is great!
My top 5 finish was ruined by having to wait 2 minutes to open the problems and submit A
My rating is 1455 and I'm still showing a contestant int this round. Please fix this
I think this is because you were under 1400 when you registered for the contest. It marked this contest as rated for you then.
Hurrah! Mission A.K. accomplished!
same
Просто дизлайк раунду, больше мне сказать нечего.
My first rated round which i Aked.
Can't believe I'm that dumb, F was so simple. I hope someone hacks it.
I can see some contestants which did not have any rating and this is their first contest and they are ranked in top 10 or so. What happens to those contestants?
They'll not be rated as it is written in the announcement blog that the participant must have participated in at least 5 rated rounds to have this round rated for them!
They will be rated. They just won't be in the official standing table.
MikeMirzayanov, 3mara is telling you #unrated_plz_mike_im_sorry_ill_join_next_time.
So please make it unrated :)
Informing everyone in advance that G will be having a lot of hacks. My simple n^2 passed instead of prefix I used simple iteration and still passed lol.
Thanks for letting me know it's hackable. It's time to be a hacker ^_^
Lot of people created new accounts just to take part in this round like meyi_will_win_NOI2023, wesaco... Here I mentioned just those in top 20. Do something about it, MikeMirzayanov.
I don't think it illegal?
It isn't illegal, but if it's for example tourist with his new account or any other participant whose rating is higher than 1400 (contest isn't rated for him), then I'm getting less rating points than I should.
Yes, I agree with you, but there are so many new accounts created like this, what can we do? How can you judge if an account is specially created like this?
Sadly, this cannot be controlled.
Only trusted users can be listed in official standings, if tourist create a new account, he needs to participate at least 5 times to be included in official, otherwise he will not be included in ratings calculation. If he behave normally in his new account, he will reach red after 5 contests. The only situation that you are defeated by "fake tourist" account in div 4 is that he crashed the first five contests on purpose.
untrusted participants whose rating <1400 is rated.
Of course most of them are smurf, but some might be legit strong participants that join codeforces for the 1st time, so it's very hard to deal with this problem. Btw it also happens in higher div contest
Any hints for problem D?
First we store all string in a map, then for each string $$$s_i$$$ with length $$$k$$$ there are at most $$$k-1$$$ way to concatenate it into 2 string, and if both string exist in the map the answer is yes
Please explain me how to solve problem E 1703E - Mirror Grid
Each field is in one class together with the other fields that get rotated onto the position of it. For most fields that are 3 other fields. The center field of an odd n grid is allone.
Each of these classes can be made same by 0,1 or 2 flips.
So, we need to count the 1s in the 4 fields of each class. Thatfor we can iterate one quarter of the grid, and foreach such cell calc the position of the three other cells.
But we need to be carefull here what is a "quarter". For me it worked fine to iterate the rows from 0 to (n+1)/2, and the col from 0 to n/2.
That is, in an even size grid exactly a quarter, in an odd sized grid the rows up to including the center row, and the cols up to, but not including the center col. Also skip the center cell.
Then the rotation is in zero based indexing: $$$(x'=y)$$$ and $$$y'=n-1-x$$$
Can anyone give hints for G?
If a number is Ai, how many different values can that ultimately take? What does it depend on? Consider the question "what is the maximum score up to index i, such that I have used j bad keys so far?"
dp, the time complexity is n * log (1e9)
There is no need to use dp.
1) You don't need to buy bad keys for more than 30 times.
2) After Buying a bad key, buying a good key wouldn't give any profit. So it's better to buy bad keys in a row.
My Solution : 163889601
The bad keys have to form a suffix of the keys used. 163911931
greedy + brute force
$$$a[i]\le 10^9$$$, so there are less than $$$30$$$ floor divisions by $$$2$$$
I the half operation is used i times, on which boxes do we use it?
There is no sense in using bad key more than 30 times
wait, isn't it at most 30?
Yup my mistake
If all a[i]<k we want to use the bad operation n times for sure.
But I think that won't affect the DP state
It will give result 0 and you cannot get that result or better otherwise.
Use 1 to stand for good keys and 0 for bad keys. Brute force through all the possible states of choosing keys and choose the optimal one. Output the way to optimally choose keys in all these $$$2^{n}$$$ ways, and observe the pattern.
What is the motivation behind the problem E?
Problem E totally hanged my brain.Otherwise I would become specialist today. Damn!
I don't think we have a chance to become specialists untill we solve all including G, so i would say don't feel bad :)
HOW TO DO F?
read about ordered_set you need to loop starting from first element if the current element is smaller than its index add number of items in the set smaller than its index to the answer then add the item to the set ps : sorry i ment to add the index of the item to the set i know my english is poor as well as my explanation but feel free to ask for further explanation
I guess their is no need of the ordered set (policy based data structure), the normal set works just insert all pairs {a[i],i} where a[i]<i and iterate on the vector. delete the first value of set until becomes greater than a[i] and just add the size of set to answer
I don't know what ordered_set is
actually that would a plot twist ( modify the spoiler tags lol) but you can read about it here : https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/ mr master xD
yeah yeah who am i to joke with a master i deserve downvotes plz give me more downvotes xDDDD
don't joke with masters
For each $$$1\le i\le n$$$, let $$$b[i] = 1$$$ if $$$a[i] < i$$$, otherwise $$$b[i] = 0$$$. Let $$$pre[i] = b[1] + \ldots + b[i]$$$. $$$answer = \sum_{i = 1}^n{pre[a[i] - 1] * b[i]}$$$.
AK-ed the contest. D, E, F, and G are the only ones I remember. D was brute force with maps, E was implementation, F was seg tree, and G was a nice greedy (kind of).
F can be done using sets also.
just insert all pairs {a[i],i} where a[i]<i and iterate on the vector. delete the first value of set until becomes greater than a[i] and just add the size of set to answer
Actually prefix sum is enough, O(n)
how prefix sum working??
We go from left to right. Foreach element we check if a[i]<i, if yes add 1 in our prefix sum.
Then find foreach element the number at position pre[a[j]-1], that is the count of a[i]<i numbers where a[i]<j.
163884238
F can be done with binary search
just realized that lol
am I the only one who used prefix sums for F lol
I did with prefix sum too :). I saw most of the pro guys used seg tree or BIT.I wonder why they didn't use the easier approach!
To come up with more optimal then current (nlogn) solution take some time, so they went straight to more familiar (nlogn) solution.
Exactly my mental process. I saw that it could be done easily in nlogn with seg tree and decided not to tire my brain out further.
why my code for problem G always give WA on test 4 ,my idea is use dp with bitmasks, thanks in advance.
Take a look at Ticket 15654 from CF Stress for a counter example.
I hate when tutorial is posted like two days after the contest.
Can someone Explain the TLE for G on my solution. 163933925 I did a recursive memoization dp like recursive knapsack.
UPD- it worked after adding if(factor>=35)return 0; condition
Please check my blog, I have some questions. https://codeforces.com/blog/entry/104782#comments
I just wonder how more people solved E than F,lol
i had the same question but it turned out its a variant from an already existed problem in geeksforgeeks maybe there are alot pro_googlers xD
It was also problem in one national competition in my country.
maybe it's cheaters?
In dp solution for G, why does it fail when I take max over last column (WA on test 4) and passes when I max over all states? shouldn't the max answer carry to the last column?
WA test 4: 163937656 AC: 163937856
In G I guess there are several nice ways to solve it. I used following:
Observe that if i divi operations are used, then it is allways optimal to use them on the last i elements. That means, we can build a prefix sum of boxes opened with k-operation, and a postfix sum of boxes openend by divi operation.
Calculation of prefix sum is streigth forward, $$$sum[0..i]-(i*k)$$$
Calculation of postfix sum needs more code. First I thought I can simply calc the sum, and in every step divide by 2, but that does not work out.
So instead I did bit counting the set bits in the postfix, and in each step move the count of each bit one position down. So I can calculate the cost/worth of the postfix in each step by the remaining count of bits.
163908470
I used the same. But is there any proof for "if i divi operations are used, then it is allways optimal to use them on the last i elements" ?
Consider one divi operation. If we use it on the last element, the costs are a[n-1]/2. If we use it on any other element, the costs are higher.
Then by induction we would choose the second last element for the second divi operation, and so on.
Can you elaborate plz?
...
Shitty contest, end Div.4!
Why was this shitty? Feedbacks are always appreciated
Fuck Div.4
Problem G Why does my solution fail test 4 https://ideone.com/FptY9R
ll n , k; cin >> n >> k; vector<ll> v(n + 1); for (int i = 1 ; i <= n ; i++) cin >> v[i]; vector<vector<ll>> dp(n + 1, vector<ll> (45)); for (int i = 1 ; i <= n ; i++) { dp[i][0] = dp[i-1][0] - k + v[i]; for (int j = 1 ; j < 40 ; j++) { dp[i][j] = max(dp[i-1][j] - k + (v[i] / (1ll << j)) , dp[i-1][j-1] + (v[i] / (1ll << j))); } } cout << *max_element(dp[n].begin(), dp[n].end()) << endl;Let's say k is big, and array a is small then after some steps it's always just better to take the bad key (it will add 0). You can just fix this by taking max of dp[i][x] over all array.
oh thanks a lot accepted
Another fun div.4 contest! Problem D, E contains a little bit of thinking and problem G is really interesting! The observation that we use good keys at the first i chests is actually not so easy to find.
I tried several ways to solve F problem, but I couldn't do it. How should I think about this problem？
Think in terms of binary search
It seems D: has most hacks
Yeah, but what's the test case? I don't see any scope of TLE in the code.
prolly people using unordered sets/maps
I saw a few codes with map also getting TLE
Some people didn't use
breakwhen theirmapchecked two strings that can be successfully combined,so if hackers let strings can let their code check many times,theirsubstrwill make them TLE.For example:
a aa aaa aaaa aaaaa aaaaaa aaaaaaa aaaaaaaa aaaaaaaa aaaaaaaa ...and the last string will be checked for 7 times but
substris so slow.Will it make any difference? because there can be test cases with no matches which will be having same complexity.
Can you give an example?I hacked many people in this way and they all used
map.i saw some that used
string = string + characterinstead ofstring += characterThe function
count()in multiset has a time complexity linear with the number of matches , which can be hacked.You can't hack this one , I did the same solution in the contest and it directly gave TLE in the contest itself .
Well I did.
When will be the rating updated?
After 2hr ig............ first time my rating won't get updated xD
Nice but underrated contest.
Rating will be updated after sys testing is done.... :)
I mean too few likes. Only +130.
The problems were great but I think the problem E Harder than all
I pariticipated in the contest, but it doesn't show up in my profile? My rating is below 1400, so it should have been rated for me? Can anybody explain or am I missing something?
rating usually will be updated few hours after system testing. so you just need to wait for it.
True. However, it's been almost 12 hours after the open hacking phase ended. I presume that there's no way to see if system testing is still ongoing?
System test was ended.You just be patient for the rating changing.
Me checking every 5 minutes, if my rating is increased by 0 or rating has not updated till now
I really don't get cf's rating system. Mine was less than 1400 and I got downrated solving 3 of them. LOL
It doesn't only depends on number of problems you have solved, it depends on your performance and other's performance including amount of time you took.
Why is my rating has decreased by 5 !
I solved 2 problems without any wrongs so what's wrong !?
Rating change depends upon your performance (Rank) in the contest.
consequence for wrong submission ?
10 minutes penalty
No brother, i have submitted 3 times wrong and forth tkme i solved. And got -75.
I believe you are mixing rating points with contest points. The -75 you are referring to is how much your rating changed after the contest. Rating changes are based on your overall performance/rank on the contests. Your performance/rank in contests with ICPC rules, such as this, are based first on how many problems you solved and then on how fast you solved them. An incorrect submission adds 10 minutes to how much time you took to solve a problem, what makes your performance worse, but doesn't quite directly influences your rating change like this. You could have had zero incorrect submissions and yet a negative rating change, because although you didn't get anything wrong you had a bad performance, or you could have had 100 incorrect submissions and yet a positive rating change, because you had a good performance.
Why my standing's different from the official standing table than the "friends standings" table?
I just wrote this to make number of comments 300 (-_-).