Welcome to another Codeforces Round!

**Please note that the time of round #191 was changed. Contest will start at Thursday 12:30 UTC.**

My name is Linh (ll931110). I'm from Vietnam, and I'm glad to present to you my first Codeforces round. It is for Div 2 only; however, I welcome participants from Div. 1 to participate and enjoy challenging problems. I hope this would be a pleasant gift for those who are going to IOI 2013 (and participants from World Finals), which will take place in just a couple of days.

This round is prepared by me and florin.elfus (from Romania). Also, I would like to thank the Codeforces team who puts efforts on making Codeforces and Polygon possible.

Happy solving!

**UPD1**: The score of problems in this round will be dynamic. The problems will be sorted in increasing difficulty order, at least in our perspective.

**UPD2**: The contest is over! Congratulations for everybody, especially for those who solved E. You proved to be smarter than I am (your solutions were totally unexpected to us). Thank Gerald, Aksenov239 and Delinur for helping us on preparing the round!

Div. 2 winners:

Those are five people who nail all problems!

Unofficial winners:

The editorial will be completed soon after revising and adding possible alternative solutions. You are welcome to post your answers in comments.

Thank you and see you in the next round!

**UPD3**: Editorial is now available. Remind that it is not the final version, as we are writing possible alternative solutions for problems. Stay tuned!

**UPD4**: Editorial is now completed.

Thank you for the contest!

And I hope your first round will be successful!

i think contest's date is late for some IOI participants.

It's div2, man

And what? IOI participants on div. 2 it's also exists, and number of them near half.

It's just that I doubt that competitive IOI participants have a great desire to solve div2 problems. And aside from that, it turns to be "contest date is late for some people", which is common.

How to read your nick?)

this is how: ll931110

I mean, for example: JKeeJ1e30 reads like "Zhelezo" which mean "Iron" in russian. JK is like russian letter "Ж". Another letters in this logic.

"llninethreeoneoneonezero"?

Maybe it like. II means 20 century. 93 means 1993 year when he was born. In this logic 11 means 11th month(november) and 10 is day.

He's vietnamese and his name is Linh, starting with a "L", that's why "ll"

ll is his name. and 931110 is his birthday. you can read what ever you want :)

Our flight to Australia should depart 20 minutes after the start of this contest, but we'll participate if the flight is delayed. :)

nice, hope there is always 1 contest per week at least :D

Oh the first CF round made by Vietnamese. As a Vietnamese, I'm really excited !

care?

It's a pity that our school have to cut off the internet after the midnight, so I only get 30 minutes to work out and submit my solutions. Can you suggest the officials to start the contest a little earlier if it doesn't bother most of the coders, that would be lovely.(Ps I'm in China)

I have the same problem and I came from China too. Also our school would cut off the internet and power when the CF contest start(7:30pm MSK) by coincidence.But I always use my phone to create wifi hot spot to porovide network for my computer,then I can participate in the contest.I think the contest start little earlier will bring great convenience for Chinese participants.

My mobile phone operators is CMCC, as a result I can't create a hot spot.T^T

It is very unfortunate that the start time has been moved. I was very much looking forward to this contest.

Thanks for preparing it, anyway.

almost missed it. why time changed? :/

admins will be on train at default time

Missed it, didn't notice the time change :( please try and avoid this in future, not many of us keep checking the time..

Что неправильно в этом решении? http://codeforces.ru/contest/327/submission/4020058) (точнее, что надо сделать, чтобы оно зашло)?

Во-первых, возводить надо по модулю. Питон не потянет 2^100000 за 1 сек. Во-вторых, зачем делать это вручную если в питоне есть встроенная функция pow(x,y,z), которая возвращает x^y по модулю z, причем работает за O(log(z)) и в данном случае не будет использовать длинку.

спасибо, понял, как надо было

Скорее за O(log(y))

Please see Submission http://codeforces.com/contest/327/submission/4018453 . I use the data 100000 to hack it . When I run this code(I type it by my own on contest) on my PC , I use 10+ s. On the custom test , it speads 3s+. However , unsuccessful hack , it says that only use 78ms . WTF ? What's wrong with codeforces ?

it's normal(i had unsuccess. hack too). mb it's because when you run code in debug mode it works slow.Remember about optimizations. Or if you type n manually it will use about 0.5 sec :D .

Today many solutions(sieves,bruteforces) passed TL. if n was 10^6 , it would be cool

Thank you very much

run it in "Custom test" on Codeforces

see this----On the custom test , it speads 3s+.

sorry, but now it use only 216 msec. mb it was a bug

how did the system testing complete so early this time??within 5 minutes

Wow amazingly fast system testing!

For problem E, In case of k = 2, call smaller k1 and larger k2. My idea was to find number of permutations having prefix sum k1 and k2. Then find the number of permutations such that it's initial prefix has some k1, and some other initial prefix has sum k2. how do you solve the just above part?

This has got to be the fastest system testing and rating change in the history of codeforces!! :O

very good and fast system testing today! :)

well done guys, it was a good contest! the only thing lacking was hacking possibilities, next time try to exclude some (not all, mind you! :D ) corner cases from the pretests!

thank you for the interesting contest!

Nice problem E indeed I love it :)

when k<2 the problem is easy

when k=2 the answer is:

answer = n! — (the number of permutations that passes k[0] + the number of permutations that passes k[1] — the number of permutations that passes both k[0] and k[1])

to calculate the number of permutations that passes both k[0] and k[1]:

find the number of ways to choose two Non-intersecting sets from the the input integers so that the sum of elements in first set is K[0] and the sum of elements in the second set is k[1]-k[0] (assuming k[1]>k[0] if not swap them) then for each way we have (u! * v! * (n-v-u)!) permutation satisfy condition above where u is the number of elements in first set and v is the number of elements in second set

to calculate the number of ways to choose two Non-intersecting sets from the the input integers one can use meet in the middle attack but the number of permutations depends on the size of two sets so:

for i=1 to N do

for j=1 to N do

let P = the number of ways to choose two non-intersecting sets from the the input integers so that the sum of elements in first set is K[0] and the sum of elements in the second set is k[1]-k[0] and the first set contain i integers and the second set contains j integers

add to answer i! * j! * (n-i-j)! * P

end for

end for

this is my guess to problem E , I didn't code it so I'm not quite sure that my idea is ok

How to compute P?

use meet in the middle attack to compute every P in O(3^(N/2))

very nice problemset&tests congratz authors:D

Someone can give a detailed explanation of problem C. During the contest I figured that the answer is sum of f[i], where f[i] is calculated when the input string has 0 or 5 at position i, and f[i] = sum( C(k, i) ) , where k goes from 1 to i — 1. The problem was that I knew how to do that in O(n*k) which is infeasable for the problem.

Thanks in advance.

How to solve C?

http://codeforces.ru/blog/entry/8274

I fail system test #24,but in custom test I run with 656ms.In theory，my algorithm is O(n).Can someone tell me why I got a TLE? my code http://codeforces.com/contest/327/submission/4012901

There are more than 10^5 primes between 2 and 2000000. So, finding primes upto 2000000 is more than enough. It will improve the runtime significantly. My code also calculated prime upto 10^7 and I got AC. Even with a slight modification (strange, but replacing printf with cout) your code http://codeforces.com/contest/327/submission/4021421 got AC.

So strange！cout is more slow in theory, isn't it?

yah it's strange! that's why I submitted your code 11 times to test only. Actually there is another very fast O(N) solution that even doesn't need sieve :-)

Can print the big number and every pair of number's divisor is less than 2,because 2 is the smallest factor.

What about print i, from 10^6 to 10^6 + n ? :D

It is rather easy to calculate all primes between 2 and 10000000 in < 300ms. 4022940

The problems are pretty straight forward...

Fantastic problem set for your first Codeforces round. Congratulations! Keep on programming :)

E's test case didn't catch overflow in calculating sum. (meaning it didn't have the case where overflow in calculating sum cause the sum of some subsets equals 'bad luck' numbers). You can see my latest submission, which got accepted instead of WA.

pretty fast system testing and rating updates, i am impressed :)

and editorial :)

4019604 4017612 4017184

These solutions in fpc appear to be the same. Please check.

How to solve E with DP?

I don't usually post things like these... but I am very confused why I got WA on the very first test case of D. http://codeforces.com/contest/327/submission/4023027

In the end, doesn't my solution create the same towers in the same positions as the judge's solution? [EDIT] Note: please ignore the code, and jump straight to the very first test case output.

In the first line you should output 8 .

Oh oops... silly haha. Thanks!

Wow, there were only two successfull hacking attempts during the whole round!

what's even more strange, is that both were made by coders from the same room!! :D

http://codeforces.com/contest/327/room/25

What is more strange that XmanX first submitted a solution in which he outputs hardcoded value for n=1, which fails system tests. Then submits a solution in which he hardcodes output for n=2. His submitted time is 1:24:01 and solution gets hacked at 1:24:47. After which he removes the hardcoded output and gets accepted.

Great contest , i loved it . The problems were great , but if you look at eoy5ihz536 , 4mkf2bw9w6 and xhn4ws5gz9 ' s contest submissions , they are the same . Moreover they were submitted by 1 minute gaps for each problem . I think they are trying to cheat . Shoudn't this contest be unrated for them ?

When is the next contest scheduled?

[user: RR, 2013-07-04] what is this ? :D

why runtime error https://ideone.com/blTv29 i try so hard but i can't find the reason of that could you help me ?! and thanks in advance :)