### natalia's blog

By natalia, 9 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!

• +85

 9 years ago, # |   +3 how to solve problem C?
•  9 years ago, # ^ |   +1 get the upperbound and lowerbound of feasible solution using bisearch
•  9 years ago, # ^ |   0 Binary search for the minimal and maximal alpha, for which given stops are possible. Check if the next stop for these alphas would differ.
•  9 years ago, # ^ |   +6 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
 9 years ago, # |   0 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.
•  9 years ago, # ^ |   0 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);
 9 years ago, # | ← Rev. 2 →   0 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
•  9 years ago, # ^ |   0 I haven't read it carefully but you should use %I64d instead of %lld.
•  9 years ago, # ^ |   0 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.
•  9 years ago, # ^ |   0 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?
•  9 years ago, # ^ |   0 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.
•  9 years ago, # ^ | ← Rev. 5 →   0 Try test case 15Correct answer is -1, you print01I placed a while (bk[1]==0) ; in your code and gave a TLE in case 5, so the case is probably similar to the one I posted.edit: typo
•  9 years ago, # ^ |   0 Thanks very much，I've found the bug!
 9 years ago, # |   +3 My solution for C.http://codepad.org/kS4YaBTk
 9 years ago, # |   +12 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.
 9 years ago, # |   0 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?
 9 years ago, # |   +12 Was this round rated?
•  9 years ago, # ^ |   0 Yes. Just waiting =)
•  9 years ago, # ^ |   +6 When will the ratings be updated?
9 years ago, # |
Rev. 4   -34

### }

•  9 years ago, # ^ |   0 too large =/
•  9 years ago, # ^ |   0 Thank you!
•  9 years ago, # ^ |   0 Давайте все коды заливать на сайты как paste.ubuntu.com, codepad.org. ПОЖАЛУЙСТА !
 9 years ago, # |   +5 The ratings aren't updated.Why?
 9 years ago, # |   0 it seems large and it is because i don't know how to post a code here!please tell me!!!thanks
•  9 years ago, # ^ |   +1 For example: http://codepad.org/
 9 years ago, # |   0 THX
 9 years ago, # |   -6 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.
•  9 years ago, # ^ |   0 1 2
 9 years ago, # |   0 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.
•  9 years ago, # ^ |   0 Try this61 1 1 2 3 3-1
•  9 years ago, # ^ |   0 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
•  9 years ago, # ^ |   0 The code you have posted doesn't work for test case15it gives01debugging it is easy to see thatnum[0] is 0,Then you havefor(int i=0;i
 9 years ago, # |   0 Can someone help me check whats wrong with my E? I failed testcase 25 :(http://pastebin.com/VWkUw2Qj
•  9 years ago, # ^ |   0 I have given test 25 to OgieKako in the comments upper.
•  9 years ago, # ^ |   0 Sorry, I can't seem to find any posts by  OgieKako.  Can you help me out?
•  9 years ago, # ^ |   0 OgieKako's post is in russian and you can't see it in english locale. Try this link.
•  9 years ago, # ^ |   0 Oh ok thanks! May I know what is supposed to be the correct answer?
•  9 years ago, # ^ |   0 Use any correct solution to get it.
•  9 years ago, # ^ |   0 May I know what is testcase 46? I had runtime error :(
•  9 years ago, # ^ |   0 1 100 200 2 200 200 0 0 1 100 0
•  9 years ago, # ^ | ← Rev. 2 →   0 (ignore)
 9 years ago, # |   0 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.
•  9 years ago, # ^ |   0 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.
•  9 years ago, # ^ |   0 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.
•  9 years ago, # ^ |   +3 you should change intoint a[100001];the array is small for the testcasegood luck :)
•  9 years ago, # ^ |   0 oh thank you so much! Stupid mistake to make...
 9 years ago, # | ← Rev. 3 →   0 What is the test 3 for F?And what is the output for the testcase
 9 years ago, # |   0 Hi, are (Div 2) contests only for users in division 2? How do I know what division I'm in?
•  9 years ago, # ^ |   0 If you are green or grey you are in Div 2, otherwise you are in Div 1.
•  9 years ago, # ^ |   0 corporals and recruits are in div2, you are in div1 but you can also take part in competition (your rating would't change)
 9 years ago, # |   0 The judging system is down?
 9 years ago, # |   0 Is an O(n^3) algorithm fast enough for G?n is the number of planets.
•  9 years ago, # ^ |   0 Surely it is not. N ~ 200k, so O(NlogN) is required.
•  9 years ago, # ^ |   0 Wouldn't all-pairs shortest path algorithm be the way to go here?
•  9 years ago, # ^ |   0 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.
 9 years ago, # |   0 hi.problem B,what is it,answer?
•  9 years ago, # ^ |   0 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.
•  9 years ago, # ^ |   0 thanks.
•  9 years ago, # ^ | ← Rev. 2 →   0 By the way, here passed a bruteforce like this in accordance with the limitations.
•  9 years ago, # ^ |   0 thanks
 9 years ago, # |   0 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[1000][1000]; 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"<
•  9 years ago, # ^ |   0 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.
•  9 years ago, # ^ |   0 why do u think my cycle detection is wrong?  and what do u mean by "single bfs"?iam using bfs
•  9 years ago, # ^ |   0 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).
•  9 years ago, # ^ |   0 It's better to post your code in one of the services like codepad.orgPlease, edit your post.
 9 years ago, # |   0 Is there anyone know the test 6 for Problem C?thx
•  9 years ago, # ^ |   0 6 1 2 3 5 6 7
 9 years ago, # | ← Rev. 2 →   +5 Hope there are no mistakes. :)B: 5?C: 8, 9, 17, 19, 25D: 4, 9, 11E: 4, 11, 25, 46H: 9
 9 years ago, # |   0 For my solution of problem D - Permutations, it says presentation error on test 4 but I tried many cases on the compiler on my system and am getting it right. Please take a look at the code : http://www.ideone.com/FBceJ
•  9 years ago, # ^ | ← Rev. 2 →   0 On the test case 4 your program outputs just one number 1, white the correct answer contains two 1's.
 9 years ago, # |   0 @natalia: Can you give that test case input?
•  9 years ago, # ^ |   0 Test 4 for D is11
 9 years ago, # |   0 @natalia: The first 1 is the input n. Then the second line contains 1 number (i.e. 1) so the answer my code gives is 1. The number of values output should be equal to the value of n right? So my answer is correct I feel..what do you think is wrong?
•  9 years ago, # ^ |   0 First number in the output must be the number of permutations. Then there must be a line which desribes a partition of the given sequence for several permutation. So the correct answer is11
 9 years ago, # |   0 Oh ok, sorry. My mistake.