Fox Ciel is back!

I invite you to participate in Codeforces Round #290, which will start at the standard time on next Monday:

This is my 4th round on Codeforces, my previous rounds: #190, #228, #270.

Last Div1 Round (#286) is so hard, so after notice that, we decide to reduce the difficulty of this round. (For example, current Div1-E was used as Div1-D) I hope more people can enjoy all tasks in this round: this time no task requires advanced knowledge like linear space or Fourier Transform.

The background story will be Fox Ciel's life: learning programming, play games, traveling, have dinner and so on.

Like Round #228, top-20 contestants that are currently at Petrozavodsk training camp will be rewarded with nice Codefores T-Shirts. Contestant may be a team member, jury, coach, organizer, or whoever else involved in camp, no matter of status.

As usual, thanks to Zlobober for giving great suggestions and test my round, and MikeMirzayanov for the platform (Codeforces and Polygon).

Good luck and have fun!

**Update1**: Score Distribution is ... Div2: Standard (500 — 1000 — 1500 — 2000 — 2500), Div1: a bit unusual ... (500 — 1000 — 1500 — **2250** — **2250**)

**Update2**: Editorial: http://codeforces.com/blog/entry/16173

**Update3**: Congratulation to our winners:

Div1:

They are all people who solved 5 tasks!

Div2:

Nice! I love your contests! Always I think that a little easier problems are better.The best programmers will certainly be in their place,and other competitiors will get more fun.

i'm not in Petrozavodsk training camp, but i want t-shirts too :)

ooops sorry, i just kidding.

"advanced knowledge like linear space" :P

hmm, i always thought that Bredor_228_Jaguar_Turnik was the author of Round

#228. ;)Look at his head carefully in his profile photo :)

Doesn't using the current Div1-E as Div1-D make it

harder, not easier? The D task will be hard as E task, and E task will be even harder!It means the previous D will be the current E.

actually, minimario's translation was correct. It seems that the author has his wording wrong.

Maybe you are right, I'm not good at grammar. Then how to express it properly?

It should be:

"For example, the previous Div1-D was used as the current Div1-E."

I parsed it as "the upcoming Div1-E was initially supposed to be Div1-D". But the points is this round is going to be easier than the last Div1 round, at least according to the author.

The contest is from China. The time is 19:00 in Russia it means 00:30 in China! an it will last for two hours that is 2:30 AM! Will you be awake that time? :D

Anyway, Thank you for the contest... It's my 100th contest and I'm really scared because my rating change in your last contests was : -54 , -74 , -127 :D

UPDATE: This time my rating change was -106 :|cgy4ever...

Afaik, cgy4ever is from China, but not in China.

It start at 8:30 am here (California), I hope I can get up at that time.

We all get used to competing programming contests at late night, since almost all contests of Topcoder, Codeforces, Hackercup and GCJ are hosted on bedtime in China (UTC+8). So I'm sure cgy4ever would be awake if he were in China (But he is in US now, Chinese topcoders always get up late :P).

.

next one -213

last time your rating change was -127,this time -106, so that's an improvement by +21 !!!

Didn't provide much help to Fox Ciel in last round . Will try to impress Fox Ciel atleast this time

Thank you for making this contest :)

YES

A CGY4EVER ROUND

!!!

finally a Div 1 + Div 2 round after 4 continuous Div 2 only rounds :)

Congratulations on advancing to the onsites of Facebook Hackercup cgy4ever.

Thanks!!

Now I've advanced to nearly all big onsite finals at least once: GCJ(2011), TCO(2013,2014), Yandex(2014, but can't participate due to visa issue), FHC(2015) and ICPC(2015).

best of luck for the final

~~~~~~~~

you did it once before, i believe you can :)

twice :P

I did it!!

I've registered but I might not be able to participate. Will my rating be affected if I never even open the contest page? (like on TopCoder).

Your rating is not affected if you don't make any submission. (You can open the problems and decide to leave if you don't want to submit without any rating change.)

I wish good rating for all

But that will never happen :(

I Love my rating :

1616 :))

then you shouldn't participate in this contest or your rating will change :)

Maybe it change to 1717:)

17 — it's not good number. Need 3232 or 88 =)

need 228 :D

I see, you decided to make this rating. It is more easier than make 1616 or 1488.

Maybe his/her rating change will be 0 :)

Shame on you :(

Why ?

Why? because Shakespear died on that year?

Dixtosa Giovanni Battista Agucchi died in 1632 :p

No, He died on 1623 :)

hoping to taste div1 after the competition

Its good that its two division contest, otherwise merging it results in some weird rating change like #270 and GoodBye 2014 because too many top coders registered for this round.

My first contest, wish me luck.

My first Div1 contest, wish me luck.

Good luck.

Get ready to rumble!

Good luck

Wow, over 6000 registrants in total. Can CodeForces handle it?

Apparently no. I cannot open the first problem.

Why I can't hack other code?

Make sure you locked your solution for that task first.

And make sure you are in the same room with that person.

He's only submitted problem A. And I really can't think of a bug someone would have in coding such a problem. :) I think he asked why nobody has made mistake in implementing A. :D

That feeling when you hacked tourist :))

Liar!

No it was mkirsche that hacked tourist, Ximera was just pointing it out. I was also confused at first.

That alone made this a successful contest as far as I'm concerned. :D

Oh! TAT! In my room,only I locked the code!And I was waiting a coder locked his code then I will hack him! But when I found a coder has locked his code,he used java and I can't hack him.I am so sad! Maybe I should average up and I can go to the div1....

You can hack any solution, not only those that are locked. (Of course, hacking an unlocked solution means the owner can still get to fix it.)

what was the hacking case in div-1 A

2 bacrr bac

it should be impossible

thnx missed it completely ....and got hacked :(

I handled this case, still got WA in test 12 :(

same :(

Then try test 3 a ba bb. You may have counted one inequality twice.

I did that as well. Still WA in test 12. :(

same :( :(

Try this 5 page ping pile care array

ans is not impossible

Have you guys figure out test 12 yet? I cannot see the whole dataset.

Possibly it is

But I am not sure if it is a valid test case

I suppose something like 2 abcx abc

What's test 12 for Div1-A?! I can't see full test. It's a huge test and shows "...". I try all of the special test cases mentioned in this post but my code still shows "Impossible" instead of "abcdefghijklmnopqrstuvwxyz" (the answer for the test 12). Here's my submission: 9688819

So what's the solution for D?

It seems that we need to ignore nodes contained in a cycle, and do a DP on the resulting forest. I had a

O(N^{4}) DP for solving a single tree, but I'm afraid it would TL (especially with recursion). Then I thought that to count the number of eliminations of sizek, we need to count the number of subtrees of sizetreesize-k, which results in aO(N^{3}) DP, but that totally ignores the order of elimination. Is there aO(N^{3}) solution after all?To solve a tree of size

SI used this algorithm: for each node, find the number of ways to removeKnodes such that the node is not removed (ifK<S) or is removed last (ifK=S). Then an ending subtree of sizeNis countedNtimes (once by each of its member nodes), so we adjust for overcounting by dividing byN.O(N^{4}) with 3 seconds TL (and nothing else that could have the same complexity) and only in one small loop? Plus withO(N^{3}) memory? I'm pretty sure it would work if you don't do something utterly stupid.For some reason I still have the impression (from sometimes before) that anything more than 10

^{8}is slow. Time to forget that and move on :)Depends on what it is. Processor instructions: no. Actually 4 times (common with DP) less simple C++ instructions: no. Insertions in a map of constant size: probably yes.

It's better to risk it and find out in such a case.

We should exclude not only cycles but some other vertices too, for example if cycle is conected to another cycle etc.

We have rooted trees (connected to some bad vertex), and unrooted trees... and well I in both cases we can compute the answer using dp in N^3. Then we can join answers for trees using binomial coefficients in O(TN) where T is number of trees.

But I didnt have enough time to debug my solution, so maybe it's wrong.

What I meant was that we should exclude nodes that are part of some cycle. That includes your case :)

Yeah, I think you were doing it the right way.

great contest i'm waiting for your next contest thank you

Last minute, CF was down! I couldn't submit my

`A`

solution :( Actually I solved`A`

but I was waiting for solving another problem too, after I submitted`B`

and Got Pretest Passed, I wanted to submit`A`

too. Which is now undone thanks to codeforces :Di wrote a submission for b, but haven't ten more secs to submit(

my last round i submitted C 2 minutes before the end.) nevertheless, i need more time to get div1 membership :/

what was the solution for div1 b or div2 d? I tried pd with a knapsack, but the numbers were to big i think for that. Are there some tricks for big numbers? or is there another approach?

A linear diophantine equation:

a*x+b*y+ ... =nhas a solution if and only if GCD(a, b, ...) divides n. Since we want that to apply to all n, then the GCD should be equal to 1. The solution is DP with state (i, GCD) (last used card and current GCD of cards). We can use a map to store the states since the number of different possible GCDs is quite small.that was also my idea, but forgot the fact that the number of GCD is small. thanks!

How to prove that the number of different GCDs is quite small?

Because it should be the divisor of some number

a_{i}anda_{i}≤ 10^{9}. Numbers in that range can't have many divisors (less than 100 I believe).EDIT: Ooops, my guess was wrong, thanks for correction Andrei1998!In fact, 735134400 has 1344 divisors, so a safe guess would be 1500.

"linear diophantine equation" is probably an overkill ;-)

Basic number theory: Given

xandy, their smallest positive integer linear combinationspc(x,y) is given bysx+ty=spc(x,y) =gcd(x,y). You just need to find the minimal cost subset such thatspc(a_{1},a_{2}, ...,a_{k}) =gcd(a_{1},a_{2}, ...,a_{k}) = 1.Note that gcd converges quickly as the subset size increases, assume that integers in the subset are distinct.

Overkill or not, it's how that type of equations is called. Then again, anyone who has done a bit of number theory knows what a diophantine (I imagine the name doesn't sound horribly different in other languages) equation is, not to mention linear.

"A linear diophantine equation: a * x + b * y + ... = n has a solution if and only if GCD(a, b, ...) divides n"

Is there a proof for this?

I can't find one right now, but this might help (see generalizations):

http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity

Left side can be divided by GCD(a, b, ...), so should right.

Yes, you are right, the gcds are too big to do dp with them, but the right thing to do there is to note that the number of useful gcds is small enough (my calculation ended up being ~60000 different gcd's), so you can map them to 1-60000 and then do dp.

thanks! unfortunately, i'm not used to mapping and tried some tricks with big numbers, but they didn't work...

i definitely have to learn how to map

Best message ever :v (And definitely, I didn't submit that -_- )

thanks for A. sweatest shit I ever eaten...

WOW you have eaten shit ???

-YES FROM YR MOTHERS BUTT

Сum on!

Have you paid for Visual Studio ? :-)

Yep, obviously, and for uTorrent too

and Sublime :D

It's freely available to students (under some usage restrictions). Say, if you have ISIC card (or another proof of enrollment), you are eligible for DreamSpark program which includes a lot of Microsoft software free of charge (not for commercial usage, of course).

Div1 A

What's the answer for:

?

All the names are distinct.

There is no equal strings.

names should be unique

Didn't the specs say that the words are different?

Sorry, didn't notice that. I thought it will fail. Whew.

This problem can be solved by graph cycle detection, right? I didn't have time to finish the code.

Cycle detection -> impossible

Else, topsort

i thought the same :) .

How to solve Division1 C? Task looks like a Euler path, but I don't know how to solve it.

Although i have not participated in the contest but i think this problem can be solved using topological sort this way . Please correct me if i am wrong some where ..

We can take each pair of string and find the first miss match then we put a directed edge from one character to the other (offcourse miss match pair is taken) then find whether there is a cycle or not in the graph . if there is a cycle then it is impossible otherwise find the topological sorting .

He asked for Div1-C, not Div2.

No, a set of cycles.

You can notice that any two neighbours need to have different parities, so you have a bipartite graph describing possible neighbourings; you want to match each vertex of each partition to exactly two other vertices.

ai >= 2. Yep, only even lenght, I miss this restrict. Thx

Is it correct to find one bipartite matching then remove the edges of this matching from the original graph and find a second matching? I wrote the solution and it passed the sys.tests, but I couldn't prove it's correct.

It's not correct. Try test:

6

10 2 26 5 3 9

or its permutations. System tests are weak.

UPD: The following proof that we need two perfect matchings is correct, but finding two perfect matchings sequentially does not always work.

"=>"

Each breakdown of graph into cycles can be divided into 2 sets of edges, "left-to-right" and "right-to-left". Each node from left and right part has exactly one edge of each type incident to it. Therefore, each of such sets of edges forms a perfect matching.

"<="

For a pair of two edge-disjoint perfect matchings we get a set of edges such that each node has exactly two incident edges. Since the degree of each node is even, there exists an euler tour in each connected component. Each connected component has exactly

Knodes andKedges, therefor the tour is also hamiltonian. Since each node has at least two edges, each component has > 3 nodes.A flow solution finds this order: 1 5 3 4 2 6

Ah, I see. So the idea about two perfect matchings is correct, but finding them sequentially does not always work.

The answer exists:

9 10 3 26 5 2

For D1-A, what is the correct answer for this case?

According to this sentence:

But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical!Should the answer be

`Impossible`

? Since you cannot do any modification to make them lexicographical...I think this problem is ambiguous on this case. Could the author clarify?

Edit: well my solution outputs`abc...z`

on this case. However, my friend's outputs`Impossible`

, because he was struggling to resubmit his hacked solution on this multiple times without success, to the point that he thought the wording of this sentence was actually the tricky case.Identity modification :).

some modification usually means no modification too.

No the answer is just the normal alphabet. I think this is pretty clear.

Aren't they already lexicographically sorted? Edit: Oh, I see what you mean.

Did somebody made mistake of writing "Impossible" as "impossible"? :P

would that pass the pretests?

Of course, no.

Obviously not, as the answer for one of samples is 'Impossible' :)

Me!

I accidentally wrote impossibru though

i made mistake of writing "YES" instead "Yes" :)

How is Div1 B solved?

Thanks a lot for the nice C problem :) It is clear experienced coders must have seen it before but I was happy once I figured out the max flow solution. Then, I ran out of time because I didn't know how to restore the flow, and had to spend some time debugging >.<

Very nice problems cgy4ever, thank you :)!

Thanks for this round. Though my rating will decrease I learnt a lot . Hope you will be setting problems frequently .

Did anyone else wrote randomized algo for Div1 E? (・_・ヾ If my solution pass, I would probably look like (☉_☉')

Edit: It failed (˘_˘٥)

DamianS got his random solution accepted.

What a bloodbath on div1 A! I missed the opportunity of being hacked.

My code (codeforces.com/contest/512/submission/9686628) got accepted but it writes "Impossible" with this simple input: 2 a a :))

Because all strings are different :)

2 a a is wrong test: "All names are different."

Thank you for such a wonderful contest!!

Finally in top 5! Congratulations to winners and big thanks to those who created this nice contest for us.

Best contest since I am on codeforces :) Thank you :)

Codeforces was working perfectly during last 10 minutes. I've read so many codes, challenged so many people during that time! To help u guess how many, i say that factorial of this number is 1

so 0 or 1 ?

Contests -> Click at place.

0

Great contest with good problems,I just didn't know about 'topological sort' before the contest,and learn it during the contest ;)

Very nice problems. And finally I can become international grandmaster, really excited!

My short sad story:

I had A and B and it was like 15 minutes to the end. I didn't have any good idea for C/D/E so I wrote some simple greedy-random solution to E but I wasn't able to submit it during last 2 minutes. And now my code from contest passed all tests: link to solution

Ofc. AC with this solution would be a bit unfair but still I'm just sad... 155-th place vs. ~24-th place :(

Why is this Div 1 B solution failing the system test cases. Please Help. http://codeforces.com/contest/512/submission/9690331

So easy question... Cause answer was wrong :|

Are you sure it's okay to modify the container which you are currently iterating over? I guess that could be the source of the bug.

I used unordered maps. So I guess it shouldn't modify the container which i am currently iterating over.

Iterators are invalidated when you insert into unordered_map: http://en.cppreference.com/w/cpp/container/unordered_map/operator_at. Try to replace by std::map.

My goodness :D ... I chose to use unordered_maps other than maps at the last moment... God has been very kind to me :D ....Thanks anyway for finding the bug :D

Won't there be a rating change for this round?

Still Pending

still same :)

My rating increased by ranking 266 ?!?!

Whoa, and here I was regretting not realizing C was a flow problem sooner and complaining about how terrible my performance was...

Though I wasn't fast enough to solve it during the contest, problem C was really nice. A very good contest overall!

Actually your rank was 266 and your rating increased by 90! :P

Exactly. I wasn't expecting that! After the contest finished, I could have sworn I was going back to purple...

Lucky you!

Слабые тесты в задаче B первого дивизиона! Моя программа, получившая вердикт "Полное решение" даёт неправильный ответ на тесте: 9 9699690 111546435 74364290 44618574 31870410 20281170 17160990 13123110 11741730 1 1 1 1 1 1 1 1 1 числа l[i] сконструированы так : 2*3*5*7*11*13*17*19, 3*5*7*11*13*17*19*23, 2*5*7*11*13*17*19*23, 2*3*7*11*13*17*19*23, 2*3*5*11*13*17*19*23, 2*3*5*7*13*17*19*23, 2*3*5*7*11*17*19*23, 2*3*5*7*11*13*19*23, 2*3*5*7*11*13*17*23. Поэтому наименьший набор l[i], имеющий наибольший общий делитель равный 1 содержит все 9 чисел l[i]. Поэтому правильный ответ на данный тест 9. Однако моя программа, зачтённая на codeforces даёт ответ 8 (не та программа, которая прошла претесты во время соревнования, а которая была отслана после окончания соревнования).

Что не так с моим комментарием?

You wrote that comment in Russian, but posted it as English. Many people who use English version of CF see your comment and can't understand.

Thank you.

Weak tests in problem B of Div.1! My program that got AC gives wrong answer on test: 9 9699690 111546435 74364290 44618574 31870410 20281170 17160990 13123110 11741730 1 1 1 1 1 1 1 1 1. Numbers l[i] are constructed so : 2*3*5*7*11*13*17*19, 3*5*7*11*13*17*19*23, 2*5*7*11*13*17*19*23, 2*3*7*11*13*17*19*23, 2*3*5*11*13*17*19*23, 2*3*5*7*13*17*19*23, 2*3*5*7*11*17*19*23, 2*3*5*7*11*13*19*23, 2*3*5*7*11*13*17*23. So the least set of l[i], that has gsd equal to 1 contains all 9 l[i]. So the correct answer to the test is 9. But my AC program answers 8. This is my comment.

Nice problem set :)

DIV 1 C --> Awesomeness!! Thanks cgy4ever!! :D

How this contest can be rated since I did not connected to codeforces at least an hour ? Is that just happened to me or everyone ? I can not send my solution to B because of the network problems and now I got -80 :( I WANT MY RATING BACK !!!

Just to you. Codeforces wasn't running so smooth, but rest of people were able to send their codes and get the verdicts.

Russian page has no links to editorial nor winners of Div1 / Div2. If anyone can fix it then do it please.

Added them in Russian version, but in English since I don't speak Russian.

Take a look at this solution of div.2 D/div.1 B please. Where is bug? (WA on 24th test)

Here. for (int i = 0; i < N; ++i) { cin >> c[i]; dp[l[i]] = c[i]; } Nobody guaruanteed that l[i] is not in map already. You will just lose too much information if l[i] overlaps with another one.

Sure! Thanks for help.