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

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.

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

O(N?) solution:

Si is character at position i in input string

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

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 thetime it comes up.

firstHmm, 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 ofcumulative 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.

negativeI 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// - Zero is a marker value, which will be replaced by a positive number before any use

int *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 ( L<maxLength ) continue;

if ( L>maxLength ) { 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.

thank you for the contest... :)

waiting for the next contest and expecting a better performance next time..