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 _kun_ 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, _kun_, 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 participantsjust that those who aren't such participants will not appear in theTop Xtable, 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.

you forgot to thank the problemsetters of IOI 2018 day 1 q2 and q3 :o

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?

follower

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..

penalty now is 10 minutes .. good

Will Educational Rounds will have from now on just 10 minutes penalty for each wrong answer?

Yes

How can

oneprepare 7 problems inONE DAY? Amazing!!! THANKSI 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.

Good point.

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

when i will be Expert..

i do not go Expert .. so i still could participate in DIV3

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...

when you be a good problem solver and above ..

MikeMirzayanov Any updates about lowering down the 20min penalty time for the 2h/2h30 contests? (For Div3 and Edu)

penalty now is 10 minutes

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.

nice Q wating for answers //

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 :)

Try 14334. Ans: 2

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?

Whatever it was. But I must say it was disastrous.

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?

observation 1 : you have to make splits in the array (vertical splits) if the element is 0 or a multiple of 3 . the number of these elements are added to the ans.

removing these elements creates some segments . within a segment you can encounter elements of two kinds . element type a (a%3=1) and element type b(b%3=2).

while processing the segment let count of elements type a be |a| and similarly |b| :

if min( |a|,|b|) == 1 , then we are sure to have encountered a subset of this segment whose sum is multiple of 3. we reset the counts here and continue looking for other such sub-segments.

if the above doesn't hold either |a|=0 or |b|=0 ,in which case |b| should be a multiple of 3 to yield 3 sum sub-segment and similarly for |a|. if that happens we reset counts and continue.

Try 112, the answer is 1

The worst future you can imagine:

I'll be in your nightmares B)

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

mappearsktimes in array then all m will have values from somef+ 1 tof+kwherefis the number of elements less thanm. Now solve as the previous problem where median should lie betweenf+ 1 tof+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.

got the mistake in my implementation. dp always works!

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)

LINK. Can you tell what kind of case will this solution fail. I have used a recursive approach. EDIT: GOT AC!

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.

Okay! DP was more intuitive to me as this problem was similar to a classic DP problem of recursive partitioning.

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://codeforces.com/contest/1005/submission/40145706

Overflow. Add more powers of 2 and it would work.

Aaaah :'(, I can't believe I didn't notice it xD Thanks man.

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?

You are right.

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)`

, not`if (!((digit + temp.front()) % 3))`

or simple`if ((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()) % 3`

equals`(!(digit + temp.front())) % 3`

Can anyone please provide a miniature version of tc 11 for problem D

Can 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

Couldn't point out this fact during contest , instead I kept on storing them :(

can u provide a proof for the above statement or an idea to get to above conclusion @keima915

You may use examples to get the feel of it ! eg : 714|3|0|888|222|57

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.

From constraint I think brute force should work. Because for each iteration we r finding for two elements at a time.

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://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

Nope , rather I got Run time error on Test 11

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.

How to solve F?

mike's contributor is oo

0^2 ?

oo = infinity

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://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 LinkI 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 insertyin map with default value 0.WhileMp.find(x) return iterator to the keyxwithout inserting it. Try thisfor(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).

Oh, I understand it now!

But can you please tell me where I went wrong with the calculations?

Thanks a lot for your generous help.

Its v.nice

I am getting runtime error with "Exit code is -1073741819" message on solution for D.

here is my code : http://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://codeforces.com/contest/1005/submission/40135410

This is the same code I submitted after the contest and got accepted http://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!

Your crafting.oj.uz ratings are updated!

my code coincided with one of the other coders and i dont know how it got copied . I generally code on ideone but i dont know much about its settings . would i be penalised for that ??

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 conclusionThere 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(n^{2}) 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 requireO(n^{2}) 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 to`return i==pow(2,log(i) / log(2))`

. The type will be double and all will be OK.