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.
it's allowed to know the type of these improvements ? :D
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.
Why always Testing rounds are at a very very unusual time?!
the duration changed?
No, but the starting time yes.
Originally durations was 1 hour.
Yes sorry, didn't saw time when the comment was written :/
Will there be an editorial for this round ?
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.
do you know any tutorials or examples for "two pointers" ? i heard about "two pointers" but don't know exactly what it is .
You can see this post for example
http://codeforces.net/blog/entry/4586
The are a lot of problems tagged as "two pointers" here in Codeforces for practice.
can any one explain how to solve problem C ? i don't think there will be tutorial for this 'Testing' round .
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 :(
i read your solution ant got it :) thanks !
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
If I'm not mistaken there was no typical window with text "Contest has started. Would you like to enter the contest area?".
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 =__=