MikeMirzayanov's blog

Testing Round #9
By MikeMirzayanov, 11 years ago, translation, In English

The contest Testing Round 9 is a special contest to test recent Codeforces internal improvements. Please, take part in it to help us to be ready for Codeforces Round 224 (Div. 2).

The Testing Round 9 will be completely unofficial and unrated. We will use problems from some Saratov contests, they will be new for many of you.

If you see any issues in Codeforces behaviour, write a comment here.

Thank you!

UPD. The contest completed. Thanks to all the participants.

Announcement of Testing Round 9
  • Vote: I like it
  • +105
  • Vote: I do not like it

Comments Comments (17)
| Write comment?
»
11 years ago, # |
  Vote: I like it -6 Vote: I do not like it

it's allowed to know the type of these improvements ? :D

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

    All improvements are relatively deep inside Codeforces system and are mainly made to improve performance. So you won't see anything, except, maybe, faster page loading.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why always Testing rounds are at a very very unusual time?!

→ Reply
»
11 years ago, # |
  Vote: I like it -8 Vote: I do not like it

the duration changed?

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Will there be an editorial for this round ?

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

    I am not sure if editorials are written for testing rounds.

    A. 3 main approaches:

    1) Select two indexes of the two biggest values with one loop.

    2) Sort numbers in pairs with their indexes.

    3) Select max index. Then find max value which is different from the previous found.

    B. Sort all numbers and use one loop for l, other for r, then select max(r — l + 1), where a[r] — a[l] <= t. You can use "two pointers" too.

    C. Find the number of substrings which have d <= i (not exactly i), for each i from 0 to 26. Then the exact answer for each i ([1; 26]) is res[i] — res[i — 1]. How to do that? Well, here you could use "two pointers". Keep the number of distinct letters (there are 26 of them, make a small array to keep their counters). Go through all l, then keep extending r if the number of distinct letters is not more than i.

    Adding r: increases the number of distinct letters if the counter of this letter was 0.

    Leaving l: decreases the number of distinct letters if the counter of this letter becomes 0.

    D. Use BFS where the positions are defined as the indexes of taken vertices. For each member in the triple try to change its location (if the colors are the same as it is said in the statement). Let's remember which member we have changed as well as its old value. We break from BFS if we dequeue a triple which when it is sorted gives (1, 2, 3). We can restore the path from the end to the beginning recursively.

    For details look into my solutions.

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

      do you know any tutorials or examples for "two pointers" ? i heard about "two pointers" but don't know exactly what it is .

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one explain how to solve problem C ? i don't think there will be tutorial for this 'Testing' round .

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    I have 26 counters (one for each possible k) and a vector with the last position for each c, updating this vector for each char of the string.

    Example: For "abacd" at char "d" the vector will be:

    (a, 3) (b, 1) (c, 2) (d, 4)

    If you sort by the second element in decreasing order

    (d, 4) (a, 3) (c, 2) (b, 1)

    You are at char 4 right now. From the vector you know that the range from 4 to 3+1 belongs to k=1, from 3 to 2+1 to k=2, from 2 to 1+1 to k=3 and the rest to k=4.

    The cost is O(26*size of the string)

    My solution failed during the final tests because I was printing at the only up to K=25 :(

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

      i read your solution ant got it :) thanks !

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

      Wow, very nice, I unnecessarily complicated it.

      When processing the ith character, I found the last occurence of that character(like you did) and had a list of prefix sums as to the number of occurences of each character upto that special character(these diversities do not change). And then, I modified the new diversities like you did. And to top it all, I had the long long bug. :D

      → Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

If I'm not mistaken there was no typical window with text "Contest has started. Would you like to enter the contest area?".

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

    I saw it. And used.

    Like this round. It was sudden and pleasant. Unfortunately, my crooked hands didn't let me make workable my two-pointers-O(n) and really unsophisticated solution in C =__=

    → Reply