When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

HolkinPV's blog

By HolkinPV, 10 years ago, translation, In English

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!:

1) PopovkinAndrey
2) FTD2009
3) Gulan14no
4) Kozakai_Aya
5) Mikael

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

  • Vote: I like it
  • +163
  • Vote: I do not like it

| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Have a good match again today. Applause.

»
10 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I will be in for my first match!

»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

nice picture!

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you change the match time?In China ,the match time is not suitable for all china players.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      i'm not very sure, but i think some rounds are also held at 12:00 or 13:00 MSK.

»
10 years ago, # |
Rev. 9   Vote: I like it +5 Vote: I do not like it

Waiting for score distribution

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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)?

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    yes. there was one, but later removed. :(

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +39 Vote: I do not like it

      Please, do not get upset, it will be scheduled very soon =)

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        when is the next contest? the contest menu is weird isn't it? :S

»
10 years ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it
puts("Good luck to everybody here that's gonna enter the cf contest.");
puts("I hope you'll all upgrade to International. Grandmaster.");
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +70 Vote: I do not like it

    kursatba324.c:2:55 Error: expected ";"

»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

GOOD LUCK

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i'll just be there being pupil :'(

»
10 years ago, # |
  Vote: I like it +22 Vote: I do not like it

I love problem E and especially pretest 6 of it!

»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

IMO TL For D was too strict. O(n log^2n) Suffix array solution was getting TLEd :(

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Problem D is about suffix structure? I never code a suffix structure before. I just know KMP:(

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But how can KMP solve this? How to get the substring which is both a prefix and a suffix?

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        suffix array is OK.I use it and it's just 77ms.6632223

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it was simple dp. But maybe i am mistaken an nlogn one.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Suffix machine gives O(n) solution.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    My O(n log^2n) Suffix array solution got AC 6626473

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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...

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    10 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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 wrong

    The main idea of the problem is greedy, while you have to check for three sides(up,left,right) when enlarging the square

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The problem was one if. Just one if more and the program is running perfectly. :(

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, Could you please explain your solution of E?

    Thanks in advance. :)

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why this solution is Accepted for problem C ? link

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem C is Goldbach Theory? I got WA on test 10:(

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Not really Goldbach conjecture i think. It's just construct minimum prime partition of a swap-range

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Yes, with this theory we can achieve at most 3n operations.

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I think constraint of 3n operations is better version of this problem.

      • »
        »
        »
        »
        10 years ago, # ^ |
        Rev. 4   Vote: I like it -8 Vote: I do not like it

        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 2n

        EDIT: 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.

»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

My rating updated so fast! Thank you!

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :(

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

http://codeforces.com/contest/432/submission/6630167 What does skipped mean? I want my point... It must be accepted

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

please explain how to solve problem D.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem C will shell-sort with prime shuffling work? I tried but it was giving tle

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Please someone explain idea of problem C ?? Not getting it through codes and if possible proof of complexity :( :( Please

  • »
    »
    10 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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 number

    in 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 i

    binary search is the best way in my point of view

    according to Goldbach's_conjecture complexity will be at most O(5 n log(n))

    here is my AC code 6629271

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 RetiredAmrMahmoud?

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes, you keep moving i until it reaches index i

        and then do the same for every i

        note that you have to choose maximum prime distance possible in order to minimize number of movements

»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

OFFTOP

Three contests number 247 are coming?! :)

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

someone explain the idea behind solving problem D...

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    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 :)

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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];

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        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).

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Because of trivial approach in Z-function. It goes in O(n^2). Here is AC verdict for your solution with modified Z-function.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Please give editorial!

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Very good problems, but unfortunately i fell down :(

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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...:(

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is a simple editorial for problem D.

  1. Run The Z algorithm ( google is your friend is you don't know it )
  2. 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: 6636526

I'll be glad to explain more and sorry for any mistake.

Special thanks to Totktonada for his Z algorithm function.

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice explanation. You can consider the prefix sum instead of binsearch to make it O(N)

    6637312

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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".