Hello, Codeforces!

We are glad to announce that on 4th of June at 19:30 MSK Codeforces Round #306 will be held. Authors of this contest are me (Adilet Zhaxybay) and Timur Sitdikov (Timur_Sitdikov). The round will be rated for the second division, however, participants from the first division can, as usually, participate in it unofficially.

We want to thank all the people, who helped us to prepare the contest: Max Akhmedov (Zlobober), who helped us with the problems, Bekzhan Kassenov (Bekzhan.Kassenov) and Sergey Lazarev (SergeyLazarev), who tested the round, and Maria Belova (delinur), who translated problem statements. Also we want to say great thanks to Mike Mirzayanov (MikeMirzayanov) for creating Codeforces and Polygon.

By the way, as far as we know, Timur_Sitdikov is the first participant from Uzbekistan, who took part in the preparation of Codeforces round. We hope that everything will go well :)

Good luck to all!

**UPD** The scoring will be dynamic

**UPD2** Editorial can be found here

**UPD3** Congratulations to winners!

Round is over, thanks to everybody, who took part in it!

This will be my first Kazakh author contest :D I wish find interesting problems and many hacks ;)

This will be my first Kazakh author content :D I wish find interesting problems and many hacks ;) hahahahahaha pls Deader downvote pls me upvote

contest*

contest* a,b,c;

It took me a while to notice what you mean xDDD +1

thenk yu vry muccc i lov yu

And you got it ?

excuse me! maybe is not good place to ask but I don't understand: http://codeforces.com/problemset/problem/545/C

look at test case 7 why answer is 5? tree x=1 to left, tree x=41 to left, tree x=55 to left, tree x=59 to right, tree x=68 to left, and last tree with x=105 to right so we can cut down 6 tree and correct answer is 5 what's wrong?

tree x=68 cannot fall to the left because [59:66] is occupied with tree x=59!

UPD: plz ask such this questions in your own blog! ;)OK Thanks

after 59 is 68, and I didn't get that

Could you please go to the appropriate tutorial page to discuss? http://codeforces.com/blog/entry/17982

Your previous round was easy ( Never mind. I love easy round :D ). Hopefully this round will be easy too ;) Wish you two good luck and prepare more rounds for us :)

I instead, hope I learn something new from this round, participating and finishing a round without progression is not much of a good idea.

or simply it's unrated for you...

It's weird that recently ratings don't update as soon as past and editorials (except PrinceOfPersia) come late! what are doing there??

UPD: 2 hours passed and we are stared at monitor waiting for raitings and nothing happened!May be they are too busy to find the cheaters and eliminate them. It's an important task.

What methods they use to find cheaters ?

I don't know how they exactly find cheaters. But I guess, they may have some software which can find the partial matching percentage of pair of codes. Then they check the suspected codes manually to be more precise. But those are my thoughts.

even if they eliminate some cheaters, many cheaters are left (like bell-sama in previous contest)!

Why downvote him? He is right.

wow. I love your problems :D wish to see some easy problems like your previous one #round294 :)

I hope that this round will be good for all. Good luck.

hahahahahaha. the hope had tricked us.

Wish a standard problem set with strong data set :P

It's maybe second Kazak contest?

It isn't Kazak contest, it's

KazakhcontestAlso this contest is the third one)

Also, it is not only Kazakh contest :)

Asia Mix contest

Scoring?????????

This time they even not write that "scoring system will be announced later" ;)

Hope will be in div1 after this contest.

We all do :3 :P

Yes -_-

I know, I will be there :/

But just for 1 round :(

I do not have to hope. I know I will be :D

Fake contestant spotted.

Sherlock holmes spotted!!

You're not wrong. My deduction skills are not bad actually, but I can't take credit in this case ;)

Why so sure? Are you from div 1 and opening a new ID to attend as a div 2 participant? :P

Do you have any doubt?

I'm just poking him :P

As usual many fake div2 participants. So unfair.

Yeah, frustrating for noobs like me!

To me is no change , after all it happens everywhere .And it can excite me !!!

Life is unfair man ! you just gotta climb up to div 1 and i don't think you'll see any fake participants!

Why do they need to participate from fake profiles ? That is the question.

it's just exciting xD

Why It's exiting?? beeing the first when you know and frustrating other??

Example

Why would you attach a link to this very page? -_-

Keep trying and don't care about that!

Loved your previous contest! I hope I can do better in this one. :)

Problem D is nice, I like it.

Unable to submit :( Codeforces temporarily unavailable, it says :(

First experience with dynamic scoring, it was different and I liked it.

So many hacks with

`ABAAB`

and`BABBA`

!I'm also wrong.

Yeah...with that particular test case I got 12 successful hackings :P

My solution also got hacked . I resubmitted it lets see if it passes system testing .

Ouch, I got hacked by this one too. Thanks for this though, now to figure out how to fix it. Update: I see how to do it now, very clever :)

I figured the hack 5mins before contest ended. Coded it right in time, but not fast enough to submit

Who is stdioH? He or She regestered 12 hours ago

Thanks to authors for problem E, it was really nice!

Could you please give an idea of solution?

If last symbol is 1, then impossible.

If sequence ends with 1, 0, then result is always 0. So we will try to make at the end.

If sequnce consists only from zeros, and number of zeros is greater than 2, whe can place second and third from the end zeros to the brackets:

If sequence suffix is 1, 0, 0, 0, ..., 0, where number of zeros at the end is greater than 2, we can place brackets in a such way: , and now sequence ends with , so result is 0.

If sequence suffix is 1, 0, 0, than there are two cases:

1) If there is no other zeros in the sequence, answer is

NO.2) If there is at least one zero, which differs from zeros at the end, we can place brackets in a such way in a suffix which starts at the last of such zeros: .

UPD: It was a mistake in last case, but now it seems ok.it's not that complicated you can just do this

if(lastone == 1) NO calculate ans like this ((1 -> (2 -> (3 -> ...... n — 1))))))) -> n) if its 0 then nice else you can't do it! the proof is that i got my E accepted

Doesn't look like a div2E like solution at all :p but good thinking, I guess.

It seems that my solution does such thing in all cases, lol.

You can gamble in div2 when you're in Div1. Div1 guys have all the fun.

Damn, its so easy solution. Thx man :)

Tried to solve it, but failed on pretest 7, idk where I've got it wrong.

Am I right so if the sequence doesn't end on 0 its impossible to get 0 with this sequence?

yes, you are right But that's all I thought up:D

i also got wrong ans on pretest 7. following are all the conclusions i could make: (assuming array name is a[] and size is n) 1. if(a[n-1]==1) ans will be NO 2. for inputs like: 1(1)*00 ans will be NO 3. for all other inputs ans will be yes

For YES, output pattern is like this: 1. if a[0]==0 and a[n-1]==0: 0->(...)->0 2. for patterns like 1(1)*0(0|1)*0, output will be: [any arrangement for 1(1)*]->(0->[any arrangement for (0|1)*])->0

I don't know what other cases I am missing. Any type of help is most welcome.

Nice problems!

There were often not available to submit or to see someones code in the last 10 minutes.

Why is it that always the contests with dynamic scoring are some kind of weird ? :D

how to solve E??

try figuring out what's gonna happen if: last number is 1 last number is 0 first number is 0 first number is 1

after some thinking, you'll get the idea :)

Problem A is very nice. Short problem statement and a lot of hacks. Really enjoyed it! :D

Is 0 a valid input on problem C?

yes

It is non negative without leading zeros. I think it should be valid input.

i will get a wa on problem A

i could'nt submit my code in the last 5 min :(

I cannot hack other either. I guess there were too many submissions at that time so that the server couldn't afford.

I did 2 mins before the end !

I could not even pass the pretests of problem A. I believe I understood the problem wrong the whole time. Can anybody tell me what did the problem actually mean?

Such misunderstandings ruined my contests too many times during past. Apart from this, I do a lot of silly mistakes like, not noticing constraints properly, forgetting long long, giving less size to arrays or vectors (even did this today at problem B :D ) and many others.

I am just getting accustomed to be a freaking block-head-dull-brained person all the time.

Happy! ^_^

I found that my solution of A is completely wrong after locking the problem! -_- howeever, the problem says to check whether the given string contains both AB and BA as a substring. and AB and BA should not be overlapped (like ABA )

I have seen the pretest #4. It was

`ABABAB`

Yep I thought that NO

`AB`

should overlap with any`BA`

and vice-versa.Same here.

Lots of construction algorithms! Nice round!

How can I solve problem D?

for even k does solution exist ?? if anybody could tell it will be helpful

Nope, for even K answer will always be NO

I read a homework question and answer pdf of MIT, and it was mentioned that there does not exist any solution for even degree of all vertices, during the contest.

Currently could not find that link, will post as soon as I find it again.

Are there any solution exists for even N in Problem D?

I also could not find any ;(.

It can be proved that there are no solutions possible for even N.

nope. if every vertex in a simple connected graph has even degree, it can be proven that the graph has an Euilerian circuit. so all of the edges of the graph are at least in a cycle. so there are no bridges in this graph.

I proved it without the help of Euilerian circuit.

Assume the graph has n vertices. Then n*k must be even. If we have a bridge break the graph into two parts(one has a vertices and the other has (n-a) vertices), then a*k-1 and (n-a)*k-1 must be even too. So the only possibility is that n is even, a and k is odd.

Thanks. I just solved it. I was so close. Tricky problem :)

Another way to think about it is like this: Look at the right side of the bridge, without considering the bridge. The degrees of that subgraph, if it existed, would be k-1,k,k,k,k,k,k,k... Since k is even, the sum of those degrees is odd. In every graph, the sum of degrees must be even, so we win :). Edit: Practically the same as boleyn.su, didnt update fast 'nuff.

I also thought that way. But I took too much time to find this.

Can't find it on paper, but also couldn't prove that its impossible, so just give up and moved to E.

Assume that such a solution exists. Consider its "left" part from the bridge and including the bridge vertex.

kvertices in this subgraph have degreenand one (the bridge vertex) has degreen- 1. So, the total number of edges in this subgraph must beBut since

nis even, the numerator is not divisible by 2.Thanks :)

i locked one of my solution to hack others :D and bam... my solution got hacked :'(

With new feature of

highlight codedid impossible to hack for me, it was very slow, sometimes did not show the code :S. ¿ Anybody had the same problem? I use Firefox.I love the new feature :D, just I have that observation.

Problem A is so amazing, until in System testing :D

Editorial ? :D

!!!!! my A got WA !!!!! what's wrong with test 8 ? The answer is obviously YES why do they expect NO?!?!?!?!?!

As I see, Test#8: ABX repeaten many-many times. It contains AB but doesn't contains BA

Is there any "BA" in testcase 8? If not, then it's NO.

I think there is:

ABX ABXABthe first two ones and the 5th and 7th one make : ABBA

They must be beside each other.

So you can't take the fifth and the seventh one.

(They are looking for

substring, notsubsequence)I'm afraid you misunderstood problem

It says to find substrings "AB" and "BA" that not overlape. There isn't substring BA in test#8

Thank you :|

PNNB — How did your submission 11416298 with worst case complexity O(n^2) for question A passed System Tests? :O . Also i can see that there is a test like "ABXABXABX....ABX" just to make sure that O(n^2) with pruning like yours gets time limit exceeded .

It didn't pass system tests and it's O(n)

which submission r u seeing? Maybe i made some mistake in posting the submission link which still seems fine to me. I can see in green letters "Accepted" verdict there!

You're right.I was totally wrong

on problem A

ABABAB => YES ?!

Are you serious? you have only overlaps!!

A BAB ABso why is the answer to test 8 NO?

is that a sub-string ?

Fuuuuuu...!!!! I hadn't read the problem statement well :((

I think you misunderstand the problem, the two substrings that you find should not be overlap.

For example, you can find such answer:

`AB*BA*`

They don't overlap.

There are two non-overlapping substrings "AB" and "BA".

ABABABDidn't do well on this contest but I'm happy I got problem A correct!

What time does regexp require? 11433753 Is there any way to make regexp works faster in Python?

It was supposed to be O(n*s*_a_) where n is the length of the string, s is the number of states of the NDFA and

ais the average number of state transfer edges. However, it seems that Python implemented it another way.Your regexp has very big time complexity. Try to make it more efficient. Later you can see my submission with regexp in 31 ms (that's because of compiler's optimization).

The problem is backtracking, I modified your solution to prevent it. You can check it out here:

http://codeforces.com/contest/550/submission/11443577

Can somebody please explain dynamic scoring to me ? Thanks

Look here: http://codeforces.com/blog/entry/4172?locale=en

Thank You :)

how to solve b and c?

For B, you need to try all possibilities which are 2^N. For C, what you need to know is that a number is divisible by 8 if the number formed from its last 3 digits is divisible by 8 which means that if there is a number with K>3 digits divisible by 8, then there is also a 3-digit number divisible by 8. So you need to try all possibilities for 3-digits numbers, 2-digits numbers and 1-digit numbers.

im going to give you a hint on problem c to not spoil it.

c-> you just need to know that a number n is divisible by 8 if and only if its 3 rightmost digits together are divisible by 8 For example for the divisibility of 3213123123213888 you just have to check the divisibility of 888 which is divisible.

Why the stoi function not working in GNU G++ 11 4.9.2 :( Due to this I'm unable to submit at last minute. And when I uses stringstream my solution accepted.

Codeforces doesn't use a 'real' g++, but rather MinGW (a Windows port which has several bugs, including missing stoi and to_string functions).

yeah, MinGW bugs, which annoyed me when I want to use stoi and to_string()....How to fix these bugs, I tried but still not work

My worst contest YET!!!!

my A, B got WA!!!!!!!!!!!!!!!!!!!!!!!!!

but glad C, D are AC!

How it is worst? You have been able to solve D first time I think, I engrossed so much in Hacking, I read problem D little late and could not generate regular graph in time.

problem D was our homework some months ago!!

The exact problem D? Can you provide some link of some kind of resource? That would be helpful indeed. :)

Hey guys, editorial was posted here

I think it has a typo. It is showing dp[i][ai mod, 2015 - 06 - 04 8] = 1 instead of dp[i][ai mod 8] in the 550C.

Update the ratings man, so I can go to sleep.

Does anyone solved A using regular expression, I tried to solve A in this way instead of simple one. Forgot that regular expression takes exponential running time.

Does codeforces not support "to_string" function ? I get compilation error even with C++11 . http://codeforces.com/contest/550/submission/11434694

Compilation error is

program.cpp: In function 'int main()':

program.cpp:40:25: error: 'to_string' is not a member of 'std'

Yes. I think there should be a warning similar to the one for '%lld'.

Read the second answer here http://stackoverflow.com/questions/12975341/to-string-is-not-a-member-of-std-says-so-g It will work with C++11 on CF. I used it in some other problem yesterday.

my solution gives a weird runtime error for C — problem with error code -1073741510 both in my compiler and on CF but my compiler runs the code and gives this error as warning . http://codeforces.com/contest/550/submission/11430760 can anyone give any insights?

Holy mother of unreadable code...

Dude, i dont know anything about the runtime but as a friendly advice, i think you should code a little bit cleaner so atleast you can understand your own code. i closed it the moment i opened it.

sorry for being a little too straight.

Do you write code in Notepad?

Yes.gradually trying to move to codeblocks

O_O

O_o

o_O

o_o

0_O O_0 o_0 0_o 0_0 O_o o_O O_O o_o

In div2 A, I wa on the ABAB so sad.. D & E 's constructive algorithms is very ingenious! Have fun in this round！

^thanks shervin will take that into account in future :)

I love this contest because of very short problems without very long story.

Plz Give Rating.Wait a long time.

It is 2:45 AM, BST. Still waiting for rating. Tomorrow morning I have an internal practice contest. So, I should sleep now. :-)

Still awake for Rating and feel bored.

Hope I will become #Candidate_Master today. Nice problem set. Enjoyed very much :-)

Yeh!!! I made it. Now I am #candidate_Master. Hope I will become Master within 2 months. :-)

Congrats :)

My submission for problem C gave wrong answer on test case #22 but the same code gives different answer on ideone.com and my home compiler which is correct. Please tell me what is the issue. My Submission for contest : http://codeforces.com/contest/550/submission/11436093 Same code with test case 22 on ideone : http://ideone.com/Y82K0r

Most probably precision issues due to pow method, try resubmitting after writing your own exponentiation method using fast exponentiation in O(logn)

Don't get inspired by codechef. Please update the ratings ASAP.

Problems A, B, C very easy.

maybe you forget that this is div2 round o_o

you saying that because you are gost.

Problem E was also easy. I couldn't solve it during the contest due to my own silly mistakes. Solved it after the contest

Good (Y)

Two and a half hours after contest and rating...........

.

1700!

I Love This rate

A, C and E solutions with regexes: 11433416, 11435544, 11438339. Update: obsolescence's solution E — 11442038

For D, I constructed the graph like described here:

For k=99, it produces 965448 edges, so it is still within the constraints. Being correct, nevetheless, my submission 11429811 timed out. Guess it is just a problem of optimizing output.

I solved problem similarly. Use

`ios_base::sync_with_stdio(0)`

. Output is very big.My submission: 11424571

It is still too slow for his solution, proof:

http://codeforces.com/contest/550/submission/11444006

Iostream is slower by an order of magnitude in certain cases and there is no way around it.

`#define endl "\n"`

and you will get accepted =) 11444087Still takes 150% more times the time though.

This is why I never use cin and cout, they are too slow! Here, I rewrote your solution using printf statements and it passed in 340 ms!

http://codeforces.com/contest/550/submission/11443935

Thank you, JohStraat, very interesting. I learned my lesson!

Congratulations to the winners!

Div.2 winners:

gotze

ptnk130210

goodhope

kiana810

xwind

The correct rating::

1st place (gotze)

2st place (I_Love_Nodir.Daminov)

3st place (tun)

4st place (ptnk130210)

5st place (goodhope)

Congratulations to these actors for a successful result in Codeforces Round # 306 (Div. 2)

Just added winners to the post. Congratulations!

Thank you all guys, who participated in contest! It was fun for us :)

My code of (550A-Two Substrings) is showing hacked. Can somebody please tell what this means in context to this codeforces platform?

Also, I not aware of those terms such as "Successful Hack — 100 points" used in contests. Can anyone tell or share some blog or something related to this to know about these properly.

I am getting an error on problem D "wrong output format Unexpected end of file — int32 expected" what does this mean , can anyone help (http://codeforces.com/contest/550/submission/11450063)

D: my experience is low , if I can master more about graph , I believe I will enjoy more,

Sorry to take part in it late. I feel this is one of the top competitions I took part in. Requires no complex knowledge of algorithms and still the problems were tough. Thoroughly enjoyed the problems. Specially surprised to find red coders getting problem A wrong.