Hello!
This time decided to fill myself in the shoes of the problem writers. It is very exciting! My challenge was to prepare a round in one day. It's really incredible pleasure to surrender to my passion and all day just work on problems!
Despite the fact that in total I've wrote 8 problems, I made it in time. Initially, I prepared 7 problems, but two of them were found to be used before (thank you, 300iq and cdkrot for poining it) and I removed them and wrote a new problem.
Codeforces Round 496 (Div. 3) will start on Jul/09/2018 18:35 (Moscow time). You will be offered 6 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the Div. 1 not be at all interested by this problems. And for 1600-1899 the problems will be quite easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.
The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.
You will be given 6 problems and 2 hours to solve them.
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:
- take part in at least two rated rounds (and solve at least one problem in each of them),
- do not have a point of 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
Many thanks to the testers: kevinsogo, 300iq, cdkrot, arsijo and adedalic. You really helped to make this round!
Good luck!
UPD 1: The round is over. Thank you for participation!
Official Top-5 (trusted only)
Unofficial Top-5 (+ untrusted)
UPD 2: The editorial is available by the link.
You forgot to thank MikeMirzayanov XD
I've told him it personally.
is that rated for me?
Common, did you read the text?
Starting rating is not shown, so it is not so obvious if their rating is less than 1600
Good point.
So, is the point of trusted participants just that those who aren't such participants will not appear in the Top X table, or they will not affect our ratings also?
Because if the round will be rated for them, we must affect each other's ratings, mustn't we?
AFAIK, there are two separate rankings, one is for trusted participants and it is the official one, while the other is for the distrusted participants. The lists do not affect nor influence each other in any way. The idea is, if you are a smurf, you'll compete with other smurfs, and people who actually ARE Div3 level will compete against one another. You won't see distrusted participants in the official standings.
Thanks for your reply.
I don't think so, because if, for example, two distrusted participants participated in some contest, according to what you said, the one with higher rank than the other will have a positive change on his rating, and the other one will have the same change but negatively (because, AFAIK, the total sum of the rating changes in a round equals 0), but this didn't happen before.
You're right, but I think that this (one gets some points, the other loses) will actually discourage people who have smurf accounts because they won't achieve much by competing in such circumstances (they all solve everything, meaning some may even lose rating points as unrated and get < 1500), while the point of them competing in a div3 round is to "dominate" it.
There are some new unrated accounts that solve all tasks in a div3 round, only they won't get the expected rating change (~+200) but something relative to other unrated folks who are clearly smurf accounts, and that effectively defeats the purpose of anyone having a smurf account (or that how it is supposed to work, anyway, I don't know if it's actually working :), but I guess it is ).
Why untrustworthy participants appear in top5?
What do you mean?
They participated in less than 2 rated rounds, so they should not be in the official table. So why are they included in the winner list?
haha, MikeMirzayanov is himself.
MikeMirzayanov a couple div3 contests back there was talk of the reduction in the penalty for wrong answers (20 is too much), any updates on that ?
I'll try to implement it before the round. Stay tuned!
Any updates regarding the penalty time?
I've implemented it. You can check how it works on the ranklist of Codeforces Round 494 (Div. 3).
Great job! Looking forward to it..
Will Educational Rounds will have from now on just 10 minutes penalty for each wrong answer?
Yes
How can one prepare 7 problems in ONE DAY? Amazing!!! THANKS
I am a simple man I see MikeMirzayanov I "upvote".
I am a simple man I see a "I am a simple man" reference I "upvote".
Hopefully MikeMirzayanov had enough time to make some not so weak pretests.No one would like to see many solutions fail after systests & I wish vovuh will be back in the next Div-3 round.
This is insane. Thank you so much for putting in effort to make this an awesome site!
As awesome as TheOneYouWant.
6th Div-3 Contest in the history of Codeforces Round. <3
Thanks a lot for making another div3 contest. It would be better if provided with 7 problems. Hopefully, problem statement will be the short description. Best of luck.
MikeMirzayanov Will you make some tutorial on How to become a good problem setter...
MikeMirzayanov Any updates about lowering down the 20min penalty time for the 2h/2h30 contests? (For Div3 and Edu)
So many "MikeMirzayanov"s in this blog. Is it his birthday?
no,it is his contest <3
no but MikeMirzayanov is father of codeforces
Wooow, you both are "soo clever" I didn't know those.
and u so dumb,we did know that:))
MikeMirzayanov why don't you ever participate in any contest on codeforces, it would be fun to see the CF founder competing with others.
Please correct me if I'm wrong, but I remember that edu rounds allow registration at any moment before the end of the contest. Why is it that this contest registration is the same as normal rounds (with extra registration) if its rule is the same as edu rounds?
Edit: my mistake, registration closes for 10 minutes before and after start of contest only
Some of the last codeforces contest were so much unbalanced. The questions in this contest were so nicely balanced. Enjoyed it. Looking forward to such more contests.
What was pretest 9 in D?
Try 317878994 The answer is 5, it worked for me :)
Loved this round. <3
How to solve E2?
Let s1[l..r] be (number of elements > m) — (number of elements < m) and s2[l..r] be the number of occurences of m.
You can prove that in order for a range to be valid, 1-s2[l..r]<=s1[l..r]<=s2[l..r].
If you expand s1/2[l..r] into s1/2[0..r]-s1/2[0..l-1], the problem becomes 2D range sum queries with point updates.
I solved it by counting number of arrays having median>=m and subtracting from those, the count of arrays having median>=m+1.
To count number of arrays having median>=X, we can replace all elements < X by -1 and >=X by +1 and count the number of subarrays having a non-negative sum (and taking special case of when the length of the array is even, in that case the sum must be positive), both of which are kind of standard problems.
Lol, why am I so dumb? I was thinking of 2d segment tree :D
You're not dumb at all, I got AC with this approach for both E1 & E2
non-negative sum? what does that mean? how sum can be negative?
Sorry, there was a formatting mistake in my comment! I have corrected it
For E1 after changing m to 0 and numbers less than m to -1 and greater than m to +1 one can iterate though the prefix sum and count answer with the help of a map like here Can a similar approach be used for E2 by accounting for the number of zeros also ? I was not able to think of any O(n)or O(nlgn) solution like iterating and using map in E1. Any help?
How to find the no of subarrays with positive sum efficiently?
I counted the number of subarrays that don't have the median equal to m, and subtracted that from n*(n+1)/2. There are two cases:
1) L + ZEROS < R
2) L >= R + ZEROS
L: left part (< m), R: right part (>m), ZEROS = number of elements equal to m.
In the first case, I change the values <= m to -1, others to +1 and find subarrays with strictly positive sum.
In the second case, I change values < m to +1, others to -1, and find the subarrays with non-negative sum.
So, what was that test 11 in D?
let's say a are numbers such that a%3==1 and b are numbers such that b%3==2
if count(a)==3 and count(b)==0 or count(b)==3 and count(a)==0 you have to split.
{ Edit : the complete approach is mentioned below }
What do you have to split?
Try 112, the answer is 1
The worst future you can imagine:
Why I got TLE on E1 test 27 ?
How to solve E2? I thought of an approach to make every number unique by giving them id in increasing order.Now suppose m appears k times in array then all m will have values from some f + 1 to f + k where f is the number of elements less than m. Now solve as the previous problem where median should lie between f + 1 to f + k;
How to solve D? I wrote a DP solution but got WA at test 11 multiple times.
It must be greedy then? I got to the same test using greedy approach.
Yeah it is greedy
And whats the problem with test 11?
what is your code doing exactly?
I first make prefix sums of digits in array pf. prvi[i][j] stores the nearest position k to the right such that pf[k] % 3 = j. Then I greedily choose the nearest number to go to,while updating the solution.
It's a very long number
Thank you very much (;
Correct answers for 824 (1) and 824824 (2) let me pass test 11.
Let dp[i]=answer for prefix of size i. We can see that dp is non-decreasing. And let sum[i] be the sum of prefix modulo 3, and x[i] be the last j then sum[j]=i. Then dp[i]=max(dp[i-1], 1 + dp[x[sum[i]]], sum[i] == 0)
I solved D on the fact that given a 3 digit number in which no digit is divisible by 3, there is at exactly 1 segment whose sum is divisible by 3.
Can anybody please post and explain his/her Solution for D, if it is based on BINARY SEARCH.
D is just greedy
In D you can observe, that every (at least) 3-elements-long subsequence will have correct combination. I swapped all the numbers a for numbers a%3 and then started greedy algorithm. For every i have sum of elements (i), (i + i-1), (i + i-1 + i-2), but first I check, whether any of those numbers was taken previously. For example I store a sum from range (i) (just a single element) and then check if element indexed (i-1) was taken. If it was I don't check further, if it wasn't I can add that in my sum. If my sum%3 == 0, then I mark element i as taken and add +1 to the answer.
If I checked only one number, correct answer would only occur if it was == 0(mod 3). If I checked only two numbers, then I would have those combinations of modulo: (0, 0), (1, 0), (0, 1), (1, 1), (1, 2), (2, 1), (2, 2). As you can see only three of these are correct. If I checked three numbers then there would always occur at least one correct subsequence.
I solved D by dp
Anyone can tell what's wrong with my solution in problem C, I got WA test 12. http://mirror.codeforces.com/contest/1005/submission/40145706
Overflow. Add more powers of 2 and it would work.
I've considered the last power of 2 which is less than 10^9, Still getting WA.. please check my solution :- My submission
But the sum of two elements can be up to 2 * 10^9. Maybe you need one more power?
Good Contest.
Can someone share the idea of E2? My Code work when median value exist only once in the array.
test case 11 of problem D was nightmare for many contestant including me. :p
XD it's something like 112
The most interesting div.3 round, with the last 2 problems pretty tough in my opinion.
How did more people solve C than D? D is just classic greedy but I don't even have an idea about C...
If you are currently considering a particular number in the array, there are only log(n) other numbers which, if added to the number being considered, give a power of 2. So we can use hash maps to store numbers and so complexity is O(n*log(2*1e9))
I don't solve D because I wrote
if (!(digit + temp.front()) % 3), notif (!((digit + temp.front()) % 3))or simpleif ((digit + temp.front()) % 3 == 0). And... I don't find the mistake.let x, y, z be the three left-most integers first check x then check y and x + y last, check z, y + z, and x + y + z
??? I solve this problem after the competition by adding two brackets, as I said before.
Because
!(digit + temp.front()) % 3equals(!(digit + temp.front())) % 3Can anyone explain greedy approach for D?
hint: if x, y, z are integers, then at least one of x, y, z, x + y, y + z, and x + y + z is divisible by 3
Very straight away approach : Iterate over the array , if s[i] is divisible by 3 , increment counter and make num =0 , else store it in num . Each time check if num is divisible by 3 , and if its length crosses "3" , it** must** have already been divisible by 3 => Clear num and increase counter.
I'm wondering what would happen if MikeMirzayanov prepared this contest in more than one day.
Whats making it TLE Im still wondering ?? problem — B
check
You create new string every time. It is rather suboptimal.
But everytime im creating with first character removed from string.
Everytime the whole new string is created, not only the first char is removed
Can u suggest me alternative for that part of while loop. Thanks
giving WA bro
Checking if strings are equal take too much time — solution has square complexity. . WA — because you need to find the first index from the end of both strings, where s[s.length() — index] != t[t.length() — index]. . codeforces and yes — you are looking for s[9] and t[2], then s[8] and t[1] and s[7] and t[0].
Im using substring method of java. Is that making it TLE?? What is time complexity for substring ()?? — is it O(n) or O(1)?
I don't know Java, but I heard that it is O(n) in new versions and nearly O(1) in old versions, maybe I'm wrong. Also I'm not sure about the complexity of method equals — it's more probably that O(n).
E1, E2 — http://www.usaco.org/index.php?page=viewproblem2&cpid=91〈=en
Do you even read that problem? They ask different thing to do. You waste my time.
I thought you said 6 problems "You will be given 6 problems and 2 hours to solve them.".But anyways I enjoyed the round thanks.
How do we solve C? Do we optimise the brute force method or use some other approach entirely?
Enumerate each number, enumerate the power of 2, and subtract the number by 2 power, to see if the result is in the original set.
There a only 31 powers of two which are less than 2e9, so you can brute-forces over those powers.
I did a different approach in D, I first removed all 1 digit no.s and stored the rest no. as various segment, and then iterated over the segments for 2 digits and so on. I am not getting TLE, I and I can prove why my algorithm can pass TLE, but instead a wrong ans on TC 11. Code link: http://mirror.codeforces.com/contest/1005/submission/40144526 Thanks :)
I had the same approach. Couldn't pass it
what was your ans for TC11
At first I was getting TLE but my implementation was crazily bad. Then when I implemented properly I'm getting RTE on tc1.
I too did the same . But there is no need to store segments of size more than 3 , as explained in above comments . So , its just wastage of memory....
Did you get AC
Всем привет. Я возможно придумал О(n) решение на Е2, но к сожалению возможности проверить его у меня нет, так что хочу сейчас его рассказать, а вас прошу проверить его. Если есть ошибки и замечания — пишите ниже, неплохо если еще и с тестами. Теперь к сути: Рассмотрим случай с нечетной длиной подотрезка. Очевидно, что число явл медианой, если колво строго больших и строго меньших равны. Число равных в таком случае будет нечетным и наше число можно поставить в серединку. Будем перебирать правую границу интересных подотрезков и походу считать на префиксе пару (колво больших; колво меньших). Теперь при текущей правой границе и префиксной парой посчитаем колво подходящих левых. Очевидно, что подходят такие пары, что разница между ее колвами равна разнице между колвами текущей пары (тогда колва подотрезка с данными границами будут равны, что нам и надо). В итоге получается что можно вместо пары на префиксе хранить разницу между колвом больше m и колвом меньше m. Ограничения позволяют использовать массив вместо мапа. Не забудем так же про префикс нулевой длины (разница 0). Однако стоит напомнить что это только при нечетной длине подотрезка, поэтому храним два разных массива на каждую четность индексов и используем какой нужно на каждом шаге. Теперь рассмотрим для подотрезков четной длины. Решение на самом деле остается таким же (помимо других нужных четностей), но с рассмотрением еще одного случая, а именно: колво меньших должно быть на 1 меньше, чем колво больших. Довольно понятно, почему и как надо рассматривать такой случай (считаем колво разниц на префиксе отличающихся на 1 от текущей. +1 или -1 зависит от реализации). Почему же все равно надо считать колво позиций на префиксе с такой же разницей? Потому что в таком случае колво равных m будет четно и мы можем поставить число на левую середину, чтобы данный отрезок подошел. Вот собственно мое решение, прошу оценить. Если есть вопросы, то задавайте.
Привет. Ты возможно придумал O(n) решение на E1
An awesome round!
How to solve E1?
Note that, in any sequence of numbers that satisfy the condition, m should be included. Also, in total we only care that the number of numbers greater than m minus the number of numbers less than m is 0 or 1. Now, just find for each indez the greater-lesser factor, separately, for indices before the value m and after the value m. Now, just compute using the condition
There is other input similar to test case 11 in problem D? Just to check why I'm getting WA.
How to solve E2?
Got Wrong Answer on Test 11. What wrong am I doing here ? My Submission: 40139802
A counter case: 382845 The answer should be 3 but it prints 2.
mike's contributor is oo
0^2 ?
Can someone give a Dp solution of problem D and why we are using only 3 values i didn't undertand any solution.
Look at this: http://mirror.codeforces.com/contest/1005/submission/40136032
thanks man
how u approach dp problems
It's two good rules: 1. Find a recursive solution 2. Look for the variable(s) changing in recursion, and store the result obtained for this variable(s) in a map or (something like that). Use this stored value when available.
https://www.geeksforgeeks.org/memoization-1d-2d-and-3d/ this might help you.
Editorial Link
I have some questions regarding Problem C:
In Sol1 on line 36, I have used mp[y]>0 check to see whether y exists in the map mp or not, here y can be negative as well but I have not checked that. This solution results in Memory Limit Exceeded error on 7 test case. However, if I use mp.find(y)!=mp.end() to check whether y is in the map of not, it passes.
Can someone please point out why is this happening?
Thanks a lot in advance.
Mp[y] will insert y in map with default value 0.While Mp.find(x) return iterator to the key x without inserting it. Try this
for(i = 0;i < = 10000000: i + + ){if(Mp[i] = = 0){};}
And check the memory used.
But even after the insertion of elements, only 120000*32 elements will be stored in the map, so why does it give memory limit error? As long long is 64 bit, it will be 29 MB roughly in the worst case. Please correct me if I am wrong.
you are iterating on the map and simultaneously inserting an element in it. This will cause the invalidation of references. Read this
Here, I have submitted your code just by storing the array in the different map and iterating over it.
I have made the same mistake once in a div2 contest. And, BTW your calculation is wrong it is more than 150MB(See This).
I am getting runtime error with "Exit code is -1073741819" message on solution for D.
here is my code : http://mirror.codeforces.com/contest/1005/submission/40144266
Can anyone point my mistake out??
I don't think you can clear a set/list while iterating through it. So if you remove
s.clear()from line 39 (from the first submission you linked) and only clear it if p is set to 1 after the loop, it should work without crashing.I have a sort of similar query too:
Consider a map map<long long,long long>mp. and now you are iterating it and using it like below:
This produces errors and undefined behaviors. Why? Thanks a lot in advance.
I think this should be helpful
Thanks a lot!
My last submission to problem C in the round has passed test 7 and 11 and it was AC and after system testing it's now WA on test 7 ! And I also want to know that why unordered_map worked her and map was so slow I didn't face such issues in a CF problems before !
My code of problem C got accepted on testcase 7 in contest time but gave TLE in system testing. Can anyone help. I total made 5 submission in which third one got accepted. In which 4 gave runtime error at testcase 7 while third submission got accepted. But in system testing got TLE. Please anyone explain.
I have the same issue and after the contest I have submitted a a solution with unorderedmap and it is AC now while the solution with map failed in test 7 although it has passed this test before
It passed with simple map after the system testing and failed during the system testing. Both are same code.
This is the code I submitted during contest: http://mirror.codeforces.com/contest/1005/submission/40135410
This is the same code I submitted after the contest and got accepted http://mirror.codeforces.com/contest/1005/submission/40160479
I didn't used unordered map. Passed with simple map. Anyone please explain this.
Can anybody help me out I can't understand why my same solution is both TLE and AC. AC:40160742 TLE : 40160895 It has cost me a problem in this contest which I was sure would pass the test cases.
Bro same happened to me.
Can someone please tell me what's the error in this approach from Problem D? Solution
WoW! I get rank 2!
I pass E2 with Balanced_Tree in Segment_Tree. But in fact using fenwick tree can pass E1 and E2, in this way, the length of code can be reduced much.
Orz Akfun!
Akfun is our red_sun!
Orz Akfun!
Akfun is our red_sun!
Orz AKfun!
AKfun is our red_sun!
(human is fundamentally repeater
Orz AKfun!
AKfun is our red_sun!
Orz Akfun! Akfun is our red_sun!
if x, y, z are integers, then at least one of x, y, z, x + y, y + z, and x + y + z is divisible by 3 ****__ can anybody provide a proof for the above statement or an idea to get to above conclusion
There aren't so many cases: 1) one of the numbers x, y and z is divisible by 3. 2) all of them aren't divisible by 3 — the variants for the rests of division are: (x % 3 = 1, y % 3 = 2) or (x % 3 = 2, y % 3 = 1) — then (x + y) % 3 = 0.
Other cases: 111, 112, 221, 222. that's all.
For E1 after changing m to 0 and numbers less than m to -1 and greater than m to +1 one can iterate though the prefix sum and count answer with the help of a map like here Can a similar approach be used for E2 by accounting for the number of zeros also ? I was not able to think of any O(n)or O(nlgn) solution like iterating and using map in E1. Any help?
Any help will be appreciated, WA in test 11 problem D Link.
I don't know how halyavin was successful in hacking so many of our solutions for problem C. Can someone explain me the Generator Algorithm he used? It would be great to understand what that algorithm did to exploit the weakness in so many solutions. Thanks!
His generator
It creates O(n2) test for Arrays.sort in Java. Only sorting of primitive arrays can be exploited — sorting Integer[] or Object[] is fine. All the complications are needed so that generator doesn't require O(n2) time itself.
Thanks a ton! This is sooo awesome!! :)
Thank you :)
Can anyone please explain me of problem C. I also read editorial. But still i didnt get it that how can it do easily to using map. Thanks.
For every element you need to find , whether there is another number which on summing gives a number of the form 2^d (i.e.,a number which is a power of 2 ) . So , first create an array which stores all the powers of 2 till 10^9 , then for every element , iterate over this array (powers of 2) and take the difference between both and check whether this difference exits in your original array excluding the current index (You can do this using a map/binary_search). If there is no such element increment your count value and finally print it !
Thanks furious__ got AC.
That's ok mate !
Sorry, I'd like to ask you. How can I solve problem D in DP?
I can't understand why we solve this problem in DP.
https://drive.google.com/file/d/1uBBOkG7DvJsU-W2NQV3q-TaurdH1XRGd/view?usp=sharing Is it a error? I test the program on my computer give a correct answer and the web give me a wrong answer.Can you test and check that ?
In your solution the problem is with
int t = log(i) / log(2). log() and power() works with double. Just remove this string and change toreturn i==pow(2,log(i) / log(2)). The type will be double and all will be OK.