natalia's blog

School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round #45 (ACM-ICPC Rules)
By natalia, 14 years ago, translation, In English

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!




  • Vote: I like it
  • +85
  • Vote: I do not like it

Comments Comments (74)
| Write comment?
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
how to solve problem C?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    get the upperbound and lowerbound of feasible solution using bisearch
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Binary search for the minimal and maximal alpha, for which given stops are possible. Check if the next stop for these alphas would differ.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    Every station si gives bounds (si+1)/i > alpha >= si/i
    Now result can be floor(min_alpha). If floor(min_alpha)+1 also works then there are multiple solutions
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It's possible to find minValue and maxValue without binsearch. Just the main idea:
    Ai <= Alpha * i < Ai + 1
    Here you should do the following:
    minValue = max(minValue,  Ai / i);
    maxValue = min(maxValue,  (Ai + 1) / i);
    → Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
why the following code got presentation error on test 5 of Problem D

const 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<n) printf("-1\n");
    else{
        printf("%lld\n",bk[1]);
        printf("%lld",bk[a[1]]--);
        for(i = 2; i <=n;i++)
            printf(" %lld",bk[a[i]]--);
    }
    scanf("%d",&i);
    return 0;
}
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I haven't read it carefully but you should use %I64d instead of %lld.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      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.

      → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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?
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah

    my 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.


    → Reply
  • 14 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it
    Try test case 
    1
    5

    Correct answer is -1, you print
    0
    1

    I 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
    → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
My solution for C.
http://codepad.org/kS4YaBTk
→ Reply
14 years ago, # |
  Vote: I like it +12 Vote: I do not like it
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] >= 10

So, 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.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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?
→ Reply
14 years ago, # |
  Vote: I like it +12 Vote: I do not like it
Was this round rated?
→ Reply
14 years ago, # |
← Rev. 4   Vote: I like it -34 Vote: I do not like it

this is my code(my reply to Narashy  appeared below the  filix's post!!)

#include<iostream>

#include<vector>

using namespace std;

vector<int> per[100010];

int a[100010],num[100010],lab[100010];

int main(){

int n;

cin>>n;

for(int i=0;i<n;i++)

cin>>a[i];

for(int i=0;i<n;i++)

num[a[i]-1]++;

for(int i=0;i<n;i++)

{

for(int k=0;k<num[i];k++)

{

per[k].push_back(i+1);

if(per[k].size()>1)

{

if(per[k][per[k].size()-1]!=per[k][per[k].size()-1])

{

cout<<"-1";

return 0;

}

}

if(per[k].size()==1&&per[k][0]!=1)

{

cout<<"-1";

return 0;

}

}

}

int l=0;

while(per[l].size()>0)

{

l++;

}

cout<<l<<endl;

for(int i=0;i<n;i++)

{

cout<<++lab[a[i]]<<" ";

}

return 0;

}


→ Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
The ratings aren't updated.
Why?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

it seems large and it is because i don't know how to post a code here!

please tell me!!!thanks

→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

THX

→ Reply
14 years ago, # |
  Vote: I like it -6 Vote: I do not like it

can anyone help me?!

my code gives the correct answer(-1)to the test case below:

1

5

i couldn't find my mistake,its good to put the test case 5 here.

→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me?!

my code gives the correct answer(-1)to the test case below:

1

5

i couldn't find my mistake,its good to put the test case 5 here.

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    Try this

    6
    1 1 1 2 3 3

    -1
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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


      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        The code you have posted doesn't work for test case
        1
        5

        it gives
        0
        1

        debugging it is easy to see that
        num[0] is 0,

        Then you have
        for(int i=0;i<n;i++) // which only enters when i is 0, since n is 1.
        The inner loop is
        for(int k=0;k<num[i];k++) // since num[0] is 0, it doesn't enter

        It now breaks out of the outer loop and tries to print the permutations. It never even has a chance to print -1.
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can someone help me check whats wrong with my E? I failed testcase 25 :(

http://pastebin.com/VWkUw2Qj
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In D, any possible permutation works? Like
6
1 1 1 2 2 3

Is the solution,
3 2 1 1 2 1

Is 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.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      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.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        you should change into
        int a[100001];
        the array is small for the testcase
        good luck :)
        → Reply
14 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
What is the test 3 for F?And what is the output for the testcase
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi, are (Div 2) contests only for users in division 2? How do I know what division I'm in?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    If you are green or grey you are in Div 2, otherwise you are in Div 1.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    corporals and recruits are in div2, you are in div1 but you can also take part in competition (your rating would't change)
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
The judging system is down?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is an O(n^3) algorithm fast enough for G?
n is the number of planets.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Surely it is not. N ~ 200k, so O(NlogN) is required.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Wouldn't all-pairs shortest path algorithm be the way to go here?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        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.
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
hi.
problem B,what is it,answer?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    → Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    By the way, here passed a bruteforce like this in accordance with the limitations.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I got wrong answer in case no.7 ,,,problem - E -....plz any help

[code]

#include <string.h>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <map>
#include <set>
#include <sstream>

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<n;i++)
#define forr(i,a,b) for(i=a;i<=b;i++)
#define forr_(i,a,b) for(i=a;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<int> vi;
typedef vector<vi> vvi;
typedef map<int,int> mi;
typedef vi::iterator it;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef vector<string> vs;
typedef pair<string,int> psi;
typedef vector<psi> vpsi;
typedef queue<int> qi;
typedef queue<pii> qpii;
typedef unsigned long long ubig;
typedef long long big;
typedef long double bigd;
template<class T> string tos(T x){stringstream ss; ss<<x; return ss.str();}
int Draw,Ivan,Zmey;
vpii v1,v2;
int i,h,t,r,m,n;
class Substitute
{
public:

};
void solve()
{
queue<pair<pair<int,int>,int> > q;
bool vis[1000][1000];
mset(vis,0);
pair<pair<int,int>,int> start(pair<int,int>(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<pair<int,int>,int>(pair<int,int>(ch-(k+1)+v1[k].first,ct+v1[k].second),cc+1));
rep( l , min(m,ct) )q.push(pair<pair<int,int>,int>(pair<int,int>(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"<<Ivan<<endl;
else if(Draw)cout<<"Draw\n";
else cout<<"Zmey\n"<<Zmey<<endl;
return 0;
}

[/code]

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      why do u think my cycle detection is wrong?  and what do u mean by "single bfs"?

      iam using bfs
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Consider such an example of normal graph (vertices are numbers)
        1->2
        1->3
        3->4
        4->2
        Your 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).
        → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It's better to post your code in one of the services like codepad.org
    Please, edit your post.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there anyone know the test 6 for Problem C?thx

→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it
Hope there are no mistakes. :)

B: 5?
C: 8, 9, 17, 19, 25
D: 4, 9, 11
E: 4, 11, 25, 46
H: 9
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    On the test case 4 your program outputs just one number 1, white the correct answer contains two 1's.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
@natalia: Can you give that test case input?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
@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?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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 is
    1
    1

    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Oh ok, sorry. My mistake.
→ Reply