### HolkinPV's blog

By HolkinPV, 7 years ago, translation, ,

Good day, friends)

Soon is coming regular Codeforces round #166 for Div.2 participants. Traditionally the others can take part out of the competition.

And again the problems were prepared by the group of authors: Pavel Kholkin (HolkinPV), Nikolay Kuznetsov (NALP), Rakhov Artem (RAD) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

UPD: Score distribution will be not standard a little bit — 500, 1000, 1500, 2000, 3000.

We wish everyone good luck, successful hacks and high rating)

UPD2: the contest is over, we hope you enjoy it)

Congratulations to winners:

1) sunzhouyi
2) xyz111
3) nanoha
4) wyx528
5) GuyUpLion

UPD3: the editorial is published, you can find it here

• +74

 » 7 years ago, # |   0 This group always offers good problems...!!!
 » 7 years ago, # | ← Rev. 2 →   -10 MikeMirzayanov's contribution is +210 O_O
•  » » 7 years ago, # ^ | ← Rev. 3 →   +4 Keep getting negative votes and your contribution will reach his (by absolute value) sooner than you can possibly imagine.
•  » » » 7 years ago, # ^ |   +3 No one will win JKeeJ1e30
 » 7 years ago, # |   +82
•  » » 7 years ago, # ^ |   +45 Такие все шутники) но иногда приятно) ставлю плюс)
 » 7 years ago, # |   0 its time
 » 7 years ago, # |   -7 Hi authors, Problem C div2 says that any alternative solution is accepted. So this answer for test: 11 3 11122233123 shouldn't be accepted?
•  » » 7 years ago, # ^ |   +3 It should, but you should have printed the blank spaces between each number...
•  » » 7 years ago, # ^ | ← Rev. 2 →   +3 if we divided in three group it will be: 1 2 3 9 4 5 6 10 7 8 11 all 3 of the sequence is not an arithmetic progression
 » 7 years ago, # | ← Rev. 2 →   +1 for all who had WA #8 in problem D,I think the test case isabaab 01 2
•  » » 7 years ago, # ^ |   +3 and what do you say abt TLE + memory limit exceeded for D.
 » 7 years ago, # |   +7 The problems were excellent! The problem-setters deserve a round of applause.
 » 7 years ago, # |   0 Nice problem set, the writers managed to come up with balanced problems, got 4 out 5.
 » 7 years ago, # |   0 waiting for rating update .....
 » 7 years ago, # |   +8 In problem D, I use 2 hash value with int always get wrong answer on test 41, and my answer always is 241238 (the right is 398680), and I use long long with same hash numbers get accepted. Why there is so big difference between them ? Many helps !
•  » » 7 years ago, # ^ |   0 I just exchanjed power of prime number from 31 to 29 and 37, then got accept.
•  » » » 7 years ago, # ^ |   0 You guys use hash without handling conflict, and still got ACCEPTED! How unfair... I found a nice c++ solution(3100030) in my room that use set, and the worst time complexity is O(n^3 log(n)), still very nice, though. My first attempt was a Python solution using a Trie, which is O(n^2). It got TLE, saddly. Then I was forced to translate the Python script into C++.
•  » » » » 7 years ago, # ^ |   0 I used suffix array with time complexity O(nlog^2n) in building the array and O(nlogn) for the rest.3108063 This is totally unfair that even solution with time complexity O(n^3logn) can be accepted. The test case should be bigger, say string of length 1000,000.
•  » » » » » 7 years ago, # ^ |   0 When the data scale is too large, we will lost some interesting solutions. It's also unfair for some dynamic languages since a loop with 1000000 times may cost about 1 sec. So I think 10^3 or 10^5 is fine.
 » 7 years ago, # |   +3 After participating in some contests here, now, I confess that I'm not clever enough as I thought I am :( I'm not sure if continue to participate will make it better; I even can not get to 1700 :(Any friend has an idea about why I'm not successful here as much as my successful in business software development (I am Microsoft Visual C# MVP 2011)?!I just like to know if I should continue or break to study more and then come back.Thanks in advance!
•  » » 7 years ago, # ^ |   0 You can come back any time. But we are sad to see you gone...
•  » » 7 years ago, # ^ |   +5 Being successful in X does not automatically mean being successful in Y. Why take a break? Theory is nothing without practice. Study more and compete in contests. Remember… practice makes perfect.
•  » » » 7 years ago, # ^ |   0 +1.thanks expert!In your opinion, how much IQ has effect in results in percent?
•  » » 7 years ago, # ^ |   0 It is a wonderful place to get knowledge and I don't have a great result but I am trying to be better day by day here.
 » 7 years ago, # |   +3 Anyone willing to share an idea for problem E?
•  » » 7 years ago, # ^ | ← Rev. 5 →   +6 My idea was based on this observation:Suppose that y=x+kWhat we really care for is the difference between a pair of numbers (the k).(because we can get (a+1,b+1) and (a-1,b-1) from (a,b) )The first horse does not change the differenceThe second horse divides the difference (k) by twoThe third horse gets two pairs with differences = k1,k2 and gives a pair with difference=k1+k2(The rest is simple NT -divisibility, gcd,etc.- )
•  » » » 7 years ago, # ^ |   0 I thought with the same idea in the contest but actually first horse give (a+1,b+1) form (a,b) but don't give (a-1,b-1)
•  » » » » 7 years ago, # ^ |   +5 (a, b) -> (b, 2 * b — a) -> (a, 2 * b — a) -> (2 * a — 2, 2 * b — 2) -> (a — 1, b — 1)
 » 7 years ago, # |   +1 Thanks to the creators , for making the catching stuff in the questions BOLD, it really helped!!
 » 7 years ago, # |   0 Unfortunately I missed the contest.. Was celebrating my birthday
•  » » 7 years ago, # ^ |   0 yaar aaj tu Div 1 me pahuch jata :( btw hbd :)
•  » » 7 years ago, # ^ |   +1 HBD :)
 » 7 years ago, # |   0 its showing me blue color but with old rating :( :( yyyyyyyyyy so ?
 » 7 years ago, # |   +3 It's showing me blue but with older rating 1448 :( why ???
 » 7 years ago, # |   0 Could someone explain Div2.E problem body? As I understand: We start with singleton, S = {(x,y)}. Given some set S of cards, we pick one card (x,y) from S, perform 1 of 3 operations(in third operation we would take two cards), and get new card (x', y') S now contains both (x,y) and (x',y') We want S to include some subset P. But it surely isn't correct understanding.
•  » » 7 years ago, # ^ |   0 Actually, it is the correct understanding.
 » 7 years ago, # |   0 Anyone willing to share an idea for problem D without hash? Thanks a lot.
•  » » 7 years ago, # ^ |   0 prefixs + substrings + set = 3103424
•  » » » 7 years ago, # ^ |   0 thankyou
•  » » » 7 years ago, # ^ |   +3 please explain how could this pass?you have 2 "for" and inside them you have "substr" which has complexity O(j-i) so your total complexity is O(N^3)
•  » » » » 7 years ago, # ^ |   0 You are right, but it has a low constant, so 2 "for" and "substr" inside them take only 350 ms on a string with length=1500.Also working with set we have total complexity O(N^3*ln(n)), because comparing the string takes O(N). But it is also with low constant and is unattainable, because not all substrings are comparable in full length.
 » 7 years ago, # |   0 Four of the winners took part in Codeforces contest for the first time,the rest one only took part twice....
•  » » 7 years ago, # ^ |   +2 I'm sure they are multiple accounts
•  » » » 7 years ago, # ^ |   +5 I'm sure they aren't muliple accounts
•  » » 7 years ago, # ^ |   0 Absolutely agree,in most contests there are about 2-3 unrated winners,maybe I'm mistaken but I think they are multiple accounts
 » 7 years ago, # |   -9 One question: the limit for the Div2 B were n,m <= 500, but what is the point to have such limits, when the max size of test file for hacking is just 256 KB? I mean there were a lot of solutions that could be hacked using a matrix of size 500 x 500, but it wasn't possible because the system won't accept files that big. Many solutions were done in O(n*m*nextPrime(x)) and I think this wasn't the complexity intended to solve this problem. An acceptable one would be done in O(n*m*log(closestprime(x)).
•  » » 7 years ago, # ^ |   +4 you have to write code to generate test-cases you want ,not the test-case itself
•  » » 7 years ago, # ^ |   0 nextPrime(x) factor is extremely small ~ O(log x), so it's just looking for 20 consecutive bytes of memory. Bad binary search could be slower.
 » 4 weeks ago, # |   0