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)
Congratulations to winners!!!
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?
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).
my C is Denial of judgement
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...
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. :(
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.
Thank You.
When I click on Hack, it did not do anything .
int x=1;
cout<<100000<<endl;
for(int i=1;i<=100000;i++)
{
if(x+1>1000000000) break;
printf("%d %d\n",x,x+1);
x+=2;
}
I have hacked some n*n solutions with this today.
(c) Egor
Let 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.
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. :( )
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.
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
thank you for the contest... :)
waiting for the next contest and expecting a better performance next time..