ll931110's blog

By ll931110, 7 years ago,

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:

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.

• +201

 » 7 years ago, # |   0 Thank you for the contest! And I hope your first round will be successful!
 » 7 years ago, # | ← Rev. 2 →   0 i think contest's date is late for some IOI participants.
•  » » 7 years ago, # ^ |   +13 It's div2, man
•  » » » 7 years ago, # ^ |   +7 And what? IOI participants on div. 2 it's also exists, and number of them near half.
•  » » » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   -8 How to read your nick?)
•  » » 7 years ago, # ^ |   +8 this is how: ll931110
•  » » » 7 years ago, # ^ |   +2 I mean, for example: JKeeJ1e30 reads like "Zhelezo" which mean "Iron" in russian. JK is like russian letter "Ж". Another letters in this logic.
•  » » » 7 years ago, # ^ |   +19 "llninethreeoneoneonezero"?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 7 years ago, # ^ |   0 He's vietnamese and his name is Linh, starting with a "L", that's why "ll"
•  » » 7 years ago, # ^ |   +17 ll is his name. and 931110 is his birthday. you can read what ever you want :)
 » 7 years ago, # |   +10 Our flight to Australia should depart 20 minutes after the start of this contest, but we'll participate if the flight is delayed. :)
 » 7 years ago, # |   +3 nice, hope there is always 1 contest per week at least :D
 » 7 years ago, # |   0 Oh the first CF round made by Vietnamese. As a Vietnamese, I'm really excited !
•  » » 7 years ago, # ^ |   0 care?
 » 7 years ago, # |   +11 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)
•  » » 7 years ago, # ^ |   +1 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.
•  » » » 7 years ago, # ^ |   +2 My mobile phone operators is CMCC, as a result I can't create a hot spot.T^T
 » 7 years ago, # |   0 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.
 » 7 years ago, # |   +5 almost missed it. why time changed? :/
•  » » 7 years ago, # ^ |   0 admins will be on train at default time
 » 7 years ago, # |   0 Missed it, didn't notice the time change :( please try and avoid this in future, not many of us keep checking the time..
 » 7 years ago, # |   -29
•  » » 7 years ago, # ^ |   -8 Что неправильно в этом решении? http://codeforces.ru/contest/327/submission/4020058) (точнее, что надо сделать, чтобы оно зашло)?
•  » » » 7 years ago, # ^ |   -7 Во-первых, возводить надо по модулю. Питон не потянет 2^100000 за 1 сек. Во-вторых, зачем делать это вручную если в питоне есть встроенная функция pow(x,y,z), которая возвращает x^y по модулю z, причем работает за O(log(z)) и в данном случае не будет использовать длинку.
•  » » » » 7 years ago, # ^ |   -14 спасибо, понял, как надо было
•  » » » » 7 years ago, # ^ |   +4 Скорее за O(log(y))
 » 7 years ago, # |   0 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 ?
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 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
•  » » » 7 years ago, # ^ |   +1 Thank you very much
•  » » 7 years ago, # ^ |   0 "When I run this code(I type it by my own on contest) on my PC , I use 10+ s" run it in "Custom test" on Codeforces
•  » » » 7 years ago, # ^ |   0 see this----On the custom test , it speads 3s+.
•  » » » » 7 years ago, # ^ |   0 sorry, but now it use only 216 msec. mb it was a bug
 » 7 years ago, # |   +1 how did the system testing complete so early this time??within 5 minutes
 » 7 years ago, # |   0 Wow amazingly fast system testing!
 » 7 years ago, # |   0 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?
 » 7 years ago, # |   +15 This has got to be the fastest system testing and rating change in the history of codeforces!! :O
 » 7 years ago, # | ← Rev. 2 →   +4 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!
 » 7 years ago, # |   0 thank you for the interesting contest!
 » 7 years ago, # | ← Rev. 2 →   0 Nice problem E indeed I love it :)when k<2 the problem is easywhen 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 setto 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 dofor j=1 to N dolet 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 integersadd to answer i! * j! * (n-i-j)! * Pend forend forthis is my guess to problem E , I didn't code it so I'm not quite sure that my idea is ok
•  » » 7 years ago, # ^ |   +8 How to compute P?
•  » » » 7 years ago, # ^ |   0 use meet in the middle attack to compute every P in O(3^(N/2))
 » 7 years ago, # |   +3 very nice problemset&tests congratz authors:D
 » 7 years ago, # |   0 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.
 » 7 years ago, # |   0 How to solve C?
•  » » 7 years ago, # ^ |   0
 » 7 years ago, # | ← Rev. 2 →   0 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
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 7 years ago, # ^ |   0 So strange！cout is more slow in theory, isn't it?
•  » » » » 7 years ago, # ^ |   0 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 :-)
•  » » » » » 7 years ago, # ^ |   0 Can print the big number and every pair of number's divisor is less than 2,because 2 is the smallest factor.
•  » » » » » » 7 years ago, # ^ |   +1 What about print i, from 10^6 to 10^6 + n ? :D
•  » » » 7 years ago, # ^ |   0 It is rather easy to calculate all primes between 2 and 10000000 in < 300ms. 4022940
 » 7 years ago, # |   +3 The problems are pretty straight forward...
 » 7 years ago, # | ← Rev. 2 →   0 Fantastic problem set for your first Codeforces round. Congratulations! Keep on programming :)
 » 7 years ago, # |   +9 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.
 » 7 years ago, # |   0 pretty fast system testing and rating updates, i am impressed :)
•  » » 7 years ago, # ^ |   +5 and editorial :)
 » 7 years ago, # |   +3 4019604 4017612 4017184These solutions in fpc appear to be the same. Please check.
 » 7 years ago, # |   0 How to solve E with DP?
 » 7 years ago, # | ← Rev. 2 →   +5 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/4023027In 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.
•  » » 7 years ago, # ^ |   +7 In the first line you should output 8 .
•  » » » 7 years ago, # ^ |   0 Oh oops... silly haha. Thanks!
 » 7 years ago, # |   +3 Wow, there were only two successfull hacking attempts during the whole round!
•  » » 7 years ago, # ^ | ← Rev. 3 →   +1 what's even more strange, is that both were made by coders from the same room!! :Dhttp://codeforces.com/contest/327/room/25
•  » » » 7 years ago, # ^ |   +3 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.
 » 7 years ago, # |   +7 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 ?
 » 7 years ago, # |   +1 When is the next contest scheduled?
 » 7 years ago, # |   0 [user: RR, 2013-07-04] what is this ? :D
 » 23 months ago, # |   0 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 :)