Hello again, Codeforces!

I'd like to invite you to Codeforces Round #452 (Div. 2). It'll be held on Sunday, December 17 at 09:35 MSK and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time!

**The round is rated.**

This round is held on the tasks of the second day of the municipal stage All-Russian Olympiad of Informatics 2017/2018 year in city Saratov. They were prepared by Olympiad center of programmers of Saratov SU. A convincing request to the participants of the municipal stage in Saratov to do not participate in this contest.

Great thanks to Nikolay Kalinin (KAN) and Grigory Reznikov (vintage_Vlad_Makeev) for helping me preparing the contest, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon platform and to Alexey Ripinen (Perforator) for writing solutions.

You will be given six problems and two hours to solve them. The scoring distribution will be published soon. Good luck everyone!

**UPD** The scoring distribution **500-1000-1500-1750-2250-2500**

**UPD**: The system testing is starting now, but upsolving, virtual participation and viewing solutions and tests will be disabled till the end of the olympiad in Saratov (around 2-3 hours from now). Hope for your understanding. Editorial will be posted after the olympiad as well.

**UPD** Congratulations to the winners!

**UPD** Editorial

You wrote two consecutive rounds! Wow!

UPDNever mind, I didn't know that the rounds were based on Olympiad. Sorry.This round is the based on problems from the same contest as today's contest. Does this mean the round, Div 2 in particular, will be of similar difficulty to today's round? It was a great round (personally anyway), don't get me wrong, but it was definitely easier than normal.

Many people solved problem D and E in today's round.

LOL dude i thought i was going to end up like you at the end of the contest but i messed up really bad today

Why is it so late?

You mean early? That's how time zones work mate.

why so early ?

He got adrenaline & used w, w, w, w

In this month will be some codeforces round

1:35 PM in Hanoi.

It would be good if my class wouldn’t start at 3:00 PM... :<

You can solve this issue recursively! If you know what I mean ;]

i hope that this round's problems will be as difficult as the previous round's problems

so as the queue

Hope the contest before the day of semester final would be enjoyable as the last one was. :)

First contest without Russians?

Not really :D

But lots of Chinese：D

An UTC+8-round :)

While is the upd point for each problem?

1:35 AM in Cuba , nice!!!

Nice people nice contest and everything nice. WISH EVERYONE HIGH RATING ALTHOUGH I DID NOT ABLE TO INCREASE MY RATING.BE HAPPY DON'T THINK THAT IF YOUR PERFORMANCE IS BAD IN ONE CONTEST YOU CAN'T ABLE TO ACHIEVE ANYTHING.YOU CAN BE THE BEST :)

You are ryt :)

stfu

tu chut*** hai

I really hope this round will be better than the round before.

Six problems? Sounds good. And the time is quite friendly to Chinese participants :)

The classic: Is it rated?

All right... It seems that today's problems are much better than yesterday's. I like this round very much. -- Though my B was hacked.

6.35am(UK) is so early XD

the last contest in Cuba was at 6:30AM and this contest is at 1:35AM , very early XD

Cov :o

apparently the link described in the rules,

http://codeforces.com/blog/entry/456 and http://codeforces.com/blog/entry/4088

was not found on Codeforces's server on my end. anyone know how to access this?

...damn it. it was two links. i'm stupid.

wh2001_ZY will solve all problems in the contest!He's the best!

whan I want to hack, I couldn't see other's solution .

why????

You lock your solutions in the dashboard before hacking other solutions, but beware, after locking your submission you won't be able resubmit any solution after

I got it

mby u haven't locked ur problem

I got it.

How to solve D and E?

I got no idea for D.

For E, though I was not able to submit because of too much code writing but my idea involved range min query and lazy propagation.

I think math is all what D needs.

Thinking of the sum of two arbitrary positive integers whose sum ends with 9. If N is greater than or equal to 5 then we always have a pair of numbers making up the sum ending with one 9. If N is greater than or equal to 50 then we always have a pair of numbers making up the sum ending with two 9's. The same goes for greater number N.

Well that's just what I thought of, but I had trouble managing time so I couldn't manage to fix my code for D. Also if there's any error or misunderstanding of the problem please fix me. I'm not sure that's really the right solution.

I think E requires some clever use of data structure like set . Couldn't get AC though because of time but I think my approach is correct.

I solved E simulating the array with set and map

Yes. That's what I did . but got wrong answer in pretest 7 . Finally when I corrected my solution , Contest was already over. screwed up badly !

Sorry man. But dont worry, I also had a bad contest :)

Hi , TwiceBig I was not able to solve E in contest timings Will you share your thinking and solution , that would be really great.. I am attempting the problem now, your method will surely help..

Thankyou.

Hi. Well basically what I do is simulate the array using a set. For that I store a pair of integers. First frequency and second what position of the array it is. Since set has data stored by minimum, I store The first value as negative. Also I have an extra map for helping me in the merge. While there is something in the array ( the set ) I erase the first value of the set, cause it is the next range that has to be erased. When I remove an element I search the left and right element with lowerbound in the map. And if left and right has same value I merge them. So I have to remove from the set the left and the Right. And add the new pair I just merged. And update the map. And that's all. Hope it helps

good approach.

For D, divide sum of pair which is to be found by 2.In case of even numbers on the pairs will be on both the sides of halved number. We only need to find the number of pairs. So this makes it even easier.

33347025, got AC with Disjoint Set Union. Each connectivity component — is segment with equal elements. I kept this components in set, selecting component with maximal size. Time complexity approx O(N log N)

I thought I finally found the bug right before the end, but still WA on pretest 4! What's pretest 4 on problem D?

n is 10

^{9}You should note that there is no shovel with the price of 0.

I got stuck there too. Costed 4 submissions and a whole fortune of time.

what's the answer for n = 1000000000? Ishan.nitj

I think I made sure there is no shovel with the price 0! Don't know what got wrong?! AkiLotus

5 * 10

^{8}gives correct answer. I checked this at first, this is not pretest 4

how to solve C? my recursive solution fails on pretest 5 :|

Make cases for each remainder of n with 4.

https://ide.geeksforgeeks.org/g7FlgnMq7a

any test case yu can suggest

If you want code and some help, you can have a look here.

Code — https://paste.ubuntu.com/26200030/

I just found a segment of numbers which sum to (sum_of_sequence) / 2

Not sure why it works, and if it's correct(did pass the tests though)

I just got my solution for problem C accepted with only linear loops (

`O(N)`

time complexity), but my approach looked pretty weird I think. I did think of modulo 4 but I didn't write code that way. Can anyone suggest or show me proof of correctness? http://codeforces.com/contest/899/submission/33346265Get the sum of the first

`M`

elements. Get the absolute difference of it and the sum of the rest.`M`

does not exceed`N/2`

.Get the sum of the last

`M`

elements. Get the absolute difference of it and the sum of the rest.`M`

does not exceed`N/2`

.Get the sum of the middle

`M`

elements. Get the absolute difference of it and the sum of the rest.`M = {N/2 - 1, N/2, N/2 + 1}`

.I wrote a little code brute-forcing all the cases and notice that with some N there exist solutions where the middle elements are chosen, and with some other N there exist solutions where the first (or last) elements are chosen.

kind of same. https://ide.geeksforgeeks.org/g7FlgnMq7a

Check the sum = n*(n + 1) / 2. If it is even, the answer is 0 (because you can divide it in 2 equal groups), else the answer is 1. Now, you have to find the 1st group: If n is even, then just write 1 4 5 8 9 12 until it is lower than n. Why does it work? (first number is from 1st group ) 1 2 (first group is second group + 1) 4 3 (first group = second group) 5 6 (first group is second group + 1) 8 7 (first group = second group) and so on if n is odd, use the same idea but from the end For example n = 7, then 7 6 (diff is 1) 4 5 (diff is 0) 3 2 (diff is 1) 1 (diff is 0)

yes. did it. i always get the correct answer after competition ends :P

Any hint on what's 7th pretest in E?

I got it wrong because I wasn't recalculating the lengrhs correctly after merging, if that helps.

I think something like 13 1 1 1 2 2 2 3 3 1 1 2 2 1

try this case:- 1 3 3 3 2 2 3 3 3 1

thanks..found the mistake giving 5 instead of 4

I have this one that is easier to debug:

7 1 1 2 2 2 1 1

Answe should be 2.

in the end of contest, i tried open hack attempt page but it not opened two min

so sad..

Another nice round. It's harder and suits Div.2 better though. Cheers. ;)

Problem D. Shovel Sale*********Note that it is possible that the largest number of 9s at the end is 0, then you should count all such variants.**** if they neither give n<5 in pretest and nor in announcement then standing will be completely different.They did give n < 5 in the pretests, because I failed on pretest 7 before checking this condition.

thst's what i am saying

If they don't...They did give n < 5 on Pretest 6. I realised, two Runtime Errors and one WA later.

I'm sure n < 5 was given, one of my submissions hardcoded the values for n < 5 incorrectly and it worked once i fixed that.

If n=4? Please tell!

answer will be 6. 1 2, 1 3, 1 4, 2 3 ,2 4 , 3 4.

Shucks I didn't consider this. I was like n<=4. cout<<0<<endl; Stupid me. :/

I did that too, but got a WA. Then corrected it for an AC pending systests

Exxxxxxx! I didn't understand! **** Note that it is possible that the largest number of 9s at the end is 0, then you should count all such variants ****

If N < 5 then all pairs making up sum ending with no 9 are counted. Refer to Enigma27's comment. Right at 5 the answer will be 1 since there exists one pair (4, 5) making up the sum 9 having one trailing 9. You can hardcode the case N < 5.

i didn't like the recent contests on this site :)

Ok

people disliking my comments 4 good ure all just haters

True nigga true

What was your Hack test case for B?

20 31 31 30 31 30 31 31 28 31 30 31 30 31 31 30 31 30 31 31 29 Answer "YES"

*28, not 20

Edit: My bad, it's right

20 is n

Sorry

28 would be NO

OK I didnt see that you replied..

Nice. That case where leap year following/preceding a non-leap year took me a while to think of.

lol

Hehe...

Thanks a lot for the suitable contest time. Due to the inconvenience of the time zone, it's really hard for me to find a CF contest to enter when I am not sleepy...

// Although today I realized contests wouldn't become easier for me when I'm awake :(

Hints Clues Solutions anything for D?

http://codeforces.com/blog/entry/56391?#comment-400946

I'm not sure this is the right solution. I want to hear a solution for D too.

Yeah I was thinking something like that too but failed the pretest #4

k

The system testing is starting now, but upsolving, virtual participation and viewing solutions and tests will be disabled till the end of the olympiad in Saratov (around 2-3 hours from now). Hope for your understanding.

UPD: Everything is up now.

k fam

I was able to see solutions :\

I noticed the lack of graph, DP, combinatoric and geometry problem in this year Olympiad.

what is C pretest 5?

IMO that could be something like this: http://codeforces.com/blog/entry/56391?#comment-400944

that is B

Oops sorry!

overflow

DIV2 A IS SO HARD TO UNDERSTAND PROPERLY DUDE!

Wrote a simple stack solution for E after contest. I would be so suprised if it passes, but I dont know why it shouldnt pass. Is it possible that E is this easy? Edit: No its not, I didnt real statement carefully lol.

I think that order of removing matters, without handling that I got wa on pretest 7.

Order does matter, but I dont think it will be problem in my solution. We will see soon.

Everybody in Russia uses Gregorian calendar. In this calendar there are 31 days in January,

days in February (depending on whether the year is28or 29)... People like me have no idea that leap year means 29 days in Feb....leapor notwhen wil be rating changes

How to solve C without knapsack?

My approach: if n=2, just like pretest. else:

1.Put n in set 1 and n-1 in set 2.2.For each other element (n-2,n-3,...,1), just check (in descendig order) if it's better that the element goes to set 1 or 2.How to prove that always works?

there is some patern in these numbers the answer is always 1 or 0.

for numbers like — 5, 9, 13, .... (odd with difference > 2) you can always make (n-1)/2 pairs without the number 1 with a abs diff of 0. and then later add 1 to any other group. for example 5 = (1, 2, 3, 4, 5) = (2, 5) (3, 4) and the add 1 to any other set.

for numbers like 6, 10, 14,.. (even with difference > 2). you can make (n-1)/2 pairs with leftmost and rightmost numbers. the middle two numbers with go to either sets which give difference 1. 6 = (1, 2, 3, 4, 5, 6) = (1, 6), (5, 2), and then add element 3 and 4.

for other types of number- diff 0

if it is odd remove the last number. make pairs with leftmost and rightmost number.

8 = (1, 2, 3, 4, 5, 6, 7, 8) = (1, 8) (2, 7), (3, 6), (4, 5)

7 = (1, 2, 3, 4, 5, 6) = (1, 6), (2, 5), (3, 4), (7)

I solved it using a simple approach.

find the sum of integer from

1toN.if sum is

evennumber then answer will be0otherwise1.in both the cases method of finding the numbers are same,do the half of the sum of

1toNand store it in a variable calledSUM.then start from

(i=N ; i>=1 ; i--)and do this if(SUM — i >= 0)thensubtract i from SUMandpush_back i into you answer.you will get your

answer vector.I also thought of same logic but could not submit correct code in time . btw how do u prove your claim?

I wrote down some test cases on copy and checked it manually...

you can think like this if you are subtracting a number from SUM and then your SUM becomes less than zero it means that you need to subtract a number which should be smaller than current number and i am going from N to 1 so it is sure that i will get that number.

I just wonder, if someone can tell me why I am disqualified?

probably because you cheated

how? how did he cheat. ??

What's the point in your reply?? If I cheated, why I would write such a comment and ask for any reason?

I would be grateful if any of organizers pm me directly and explain the reason.

Because you, Birjik, used fresh account to take part. It's ugly, unethical, disrespectful to me and the community.

How did you know? There must be other users using fresh accounts too.

I wonder how did you detect his fresh account through his submissions?

First of all, it's not Birjik even though we do share same template code.

Secondly, my real username is banned from CF (due to I cheated once a few years ago) and I gave you my sincerest apologies for that (several times), and asked to be unbanned in my real account.

After several attempts, I even changed my PC and could somehow login and was eligible to participate in contests from my original account, but some times later, I couldn't even login into my account. After 5 mins of logging in, the site takes me out and I have to login again. Moreover, in most of the times I can't even register to the competition (due to my account was banned).

I already noticed organizers about that issue. Didn't receive any reply. Okay.

Well, so I decided to create my new account since I can't normally participate in competitions from my original account and this decision was made by me not because I do wanna cheat, I just don't have any options.

How to solve problem-F?

I saw some submissions for D with Digit — DP. Can someone explain their solution using Digit — DP ?

for problem C: I noticed that the difference between every two adjacent numbers is 1. So if n is even, there will be two situations:if n/2 is even, answer is 0, or answer will be 1; Similarly, if n is odd, there are also two situations:if n/2 is even, answer is 1, or answer will be 0;

What could be the case 13 of B ? My solution didn't pass that :(

http://codeforces.com/blog/entry/56391?#comment-400944 I guess.

Thanks

Good contest, the problemset was perfect. We want more contests like this.

Yes very true. All-Russian olympiad problems are good

Hi,MikeMirzayanov,can you tell me why I got disqualified? I didn't share code with anyone else.

Because you created fake account to participate bro. It's ugly, unethical, disrespectful to me and the community.

Because you (maybe a group of people, and I'm not sure who) used a fresh account to take part. It's ugly, unethical, disrespectful to me and the community.

I wonder how these two accounts can participate round 441 at the same time with different codes and different verdicts...

whats wrong with using a fresh account to take participate. i don't get it ??

Maybe it is because of this comment

It's a rule.

I want to know why I got disqualified,too.I didn't share code with anyone else,either.

My friend eselppa got disqualified in yesterday's contest too, he solved all problems by himself, he didn't cheat, I can prove it. The reason why this account's ID is very similar with mine is that he wants to play a joke to me. That's not my account.

But he used fresh account to take part. It's ugly, unethical, disrespectful to me and the community.

Didn't you also use a fresh account to take part when you first participated. It's ugly, unethical, disrespectful to me and the community.

Exactly correct.

I found a new problem ... How many "It's ugly, unethical, disrespectful to me and the community." in the replies of this comment. since the answer may be very large print it module 10^9+7.

UPD: You also have to consider the occurrences in the replies after this reply.Stop making jokes about cheating, it's ugly, unethical, disrespectful to me and the community.

Good god how did this become a memeful copy-pasta so fast dude. I mean it's ugly, unethical, disrespectful to m-

Why I can't submit now?? The contest is over and the system testing has finished ...

Refer this http://codeforces.com/blog/entry/56391?#comment-400964

Now you can submit~

hello in your contest in b problem you gave test cases that there is two contiguous leap years but its impossible in real (one of them is test case 13) please correct it

Leap years are ones with 29 days in February not 28.

my bad :(

The problem B condition was not, in fact, overly clear regarding what leap/non-leap year is.

It seems that the author(s) treated that knowledge as an implied one.

(Although, there is the

February (leap year)reference in notes, when explaining the third example, where`29`

is present.)Look at all the people who failed problem B. They all did same mistake as you. It's because of the problem statement, January, 28 or 29 days in February (depending on whether the year is leap or not) , which gives an idea that correspondly leap has 28 days and not leap has 29 days.

Can anyone please help me figure out what's wrong with my C solution http://codeforces.com/contest/899/submission/33345251 it fails on pretest 8 :(

UPD: got it xD

Hello, I found a very weird bug in my code for problem E. It works fine for many test cases except for the case when n = 2 and the 2 numbers are distinct. I checked on my local machine and it gives the error.

Checking on gdb, I find that the pointer

`majt`

remains the same as`mait`

, even though I'm doing`majt--;`

which should make it`ma.end()`

if we are removing the first number (Note that this works for other test cases, i.e. n!=2, even for n=1). I'm unable to figure out why. Any help would be appreciated. Thank you.Code ID: 33351982

Well,the time is best for Chinese!We always had to stay up late for the CF round :(

666!

Relatable here, GMT+7 :)

Why are submissions not being judged?? I submitted 4 hours ago and it still writes "in queue" as status. :/

Why crash?

http://codeforces.com/contest/899/submission/33344155

You are erasing from set at the same time you are iterating over it. So when you delete an element the inner structure changes. You should create a temporal set and erase from it

Wrong answer on test 7 on problem F. Anyone have any idea? I am unable to find my bug. I have tested several cases but couldn't find anything.

Here is my submission 33357864

[Deleted] I post it on the wrong topic.Sorry.

What's problem with this E code? 33382017

Hi,MikeMirzayanov,can you tell me why I got disqualified? I didn't share code with anyone else.Please give me a reason.

Because you, czr, used fresh account to take part. It's ugly, unethical, disrespectful to me and the community.

Oh, you're really ugly, unethical, disrespectful to me and the community. As far as I'm concerned,you,it's your third fresh account! You should be banned by MikeMirzayanov in no time. And I can't imagine a more ugly and unethical behaviour than using a fresh account to point out that I used a fresh account!

What's more,I do not use a fresh account and it's the first time I participated in a CF Contest!

I've been stuck for ages... anyone know what test #33 was on div2E? http://codeforces.com/contest/899/submission/33345602

My answer is 1 + the correct answer. :(