### natalia's blog

By natalia, 12 years ago, translation, Good day!

I invite everyone to take part in the last contest of the series of WCS olympiads for school students which is one of the regular Codeforces rounds at the same time. The start of the contest is  on the 12th of December, at 11:00 MSK.

The competition rules are ACM-ICPC rules, the duration of the contest is 3 hours.

Like the previous school individual olympiads, the contest will be rated for all participants (both for school students and others). Rating will be calculated according to the merged result table.

The authors of the problems are me and Dmitry Matov again. Thanks to Gerald Agapov and Artem Rakhov for their help in preparing the problems and to Maria Belova for translating the problem statements.

Good luck everyone!

UPD. The contest is over. The results are available. The winner of School Personal Contest is scottai1, the winner of Codeforces Beta Round is ilyakor. Congratulations to the winners!

The author's problem analysis is posted. Now problems G and H are added to the tutorial, too.

Thanks to everyone who participated in WCS series for school students, officially and unofficially!  Comments (76)
 how to solve problem C?
•  get the upperbound and lowerbound of feasible solution using bisearch
•  Binary search for the minimal and maximal alpha, for which given stops are possible. Check if the next stop for these alphas would differ.
•  Every station si gives bounds (si+1)/i > alpha >= si/iNow result can be floor(min_alpha). If floor(min_alpha)+1 also works then there are multiple solutions
 Binary search on alpha. First binsearch on minimum alfa (check only the condition if alpha isn't too small), then binsearch on maximum alfa (check only the condition if alpha isn't too big). Then  compute next station for minimum and maximum alpha.
•  It's possible to find minValue and maxValue without binsearch. Just the main idea:Ai <= Alpha * i < Ai + 1Here you should do the following:minValue = max(minValue,  Ai / i);maxValue = min(maxValue,  (Ai + 1) / i);
 12 years ago, # | ← Rev. 2 →   why the following code got presentation error on test 5 of Problem Dconst int N = 100010;long long bk[N];long long a[N];int n;int main(){    int i, j, k;        scanf("%d",&n);    memset(bk,0,sizeof(bk));    for(i = 1; i<=n;i++)    {        scanf("%lld",&a[i]);        bk[a[i]]++;    }    i=1;    while(i+1<=n&&bk[i]>=bk[i+1])i++;    if(i
•  I haven't read it carefully but you should use %I64d instead of %lld.
•  No he shouldn't. If he've chosen Visual C++ compiler, of course... More than that, you don't need 64-bit variable here at all!Possibly that's a mistake:while (i+1<=n && bk[i] >= bk[i+1]) i++;Even if n = 4, Ai can be even 105.
•  Wild guess - by using "%lld" in scanf/printf, provided you sent it as GNU C++, since it doesn't work well on the compiler that's here (sad...). BTW, why use long longs in this problem?
•  yeahmy first code got presentation error on test 5 too.i had to change my code completely and then got AC.but still i don't know where i made the mistake.
•  12 years ago, # ^ | ← Rev. 5 →   Try test case 15Correct answer is -1, you print01I placed a while (bk==0) ; in your code and gave a TLE in case 5, so the case is probably similar to the one I posted.edit: typo
•  Thanks very much，I've found the bug!
 Here is a slightly different approach without doing binary search.When a car is located at station X and you refueled your car K times before (let's say initial moment also counts as refuel, so K >= 1), then the amount of fuel in the tank at station X is equal to [alpha * K - X * 10]. You can easily see that:- if you had to stop at station X, then [alpha * K - X * 10] < 10 because otherwise you would have reached the next station without refuel- if you didn't have to stop at station X, then [alpha * K - X * 10] >= 10So, input values give you a set of less/greater conditions on alpha, so you can calculate alpha_lo and alpha_hi for the input data. Then you have to check a few forward station indices X and see if [alpha_lo, alpha_hi) is non-empty for them using the same algorithm. If you find a single matching value X, then the answer is unique. Otherwise it's not.So, that gives you linear complexity in respect to the max station index.
 During contest I tried to post a question. First it stopped me with 1000 character limit while my question was ~300 characters long. Only issue was that it contained copy-pasted line from problem statement and formatting was long. I don't know how to improve this but I didn't like this situation and I think this should be fixed.Then when I finally managed to fit in character limit it sent a void message (while I am sure the text was there when pressing submit button). Has anyone had this kind of problems too?Can some admin look at this?
•  Yes. Just waiting =)
•  When will the ratings be updated?
12 years ago, # |
Rev. 4

### }

•  too large =/
•  Thank you!
•  Давайте все коды заливать на сайты как paste.ubuntu.com, codepad.org. ПОЖАЛУЙСТА !
 The ratings aren't updated.Why?
 it seems large and it is because i don't know how to post a code here!please tell me!!!thanks
 THX
 can anyone help me?!my code gives the correct answer(-1)to the test case below:15i couldn't find my mistake,its good to put the test case 5 here.
•  1 2
 can anyone help me?!my code gives the correct answer(-1)to the test case below:15i couldn't find my mistake,its good to put the test case 5 here.
•  Try this61 1 1 2 3 3-1
•  its right too!I'm really wondering !what's wrong with that!i have posted my code(bud it's a little unreadable!)you can check it your self...thanks
•  The code you have posted doesn't work for test case15it gives01debugging it is easy to see thatnum is 0,Then you havefor(int i=0;i
 Can someone help me check whats wrong with my E? I failed testcase 25 :(http://pastebin.com/VWkUw2Qj
•  I have given test 25 to OgieKako in the comments upper.
•  Sorry, I can't seem to find any posts by  OgieKako.  Can you help me out?
•  OgieKako's post is in russian and you can't see it in english locale. Try this link.
•  Oh ok thanks! May I know what is supposed to be the correct answer?
•  Use any correct solution to get it.
•  May I know what is testcase 46? I had runtime error :(
•  1 100 200 2 200 200 0 0 1 100 0
•  12 years ago, # ^ | ← Rev. 2 →   (ignore)
 In D, any possible permutation works? Like61 1 1 2 2 3Is the solution,3 2 1 1 2 1Is this a correct solution?In case this might be just a coincidence, This is the algorithm I applied;using a counting sort, count the instances of each number while also storing the numbers in an array. Then, reading the numbers in the array one by one and simply printing its count and then reducing its count by 1.http://codepad.org/GHUzcb2v this is the code if someone wants to go through it to understand what I have done.
•  The solution you give for your test is correct. The description of your algorithm seems to be correct too, but you should be careful with cases when the answer is -1, i.e. no partition exist.
•  I have simply checked that  for i, j such that i>j then count(i)<=count(j)If that is right then perhaps i made a mistake with my limits or something.
•  you should change intoint a;the array is small for the testcasegood luck :)
•  oh thank you so much! Stupid mistake to make...
 12 years ago, # | ← Rev. 3 →   What is the test 3 for F?And what is the output for the testcase
 Hi, are (Div 2) contests only for users in division 2? How do I know what division I'm in?
•  If you are green or grey you are in Div 2, otherwise you are in Div 1.
•  corporals and recruits are in div2, you are in div1 but you can also take part in competition (your rating would't change)
 The judging system is down?
 Is an O(n^3) algorithm fast enough for G?n is the number of planets.
•  Surely it is not. N ~ 200k, so O(NlogN) is required.
•  Wouldn't all-pairs shortest path algorithm be the way to go here?
•  It is a solution but not fast enough here. Since our graph here is a tree with one added edge, there exist some more efficient algorithms.
•  For B you need to do some pre-processing and calculate the sum of all elements in the square (0-i)*(0-j) for every i,j. This can be done in linear time as you read in the matrix. s(i,j)=s(i-1, j) + s(i, j-1) - s(i, j) + a[i][j].Then you iterate over the entire matrix and calculate the sum in the small rectangle which can now be done in O(1) using the above matrix.
•  thanks.
•  12 years ago, # ^ | ← Rev. 2 →   By the way, here passed a bruteforce like this in accordance with the limitations.
•  thanks
 I got wrong answer in case no.7 ,,,problem - E -....plz any help[code]#include #include #include #include #include #include #include #include #include #include using namespace std;#define all(c) c.begin(),c.end()#define rep_(i,n) for(i=n-1;i>=0;i--)#define rep(i,n) for(i=0;i=b;i--)#define min(a,b) ( a>b? b : a )#define max(a,b) ( a>b? a : b )#define sz size()#define pb(a) push_back(a)#define mset(a,v) memset(a,v,sizeof(a))typedef vector vi;typedef vector vvi;typedef map mi;typedef vi::iterator it;typedef pair pii;typedef vector vpii;typedef vector vs;typedef pair psi;typedef vector vpsi;typedef queue qi;typedef queue qpii;typedef unsigned long long ubig;typedef long long big;typedef long double bigd;template string tos(T x){stringstream ss; ss<,int> > q; bool vis; mset(vis,0); pair,int> start(pair(h,t),0),cur; q.push(start); int cc,ch,ct; while(!q.empty()) { cur=q.front(); cc=cur.second; ch=cur.first.first; ct=cur.first.second; q.pop(); if(vis[ch][ct]) { Draw=true; } else if(ch+ct>r) { Zmey=cc; } else if(!ch && !ct) { Ivan=cc; return; } else { vis[ch][ct]=true; int k,l; rep( k , min(n,ch) )q.push(pair,int>(pair(ch-(k+1)+v1[k].first,ct+v1[k].second),cc+1)); rep( l , min(m,ct) )q.push(pair,int>(pair(ch+v2[l].first,ct-(l+1)+v2[l].second),cc+1)); } }}int main(){ cin>>h>>t>>r>>n; v1.resize(n); rep(i,n)cin>>v1[i].first>>v1[i].second; cin>>m; v2.resize(m); rep(i,m)cin>>v2[i].first>>v2[i].second; solve(); if(Ivan)cout<<"Ivan\n"<
•  I don't know exactly what your algorithm is doing, but for example your cycle detection works wrong. You definitely can't solve this problem with single bfs.
•  why do u think my cycle detection is wrong?  and what do u mean by "single bfs"?iam using bfs
•  Consider such an example of normal graph (vertices are numbers)1->21->33->44->2Your algorithm would mark 1, 2, 3 as visited than it would process 4 and find edge to visited node 2, but in fact there is no cycle in this graph. Also this bfs is strange, because each vertex has a chance to be several times in queue.By "single bfs" I meant that standard approach uses bfs and dfs, however I know that somebody solved this problem using two bfses. I think it can't be solved with just one bfs (I can be wrong, because maybe second approach described in tutorial could be done by single bfs, I don't know).
•  6 1 2 3 5 6 7