Hello everyone.

Today I am an author of the contest. This round is for both divisions. There will be five problems in each division. This is my second round on the Codeforces. The actors in this contest will be walruses again =)

I want to thank Codeforces and **Alias** for helping me to prepare the round.

Good luck!

**UPD1: **

Points for problems in div1: 500-1000-1500-2500-2500

Points for problems in div2: 500-1000-1500-2000-2500

_{Codeforces Beta Round #64By Connector, 3 months agoif you wan't to see the problems by the same auther click here}After I locked C problem. Trying to hack my solution, and my solution got TLE. And I using that test and hacked 5 other coder`s solution. (Therefore test is suitable)

But my solution is accepted in final test.

Kind of guessed the answer in C and was pretty close in D.

I'm waiting for the editorial, especially for the proofs of C and D.

I am very suprised.In problem B,div2,I use string always got RE on pretest 2,but I use char got AC,why??whether it is relative to the head files,I type #include<string.h> and #include <string>

Thanks for the contest! The problems were excellent, varied, the statements were very clear, and I'm very curious about the problems that I didn't solve, which is the way it should be :)

BTW, I thought that more people would implement a brute-force approach in Div1 A (maybe they did in Div2 C). It looked like a good hack target but I only managed to find three slow solutions in my room.

Waiting for the editorial :)

Anyway, learning is always happy:)

Translate By Google Tranlate(English)Does anyone know when is the next contest?

Hope it helps, sorry for bad English.

Thanks a lot!It's very kind of you.

I need clarification for problem E(div 2). Specially i m very much confused about the paragraph

"Let's consider the ski base as a non-empty set of roads that can be divided into one or more tracks so that exactly one track went along each road of the chosen set. Besides, each track can consist only of roads from the chosen set. Ski base doesn't have to be connected."

What is meant by this paragraph......................

abcd,athen search forb, but don't start search from start, instead search from the position you last found the matching character that isain this case.Why we are doing this:: Because we don't want to take new headline unnecessarily .By checking whether we can find

bnext-to where we founda, we can save 1 headline-expense. Ifbis not found next(next does not necessarily mean adjacant) toa. We will have to use another headline. So, then search the source string(that is the headline),from start forb. Doing this again and again will provide you how many headlines you need. But this is SO costly. Every time you will have to search for a character in O(n) time. So, you see, this is very costly , given such constraints. So, we use binary search. We binary search for the next position where the next character to be searched is located. Supposeawas found at 5^{th }position, now we want to findb, nearer to 5th position but on the right side.How do we do this::b's location in a array.b's position. If nobis found after 5th position ::I have added few lines to understand what is going on on test case 2 of the example (abcd,dabc)....

forn(i, tn)

{

vi &v = pos[t[i] - 'a'];

// v[3]=3 for 'd'

int j = lower_bound(all(v), p) - v.begin();

// can't understand.

have read about lower_bound.but how p=0 will find 3 in vectorprintf("%d\t%d\n", j,p);

if (j >= sz(v))cnt++, p = v[0] + 1;

else

p = v[j] + 1;

}

printf("%d\n", cnt);

and I got this as the output:

0 0

1 4

0 1

0 2

2

could you please explain me little bit more as I am unable to correlate the output to the input with the help of code?

but how p=0 will find 3 in vector"1. If the target is "dabc" and source is "abcd", then after 'd' p=4, so for target: 'a': v[0]=0; then how p=4 in lower_bound will give j=1?

2. What I have learned from Top coder algorithm tutorial and recipes is that to use binary search there should be predicate which is true for some interval and false for other interval. so we continuously divide the search space until found the correct one. But in this case we are maintaining separate container for every alphabet in source and storing its position. then we are applying steps you mentioned but how this is binary search? How have we divided the search space?

Lastly could you refer me more problem like this for practice.Lastly, there are lots of problem on binary search , here and at topcoder.Use Google (and the word "archive")1. "how p=4 in lower_bound will give j=1?"

for case 'a', vector v[0]=0 has only 1 element whose index or position is 0, which is represented by j. but then how j is giving value 1?

All the vectors in this case are maintaining only single element then j must be 0 for all the cases. So why it is giving 1 in case of 'a'.

2.

if (j >= sz(v)) cnt++, p = v[0] + 1;

this part of code is incrementing cnt or new headline and if p reaches end of the sorted values in vector then starting once again it from beginning. and

else

p = v[j] + 1;

this part is putting next value in sorted array of vector v in p.

So where are we dividing the search space? I suppose we are only iterating in the vector.

Likewise you mentioned in binary search we first search middle value then look at whether to search in [mid+1,high] or [low,mid+1], then further divide. but in this case how it is binary search.

C. Ski Base:

if input is :

4 4

1 2

1 2

3 4

3 4

why the last answer is 3 ?

I think it should be 2:

1-2-1 and 3-4-3

thanks in advanced!!!

D was a bit tricky. Spent lot of time in debugging.