Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

### Edvard's blog

By Edvard, 10 years ago, translation,

Hi everyone!!!

It remains less than 10 hours before Codeforces Beta Round #98 (Div. 2). This round was prepared for you by me, proposed the ideas of the problems. Traditionally, RAD made sure that there is no bugs and that the statements are normal, and Delinur translated the statements into English. Thanks to them!

If you decide to participate in the round you have to help the boy Polycarpus and his classmate Innocentius in all the difficulties they face. The more you help them, the higher you will be placed in the standing.

I hope the problems will be interesting not only for Div. 2 participants, but the participants rated higher than 1699.

I will continue the story about myself (beginning of story in the previous blog entry). Besides programming I love sports. Within a few years before I started writing code, I was seriously involved in rowing. And before that I was going in for almost all sports :-): karate, soccer, hockey and so much more interesting. Now I love (especially at the training camp) to play volleyball and table tennis. I decided to prepare this round despite the fact that during the past two weeks, much has changed inside Codeforces and I took part in this.

Following the fashion trends I have changed my avatar.

Good luck for all on the round!

UPD:

Contest is finished, results are final, ratings are updated.

Top 10 (Div. 2)

3. stx2

Congratulations to winners!!!

• +141

 » 10 years ago, # |   +2 Luckly,there will be not class for me in the afternoon,so I can take in the contest;thanks for your hard work!
 » 10 years ago, # |   +6 Thanks for your work! I think this round will be fun.
 » 10 years ago, # |   +4 I was going to watch Mission Impossible 4 !!! I had to change my plans because of the contest . :P
 » 10 years ago, # | ← Rev. 2 →   0  Contest already started, but I cannnot connect. I only see standings. And some people already solved some tasks, so I guess that this problem is not for everyone.EDIT: Seems like I am not registered to this contest, but I did register.
 » 10 years ago, # |   0 after contest finishes check out organofjohannbach's solution to problem C. This guy must be real pro
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 Liked the problem set, but I cant understand how to prove binsearch in E, can anyone help?Binary search is incorrect, can anyone explain right sol?
•  » » » 10 years ago, # ^ |   +1 It is not correct as function is not monotonic. baaab has good string of length 5, but not of length 4
•  » » » » 10 years ago, # ^ |   0 then my E failes, thanks
•  » » » 10 years ago, # ^ |   0 Binsearch is incorrect solution for E.
•  » » » » 10 years ago, # ^ | ← Rev. 2 →   0
•  » » » 10 years ago, # ^ |   +3 Well my solution for E works like this,1. Convert the string into an integer array A. convert a vowel to -1 and a consonant to +2.2. Calculate a sum array, where sum[i] is the summation of A[0] to A[i].3. Now for each i, we need to find the minimum index j<=i, such that sum[j]<=sum[i]. For this I used a binary indexed tree. So for i we found the longest good substring which starts at j.4. Thus longest good substring can be easily calculated in O(nlogn).5. The number of times can be easily calculated in O(n).
•  » » » » 10 years ago, # ^ |   0 Constant time lookup is also possible (instead of binary tree), for an O(n) algorithm.
•  » » » » 10 years ago, # ^ |   0 I don't understand how do you find the minimum index j
 » 10 years ago, # |   0 i also tried to use binary search but i found out mistake soon...
 » 10 years ago, # |   +3 Thanks to admins,codeforces was really fast today. I have participated in 36 contests but never seen cf working so fast,its great :).
 » 10 years ago, # | ← Rev. 2 →   +1 my C is Denial of judgementwtf?It's ok now, sorry
 » 10 years ago, # |   0 a lot of C recv " Denial of judgement"
 » 10 years ago, # |   0 Nice problem set!But I have a little question:In a char tab[100], is the '\0' counted on the 100 ?Because I have tried to hack a code who had a char tab[100] for the problem A, with a string "C....C" (containing 100 'C'), and it was unsuccessful...Thanks you in advance
•  » » 10 years ago, # ^ |   +12 It is, but in C++ there are no range check, so trying to hack for being out of bounds for array/vector are very risky (expecially with off be one errors)
•  » » » 10 years ago, # ^ |   0 Ok, I did think about this possibility, but I wasn't sure.
•  » » 10 years ago, # ^ |   +1 '\0' would never be counted in this 100 chars since it is just implementation detail of one of variants of holding string in one of programming languages.Anyway char tab[100] would not necessarily yield error with 100 Cs - it is possible that 101-th '\0' was placed in spare memory after the end of the array without error...
•  » » » 10 years ago, # ^ |   0 I also mis-hacked one solution, in which he tried to access indexes of a vector which did not exist.To make sure that my hack is correct , I tested it on my computer, and it caused Seg. Fault. And unluckily enough, got -50 During hack. :(
•  » » » » 10 years ago, # ^ |   0 It is very unstable thing. For examle suppose:char a[100];char b = 5;int func() {    return;}Suppose, user made writing into a[100] - what then?If code is not optimized and data are not aligned, he will write actually into b.If code is aligned at 4 bytes border, he will writing between end of a and beginning of b - no problem at all.If code is optimized, b may become register variable and disappear, if code is not aligned, he will erase beginning of "return" instruction (this may lead to funny bugs).However this depends on actual placement of data and code, architecture etc.
•  » » » » » 10 years ago, # ^ |   0 Okay, will keep that in mind.Thank You.
 » 10 years ago, # |   0 a lot of people had solution in o(n*n) but i couldn't hack because you cant send test with more than 20k memory ...
•  » » 10 years ago, # ^ |   +5 You can send a generator
•  » » » 10 years ago, # ^ |   0 When I try to upload the input, why did it not say: "Your Input is more than 20kb limit. " in RED BOLD FONT.When I click on Hack, it did not do anything .
•  » » » » 10 years ago, # ^ |   0 You should upload a generator, not an input
•  » » » » » 10 years ago, # ^ |   0 I know now. But I want to ask , why does the interface not show that "What you just uploaded is so much large in size that we cannot handle, plz use generators" in RED BIG FONT instead of just blinking once and keeping quite.
•  » » 10 years ago, # ^ |   0 Yes, I don't like this too... I have seen a code who use a int tab[10000] for the problem C, and I didn't can hack his problem because my input was too large....
•  » » » 10 years ago, # ^ |   0 You can't hack not because input was large, but because you never tried sending generators, though it was discussed a lot of times.
•  » » » » 10 years ago, # ^ |   0 What is a generator? A executable who send input on stdout?
•  » » » » » 10 years ago, # ^ |   0 Exactly... Read some comments above - here are examples
•  » » » 10 years ago, # ^ |   +3 The reason you need generator is for large inputs,input file becomes to large,may be some megabytes and uploading them will create severe pressure on server. If you want to know how to write generators,here is my generator in div2C:int x=1;    cout<<100000<1000000000) break;        printf("%d %d\n",x,x+1);        x+=2;    }I have hacked some n*n solutions with this today.
•  » » » » 10 years ago, # ^ |   0 if i knew that i would have more than 5 hacks :@:@:@
 » 10 years ago, # |   0 Hey guys. I competed in codeforces for the first time today. would anyone mind telling me why my submission for problem B gets a run time error? thanks!
•  » » 10 years ago, # ^ |   0 Look at the constraints.  You can get values bigger than N for t-1 in this lineV[t-1] = true;
•  » » 10 years ago, # ^ |   0 because t can be >= N if N<5000
 » 10 years ago, # |   0 Y the system test didnt accept my problem A submission?
 » 10 years ago, # |   +1 Very nice algorithmic problems! It gave me a lot of pleasure to solve them! Thanks!
 » 10 years ago, # |   +13 I like this contest.I'm happy and learn a lot after doing this contest.Thanks the author!
 » 10 years ago, # |   0 Could anyone please tell me why my solution got WRONG_ANSWER on this test?Test: #22, time: 90 ms., memory: 42128 KB, exit code: 0, checker exit code: 2, verdict: WRONG_ANSWERInputWdYlPYGSNSGYPlYdWpIyMrtjUleOWVihRoZkUyXWuKuWXyUkZoRhzVWOelUjtrMyIpZassaZBSohcqchoSBZKgKZlhMOXMoMXOMZGZvvRkqSOmHWZxSxZWHmOSrkRvvWPW 10 Output3 WdYlPYGSNSGYPlYdW+pIyMrtjUleOWVihRoZkUyXWuKuWXyUkZoRhiVWOelUjtrMyIp+ZassaZ+BSohcqchoSB+ZKgKZ+l+h+MOXMoMXOM+ZGZ+vvRkqSOmHWZxSxZWHmOSqkRvv+WPWAnswer3 WdYlPYGSNSGYPlYdW+pIyMrtjUleOWVihRoZkUyXWuKuWXyUkZoRhiVWOelUjtrMyIp+ZassaZ+BSohcqchoSB+ZKgKZ+ll+MOXMoMXOM+ZGZ+vvRkqSOmHWZxSxZWHmOSqkRvv+WPW Checker Logwrong output format Expected string with length not greater than 139, but string length is 140.
•  » » 10 years ago, # ^ |   0 Because you split the string into 11 palindroms, not 10.
•  » » » 10 years ago, # ^ |   0 Thank you!
•  » » 10 years ago, # ^ |   0 You have split string into 11 palindromes, while k = 10.
•  » » 10 years ago, # ^ |   0 А объясните плиз, почему у меня рейтинг понизился? хотя если на прошлом контесте я 1069\2031 место с 1 задачей , а на этом  650\1324 с 2мя. потому что участников меньше ?
•  » » » 10 years ago, # ^ |   0 Да, в процентном соотношении у вас примерно одинаковое место на обоих раундах.
•  » » » 10 years ago, # ^ |   +3 А ещё количество зарегистрировавшихся не есть количество участников.
 » 10 years ago, # |   0 I am new to code forces. can u tell me how to view others solution??
•  » » 10 years ago, # ^ |   0 lock your solution,then you can see others in your room.
•  » » » 10 years ago, # ^ |   0 how to lock the solution??
•  » » » » 10 years ago, # ^ |   0 At problems page a lock icon will appear if your code pass pretests,click that icon.
•  » » 10 years ago, # ^ |   0 If the round is already over, then just double-click on a result in the total results table.
 » 10 years ago, # |   0 My DP solution to problem E exceeds time limit, with O(n^2) complexity (n being length of the string). What is the correct solution supposed to look like?
•  » » 10 years ago, # ^ | ← Rev. 3 →   0 (c) EgorLet B[i] "Balance" of the position i - doubled amount of consostants minus amount of vowels in i-th prefix. Then the longest "good" substring, which begins at i'th position ends at the farest position j, such that B[j] >= B[i]. Count for each balance the farest poisition, where we can achieve it, then for each balance count the farest position, where we can achive equal or greater than it. Finally, iterate threw a string and for each position count the longest "good" string, which ends here.
•  » » 10 years ago, # ^ |   0 O(n^2) obviously will exceed time limit. Expected solution was O(nlogn) .One of the solution I saw, used Binary search . (Don't ask on what ;-) )Other used some kind of tree. Binary Indexed one. (I was never able to fully remember this thing. :( )
•  » » » 10 years ago, # ^ |   0 I'm pretty sure my solution is O(N).
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 O(N?) solution:Si is character at position i in input stringCalculate cumulative sum, cumu, of -1s for vowels and of +2s for consonants, after each character Si in string  - maximum possible sum it 400,000 (2 x 200,000)  - minimum possible sum is -200,000 (-1 x 200,000)As cumulative sums are being calculated, fill array Array of 600,001 ints so A[CUMU+20000x] contains first position, i, in string where cumu is >= CUMU  - 20000x is 200000 or 200001 for zero- or one-based array indexing, respectively  - fill each element no more than once i.e. fill A[CUMU+20000x] the first time cumu is CUMU    - for a new cumu when Si is a vowel, put i into A[cumu+20000x] the first time     - for a new cumu when Si is a consonant, put A[cumu+20000x-2] into A[cumu+20000x] the first time   - A[cumu+20000x-1] may need to also be filled for consonants because cumu-1 may have been stepped over from previous (cumu-2) to cumu [oops, pressed Post instead of Preview]  - maximum cool length at any position i, with cumulative sum of cumu, is i-A[cumu+20000x]
•  » » 10 years ago, # ^ |   0 My solution. Of cource this code may looks better but I'm little stuped and can't realize short and obvious solution.First idea. Let's substitute vovels by -1, consonants by +2, and calculate the sum on a prefix. Second idea. Let's find for any position the most length of correct string which started at this position. Of cource, it's the most distant element with a larger value of sum on the prefix.Third idea. Let's sort our array of pair (with element (0,0) - null element), and will support a pointer of last not used point in our array.
•  » » » 10 years ago, # ^ | ← Rev. 2 →   0 we need to keep track of the first position in the string that has a cumulative sum less than the or equal to any given cumulative sum the first time it comes up.  Hmm, for non-negative sums, the first position is always zero.  Haha, the joke is on me:  I only needed to keep track of the first position of negative cumulative sums!  the array only needs to be 200,000 elements long; the length for any non-negative cumulative sum after N characters is always N.
•  » » » » 10 years ago, # ^ | ← Rev. 2 →   0 I said: for any position let's find the string with the most length which started at this position. What is it hard to understand? I can explain it in another variants, but I can't understand what's the trouble.UPD: I'm understand
•  » » » » » 10 years ago, # ^ |   0 // Set earliest position, at which negative cumulative sums will occur, to 0// - Zero is a marker value, which will be replaced by a positive number before any useint *earliest = new int[200001]; memset(earliest,0,200001*sizeof(int));// Initialize vals[] so vowels add 2 and consonants subtract -1 //- yes, i know that is backwards, but it doesn't matter!char sets[] = { "AEIOUbcdfghjklmnpqrstvwxyz" }; for (char* p=sets; *p; ++p) vals[toupper(*p)]=vals[tolower(*p)]=toupper(*p)==*p?1:-2;// Finally the loop, a thing of beauty:  for ( (cin>>c),posn=cumSum=maxLength=0; cin.good() && vals[c]; cin>>c ) {  int L = ++posn;    cumSum+=vals[c];    if (cumSum>0) L -= earliest[cumSum] ? earliest[cumSum] : (earliest[cumSum]=posn);    if ( LmaxLength ) { maxLength=L; count=0; }    if ( maxLength) ++count;  }Interesting g++ (Ubuntu 4.4.3-4ubuntu5) 4.4.3 optimization bug:  maxLength was reset to zero on each pass through the loop, even after it was set and verified as =L when (L>maxLength); my workaround was to make maxLength static.
 » 10 years ago, # |   0 after this contest Social Buttons disappered! Did admin forget to turn on all the stuff?
 » 10 years ago, # |   +5 Really nice contest......first three problems were really easy.....i should have solved them......got AC in only one.....misread one....got tle in other......it was a nice learning experience......thank you for the contest... :)waiting for the next contest and expecting a better performance next time..
•  » » 9 years ago, # ^ |   0 Оо, "Все задачи" - это очень удобно! Спасибо :)