### HolkinPV's blog

By HolkinPV, 6 years ago, translation, ,

Good day, codeforces)

Welcome to regular Codeforces round #246 for Div.2 participants. As always Div.1 participants can take part out of the competition.

The problems were prepared by authors Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Is not the first and definitely not the last time when we tried our best for you. Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

UPD: Score distribution will be standard500-1000-1500-2000-2500.

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

UPD3: the editorial is here

Congratulations to winners!:

We wish all participants good luck and enjoyment of solving problems)

• +163

 » 6 years ago, # |   0 Have a good match again today. Applause.
 » 6 years ago, # |   +10 I will be in for my first match!
•  » » 5 years ago, # ^ |   0 hah, good luck and have fun!
•  » » 5 years ago, # ^ |   0 Too bad you did not show up :D
•  » » » 5 years ago, # ^ |   0 I just have a try to see the rules, next match I will play in it.
 » 6 years ago, # |   +8 nice picture!
 » 6 years ago, # |   0 Could you change the match time?In China ,the match time is not suitable for all china players.
•  » » 6 years ago, # ^ |   0 I'd also like to raise similar question. This is third CodeForces round for me. Each time it was 19:30 Moscow time. Apparently when people from all around the world participate it is impossible to always choose time which is convenient for everybody. Some other platforms try to rotate timings so that different rounds are more or less convenient in different time zones.So the question is — Does Codeforces always conduct rounds at 19:30 Moscow time? If so — will it change at some point in the future? or is it conscious decision because the platform is Russia-based? Still, even for Russian cities — like Vladivostok — 19:30 is hardly convenient.
•  » » » 5 years ago, # ^ |   +2 i'm not very sure, but i think some rounds are also held at 12:00 or 13:00 MSK.
 » 6 years ago, # | ← Rev. 9 →   +5 Waiting for score distribution
 » 6 years ago, # |   0 The contest should be presumed to take place at 7:40pm?And ohh please, you guys can inform the informers for your dinner schedule? Sorry but constructuve criticism.We see everytime the contests are post-poned by several minutes.:) We request you to look into the matter.Good luck and have fun all.
•  » » 6 years ago, # ^ |   0 Agree!I eat banana 3 minutes before the contest. So have to eat two bananas if it is postponed by 10 minutes :) If they ever do postpone it several times, I might not be able to participate.
 » 6 years ago, # |   +3 is it just me, or was there a countdown for CF Round #246 (Div. 1) as well about 2 days ago (a few hours after Round #245 ended)?
•  » » 6 years ago, # ^ |   +2 yes. there was one, but later removed. :(
•  » » » 6 years ago, # ^ |   +39 Please, do not get upset, it will be scheduled very soon =)
•  » » » » 5 years ago, # ^ |   0 when is the next contest? the contest menu is weird isn't it? :S
 » 6 years ago, # | ← Rev. 2 →   -15 puts("Good luck to everybody here that's gonna enter the cf contest."); puts("I hope you'll all upgrade to International. Grandmaster."); 
•  » » 6 years ago, # ^ |   +70 kursatba324.c:2:55 Error: expected ";"
 » 6 years ago, # |   -8 GOOD LUCK
•  » » 6 years ago, # ^ |   -21 TO everyone
 » 5 years ago, # |   0 i'll just be there being pupil :'(
•  » » 5 years ago, # ^ | ← Rev. 2 →   +7 No Problem, ratings are not important What you will achieve is important ;)
•  » » » 5 years ago, # ^ |   +1 like what ? :D
•  » » » » 5 years ago, # ^ |   0 contest experience ans skill ;)
 » 5 years ago, # |   -28 this contest have to be good one !HAVE TOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO !(give me some dis plz <3 )
 » 5 years ago, # |   +22 I love problem E and especially pretest 6 of it!
 » 5 years ago, # |   -8 IMO TL For D was too strict. O(n log^2n) Suffix array solution was getting TLEd :(
•  » » 5 years ago, # ^ |   +8 Problem D is about suffix structure? I never code a suffix structure before. I just know KMP:(
•  » » » 5 years ago, # ^ |   0 Yes, I got the idea of solution after you told that it can be done by KMP. But still I was expecting that authors will keep in mind that somebody might try more complicated suffix array solutions.
•  » » » » 5 years ago, # ^ |   0 But how can KMP solve this? How to get the substring which is both a prefix and a suffix?
•  » » » » 5 years ago, # ^ |   +1 suffix array is OK.I use it and it's just 77ms.6632223
•  » » 5 years ago, # ^ |   0 I think it was simple dp. But maybe i am mistaken an nlogn one.
•  » » 5 years ago, # ^ |   0 Suffix machine gives O(n) solution.
•  » » » 5 years ago, # ^ |   0 Is this the same as suffix automaton?
•  » » 5 years ago, # ^ |   +2 My O(n log^2n) Suffix array solution got AC 6626473
 » 5 years ago, # |   0 What does "submit already challenged" mean when I am trying to hack somebody? I am only one in room to lock problem C, so nobody else could have challenged it, but it rejected my hack attempt 5 times with this message...
 » 5 years ago, # |   0 What was wrong with the E problem. Isn't it just greedy. Try to put every letter (A,B,C,D,...X,Y,Z) until you can. I don't know what else could be. I have wrong answer on 7th test.
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 The answer should only consist of A,B and C. If your anwser has letter D or others your solution is 100% wrong.Oops I found my presumption was wrongThe main idea of the problem is greedy, while you have to check for three sides(up,left,right) when enlarging the square
•  » » » 5 years ago, # ^ |   0 The problem was one if. Just one if more and the program is running perfectly. :(
•  » » 5 years ago, # ^ |   0 Hi, Could you please explain your solution of E?Thanks in advance. :)
•  » » » 5 years ago, # ^ |   +3 This is what I did:1) Start on position (0,0) of the table. (You will move in this order: (0,0),(0,1),...,(0,m-1),(1,0),(1,2), ...,(n-1,m-1) ).2) Check for neighbors and put the minimum possible letter.3) -If this letter is "greater" than the last one, go back and make the biggest square possible with the previous letter. Then move to the next empty position, put the minimum letter and go to the next position.-Otherwise, just move to the next position.4) Go to step 2)My solution 6634518.
 » 5 years ago, # |   +1 Aww.. Really hate it when someone hacks my code with the time is almost at the end.. No more time to think the code again!!! T.T
•  » » 5 years ago, # ^ |   +6 Philosophically thinking this is almost exactly the same situation as if you just left your solution to be crashed by pretest. So take it easy.
 » 5 years ago, # | ← Rev. 2 →   0 Why this solution is Accepted for problem C ? link
 » 5 years ago, # |   +1 Problem C is Goldbach Theory? I got WA on test 10:(
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 Not really Goldbach conjecture i think. It's just construct minimum prime partition of a swap-range
•  » » 5 years ago, # ^ |   +11 Yes, with this theory we can achieve at most 3n operations.
•  » » » 5 years ago, # ^ |   +1 I think constraint of 3n operations is better version of this problem.
•  » » » » 5 years ago, # ^ | ← Rev. 4 →   -8 Why not 2n operations?If you go from beginning to end, every item can be moved just once. So you need to do n operations to sort array (because this is not "real" n*log(n) sorting — this is ideal sorting, when you know all your elements beforehand).Each move can be achieved at most in 2 operations, if difference is not prime.Which should give 2nEDIT: Ah, see problem when you need to move by just 1 items, you have to do two operations 3 forward and 2 backward. And you can do it only if you are not at the end of array. So there might be problem in the end.
 » 5 years ago, # |   +4 My rating updated so fast! Thank you!
•  » » 5 years ago, # ^ |   0 It always took more than an hour!
 » 5 years ago, # |   0 All Submission for Problem A fail in Final test who use sort and check 3 element in a row ,where there occurs a overflow of given data !! :P Really shocked about my bad Code :(
 » 5 years ago, # |   +1 http://codeforces.com/contest/432/submission/6630167 What does skipped mean? I want my point... It must be accepted
•  » » 5 years ago, # ^ |   0 Most likely this submission was not your final solution. Meaning later into the round you resent submission for this problem. When you resend submission for you problem, all previous submissions are "skipped". Seems that your new solution was wrong, while previous one was correct. Bad luck.If this is not the case, then you probably should contact admins.
 » 5 years ago, # |   0 please explain how to solve problem D.
•  » » 5 years ago, # ^ |   +9 I calculated Z-function for the string s (but z[0] = n). Then I found all the prefixes coinciding with suffixes ("necessary" prefixes), i.e. stored all their lengths in set V (I mean all values of z[i] which were equal to n-i). Besides, I stored the number of occurences of each value of z[i] in a map C. Then I calculated the number of occurences for each prefix. Here is an example: let C['ab'] = x1, C['abc'] = x2, C['abcd'] = x3 ... => # of occurences of 'ab' is equal to the sum of occurences of bigger prefixes (x2 + x3 + ...) + C['ab']. We can calculate this with O(n) complexity. I also created a map M, where I stored the number of occurences of "necessary" prefixes, and outputted all its contents.
 » 5 years ago, # |   0 In Problem C will shell-sort with prime shuffling work? I tried but it was giving tle
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 problem c was simple , for each number i= 1 to n , swap the number to greatest left position such that length of swap is prime , start from (pos-i+1) search nearest prime , repeat down till its sorted position is obtained
 » 5 years ago, # |   0 Too strong pretests that a few people hacked:(
 » 5 years ago, # | ← Rev. 2 →   0 Please someone explain idea of problem C ?? Not getting it through codes and if possible proof of complexity :( :( Please
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 Simply, you can follow an optimal strategy which is :for every i from 1 to n swap the element which has the value i with index j;index j is the closest element to i whose distance to the element with value i is a prime numberin other words you have to find the maximum prime number which is not larger than distance between the index of the element which has a value of i and index ibinary search is the best way in my point of viewaccording to Goldbach's_conjecture complexity will be at most O(5 n log(n))here is my AC code 6629271
•  » » » 5 years ago, # ^ |   0 i didn't get a word from your comment :D +1 for caring :3
•  » » » 5 years ago, # ^ |   0 So basically, we're moving i to a prime distance from it's intended position, index i, so that we can swap it in the next move. Then we do this for each i in n?Did I get you right AmrMahmoud?
•  » » » » 5 years ago, # ^ |   0 yes, you keep moving i until it reaches index iand then do the same for every inote that you have to choose maximum prime distance possible in order to minimize number of movements
•  » » » » » 5 years ago, # ^ |   0 ok .. ! #osama's
»
5 years ago, # |
+7

# OFFTOP

Three contests number 247 are coming?! :)

 » 5 years ago, # |   +1 someone explain the idea behind solving problem D...
•  » » 5 years ago, # ^ | ← Rev. 2 →   +2 I know two solutions for problem D. The first one is based on Z-Algorithm. If you compute Z[i] — largest substring starting at the i-th position, which matches with the prefix of the same length, when you have a prefix which matches with the associated suffix, you have to count how many values of Z[] are >= the length of the current prefix.The second one, a bit harder than the first one, is based on KMP (Prefix function) and hashing. First of all, you have to compute for each prefix and each suffix their hashcodes. If you compute Prefix[i] (from KMP) and consider a tree where edges are from Prefix[i] to i (nodes are labeled from 1 to N), you can find Nr[i] — how many times does the prefix [1..i] match with the entire string by counting how many nodes are in the subtree rooted at node i. Here is the code which computes this: for(int i = N; i; -- i) { Nr[i] ++; Nr[Prefix[i]] += Nr[i]; } Now, if you find a prefix which matches with the associated suffix (by comparing their hashcodes), you know the answer for that prefix :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 I used KMP. We can easily calculate, for each prefix of length i, the second longest prefix which matches it (is its suffix); its length is prev[i]. Then, we can calculate the number of times P[i] the prefix of length i appears in the string: a bruteforce would iterate j=prev[j] starting from each and increment each P[i] encountered, but it can be simplified by iterating i from N to 1 and adding P[i] to P[prev[i]] (it basically processes all iterations j=prev[j] at once). Counting prefixes which match a suffix is even easier: these are the ones which are iterated by j=prev[j] starting from j = N.
•  » » » 5 years ago, # ^ |   0 Can you elaborate these two lines a little more? I have seen these in almost every code but cant get it how it gives me the required result. - vector P(N+1,1); - for(int i =N; i > 0; i--) P[prev[i]] +=P[i];
•  » » » » 5 years ago, # ^ |   +2 We know that if a prefix i ended somewhere, then so did prefix prev[i]. Mathematical induction: suppose P[j] (j > i) have been fully calculated and tell the number of times prefix j appeared in the string. Then anytime prefix i occurs as a substring string (except as that prefix itself), it'll be a suffix of some other prefix. We could iterate over all prefixes that can contain it (and no larger prefix, so that we wouldn't count occurences multiple times) as a suffix — each time such prefix occurs in the string as a substring, prefix i must also occur in it, so it's the sum of P[j]-s for which prev[j] = i. We're just calculating that in the opposite direction (imagine it as counting subtree sizes of a tree, we're not doing a DFS but cutting off leaves).
 » 5 years ago, # | ← Rev. 2 →   0 I got timeLimit in pretest9, i don't understand why, my solution is a simple Z algorithm For every string's position accumulate the largest valid prefix who is a suffix in a frecuency array then you easily know how to get all valid prefix's frecuencies, accumulate from the largest to the smallest for get all answers. If someone don't understand I can explain it better.http://codeforces.com/contest/432/submission/6632244
•  » » 5 years ago, # ^ |   +3 Because of trivial approach in Z-function. It goes in O(n^2). Here is AC verdict for your solution with modified Z-function.
•  » » » 5 years ago, # ^ |   0 Can you please explain your algorithm.
•  » » 5 years ago, # ^ |   +1 Your simple Z algorithm really runs in O (N^2), which is not fast enough to pass the time limit under the given problem constraints.
•  » » » 5 years ago, # ^ |   0 Thanks, I saw that minutes after I published this xD, Is really bad copy and paste an algorithm whenever you don't remember well it and you are in a hurry.So, today's lesson is to review well or have your own prewritten code. Thanks!!
•  » » » » 5 years ago, # ^ |   0 Or read carefully "z_function_trivial" !! xD
 » 5 years ago, # |   +1 Please give editorial!
 » 5 years ago, # |   +1 Very good problems, but unfortunately i fell down :(
 » 5 years ago, # |   0
 » 5 years ago, # |   0 What i want to Say is it's too unbelievable to find the System test#29 of Problem D it make the Hash which Mod 2^64(using unsigned long long) wrong..... so, my D's solution which use SuffixArray failed the system tests...:(
 » 5 years ago, # |   0 Here is a simple editorial for problem D. Run The Z algorithm ( google is your friend is you don't know it ) Copy the Z array into another one && sort it in increasing order ( I will explain why ) Now we need to compute the frequency of each substring of length 'l' in the original string. Of course it needs to be both a suffix and a prefix. PS: Given The Z array it is easy to know if a substring of length 'l' is also a suffix. You need just to check is Z[N-l] >= l, with N the length of the original string.The problem now, is how to efficiently count these frequencies. The trivial way, is to iterate over the Z array and is Z[i] >= l then we increment. Unfortunately, it is too slow.A better way, is to sort the Z array and perform a modified binary search ( one that gives the most left occurrence of the target key ). Now some little arithmetic will give us the number Zs greater than or equal than length 'l'.Complexity of the algorithm is O(n*logn). Since we can construct the Z array in O(n) time, and for each length 'l' we run a binary search O(logn), and finally compute the frequency in O(1) time.Let's take the string: ABACABA. Z algorithm will give us: 7 0 1 0 3 0 1 After copying and sorting: 0 0 0 1 1 3 7 Now for length l = 1, we first check if Z[N-1] >= 1 ( which is true ), then we perform the binary search which will return index = 3 ( 0 based ). Now the magic comes, freq[1] = N-3 = 7-3 = 4. Which is the correct number.Here's my code: 6636526I'll be glad to explain more and sorry for any mistake.Special thanks to Totktonada for his Z algorithm function.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 We don't need binsearch actually: 6637149 And no magic, small observation: if we have substring with L length X times, we also have additional X substrings with [1; L-1] len. Too bad that i didn't write solution correctly on contest.P.S. Sorry for my bad english.
•  » » 5 years ago, # ^ |   0 Nice explanation. You can consider the prefix sum instead of binsearch to make it O(N)6637312
•  » » » 5 years ago, # ^ |   0 Excellent idea. I appreciate.
•  » » » 5 years ago, # ^ |   0 It actually is a suffix sum. You don't need the pref array (if you want to optimize for space); use z[N - len] == len as a test for "suffix that is also prefix".