Добро пожаловать на очередной раунд Codeforces!
Обратите внимание, что время раунда #191 изменено. Раунд начнется в четверг 16:30 MSK.
Меня зовут Linh (ll931110), я из Вьетнама, и я рад представить для вас мой первый раунд Codeforces. Раунд будет Div. 2 onlу; однако, я приглашаю Div. 1 участников посоревноваться и получить удовольствие от непростых задач. Я надеюсь, что этот раунд — хороший подарок для тех, кто участвует в IOI 2013 (а также участников финала ACM ICPC). Заметьте, что раунд будет проводиться всего через пару дней.
Раунд подготовлен мной и fchirica (из Румынии). Традиционно, я хочу поблагодарить команду Codeforces, которая прикладывает много усилий, чтобы поддерживать Codeforces и Polygon.
Приятного решения задач!
UPD1. Будет использоваться динамическая разбалловка. Задачи при этом расположены в порядке предполагаемой сложности.
Вьетнамо-Румынский контест...интересно)
Я думаю, это заслуга организаторов: у одного автора были одни задачи, у другого — другие, они их совместили.
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.
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
Смотрю текущих лидеров, которые "не в рейтинге"... мне одному кажется, что здесь что-то не так? Или просто новичкам везет? :)
На div2 раундах часто так бывает
Из-за того, что это бывает часто, оно не перестает быть странным. Лично у меня, такие участники вызывают единственную ассоциацию: Ералаш — Самый умный
Missed it, didn't notice the time change :( please try and avoid this in future, not many of us keep checking the time..
Что неправильно в этом решении? http://mirror.codeforces.com/contest/327/submission/4020058) (точнее, что надо сделать, чтобы оно зашло)?
Во-первых, возводить надо по модулю. Питон не потянет 2^100000 за 1 сек. Во-вторых, зачем делать это вручную если в питоне есть встроенная функция pow(x,y,z), которая возвращает x^y по модулю z, причем работает за O(log(z)) и в данном случае не будет использовать длинку.
спасибо, понял, как надо было
Скорее за O(log(y))
Please see Submission http://mirror.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
Когда будет разбор ?
5 минут назад
How to solve C?
http://mirror.codeforces.com/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://mirror.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://mirror.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?
И опять в div2 контесте в топе куча только что зареганных людей..
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://mirror.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://mirror.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