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 #64
By Connector, 3 months ago
if 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:)
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......................
By checking whether we can find b next-to where we found a , we can save 1 headline-expense. If b is not found next(next does not necessarily mean adjacant) to a . We will have to use another headline. So, then search the source string(that is the headline),from start for b. 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. Suppose a was found at 5th position, now we want to find b, nearer to 5th position but on the right side.
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 vector
printf("%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?
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.
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.
D was a bit tricky. Spent lot of time in debugging.