gridnevvvit's blog

Codeforces Round # 252 (Div. 2)
By gridnevvvit, 11 years ago, translation, In English

Hello!

Soon (on June 8 at 19:30 MSK) you are lucky to participate in Codeforces Round for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by: Gridnev Vitaly (gridnevvvit) and Danil Sagunov (danilka.pro).

We want to thank Gerald for help in preparation of this round, Delinur for translation of statements and MikeMirzayanov for marvelous Codeforces and Polygon systems.

Scoring will be next 500 — 1000 — 1500 — 2000 — 2500.

Contest finished, congratulations to winners!

  1. kuangbin10
  2. ToumaKazusa
  3. qiaoranpenxiang
  4. rotoZOOM
  5. umczca195

Editorials will be there

Good Luck!

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

Comments Comments (115)
| Write comment?
»
11 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Hope this round to be a bridge to be a div1 contestant for the first time , just hope

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    gl & hf

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    another hope not back to green :(

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why does my 6839434 for A fail?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Because you have WA

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      you break out of the loop but you don't handle the rest of input in that loop

      Ex: 3 50000, 1 50000, 3 100000 1 110000, 3 120000 110000 120000,

      Your code it will read it as if the 3rd k = 110000 because you break after the 1 in the 2nd

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Because you used break;

      So, you did not ignore the remaining entries of that seller, and the next entry (which was to be ignored) was taken as the number of products with next seller and that ruined your code. your code works fine iff either no one has cheap product or only last product is cheap.

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      fixed 6850039

      → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Good luck with preparing your second contest , Keep going for more =)

and I hope that the problems and the editorial will be reach with new and useful things to learn

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    This round is not second. This round is the ninth my round

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      The 236 round was your first round for both divisions and not your first round for Div2 only , now I see

      thanks for clarification =)

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Are there many hacks?

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    You rating curve is so interesting~

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

Hope everyone good luck and success for the this contest

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

can any one give me the links of other contests DIV2 made by gridnevvvit :) thanks

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I have never been able to solve Div-2 C type questions during contest... I hope i do solve it this time :) Good luck everyone

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    start with C. This worked with me, hope it works with you also.

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

I guess that someone black will win this round again.

249 div 2 only

247 div 2 only

UPD: yeah, I'm right.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    I think they are people which already have an old account at Codeforces but they just build a new account to become candidate master in 1 contest!

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    let them
    I think making another account to compete in a div2 contest and be from top 10 ,that's the result of competing at div1 and lose every time or you can't make a significant score so you leave the real competing at div1 and try to stretch your muscles on a div2 players :)

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    Black? Dat's racist.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I don't think that what he was aiming to . Black is the non-rated contestant as he didn't enter any contest just as the color of your account

      And give me a break , you are putting Hitler photo and talking about racism ? =D

      → Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

A question: Why everybody says that the scoring will be announced later?! Couldn't they publish it earlier?!

→ Reply
»
11 years ago, # |
  Vote: I like it -28 Vote: I do not like it

give me '-' pls

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Sure. ^_^

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that's a bad idea according to amount of trolls around :D

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

Gd luck every one, hope I rise my rating this time :3 :D

→ Reply
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Great round! Pretty interesting problems :)

→ Reply
»
11 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Very hard D and E :(

→ Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Statements was unclear.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    What thing is unclear for you in the statements? I will try to do better statements in the future

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      A problem, i read three times to understand statement. B problem, i didn't now is possible to collect any number of fruits(<b[i]) or you must collect all fruits from this tree.

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you find the exit you asked for?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      oh, i was nervous,i have made stupid mistake in A problem(i set INF 10^5 instead of 10^6)

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    wasn't unclear ... just a little bit hard to understand . ;)

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yaap... statement was not clear to me too... :/
    but the notes after each problems helps me a lot... thanks to author for that... :)

    → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve problem D?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 4   Vote: I like it +11 Vote: I do not like it

    There were a few key points :
    1) Number of swaps needed to make a permutation an identity permutation are N-C, where N is the number of elements and C is the number of cycles in the permutation. This can be proved using the statement 2 and 3 below (that it is unoptimal to swap outside cycle) and that a cycles of size M needs M-1 swaps to be sorted (provable by induction on M).

    2) Swapping two numbers in the same permutation cycle increases the number of cycles by 1. This can be proved constructively (take a cycle C, swap two elements and see that two new cycles are made.)

    3) Swapping two number from different permutations decreases the number of cycles by 1. Again, constructive proof.

    We have some number of cycles in the given permutation P, and we need N-M cycles in the target permutation Q. Hence keep on making an inter or intra cycle swap depending on which is bigger; and greedily choose the smallest index for lexicographically smallest solution. Complexity O(N2)

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The problem is tagged with disjoint-set unions. How can dsu's be used in this problem? What I did was to calculate the new disjoint cycles of the permutation resulting from every optimal intra/inter cycle swap.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        DSU can be used, for example, for joining cycles to cycle containing vertex 1 (The first case in editorial).

        → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please provide a code where you have implemented the above idea ? Thanks.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 3   Vote: I like it -17 Vote: I do not like it 
        #include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<bitset>
using namespace std;

bitset<4000> vis;
int phi[3000];
vector<vector<int> > v;
priority_queue<int> pq[3000];
int ind[3000];
int cyc;
int n;

void process(){
   for(int i=0; i<n; i++) while(!pq[i].empty()) pq[i].pop();
   vis.reset();
   v.clear();
   
   cyc=0;
   for(int i=0; i<n; i++){
      if (vis[i]) continue;
	  int j=i;
	  cyc++;
	  vector<int> tmp;
	  while(!vis[j]){
	     tmp.push_back(j);
	     ind[j]=v.size();
		 
		 pq[v.size()].push(j);
		 if (tmp.size()>2) pq[v.size()].pop();
		 
		 vis[j]=1; j=phi[j];
	  }
	  v.push_back(tmp);
   }
}
int main(){
   scanf("%d",&n);
   vis.reset();
   for(int i=0; i<n; i++){
      scanf("%d",&phi[i]); phi[i]--;
   }
   
   process();
   
   int m; scanf("%d",&m);
   m=n-m;
   
   if (m>cyc){
      int diff=m-cyc;
	  printf("%d\n",diff);
	  for(int it=0; it<diff; it++){
	     if (it) putchar(' ');
		 int x,y;
		 for(int i=0; i<v.size(); i++){
	        if (v[i].size()==1) continue;
		    x=pq[i].top(); pq[i].pop();
		    y=pq[i].top(); pq[i].pop();
		    break;
	     }
		 printf("%d %d",y+1,x+1);
		 swap(phi[x],phi[y]);
		 
		 process();
	  }
	  puts("");
   }
   else if (m<cyc){
      int diff=cyc-m;
	  printf("%d\n",diff);
	  for(int it=0; it<diff; it++){
	     if (it) putchar(' ');
		 int x=v[0][0],y=v[1][0];
		 printf("%d %d",x+1,y+1);
		 swap(phi[x],phi[y]);
		 process();
	  }
	  puts("");
   }
   else{
      puts("0");
   }
}
        → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Here is my implementation of the above idea, as requested.

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

How to solve B?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you must sort your trees by days and then model situation

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i stored the number of fruits on tree i in pp[i-1] and then iterated from 0 to n, picking as much fruits as possible. this is the submission http://mirror.codeforces.com/contest/441/submission/6845290 why is this approach wrong?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it

        Because you are summing the fruits you can collect to the Nth day...
        Here in your code — Line 22 : 

        for (int i = 0; i < n+1; ++i)
	{
            ...

        Should be : 

        for (int i = 0; i <= 3001; ++i)
	{
            ...

        UPD: That is one of your mistakes, but not that you got WA for.

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

Did everyone run the loop till the maximum day value for problem B? :P It was a pretty good hack.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    so what is the good test to hack them?

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Till max day + 1 of course :))

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yes, till max day + 1 :D The best way was to run it till <=3001

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good hack.. But in my room almost everybody run till <=3001 :) I have hacked only 3 submission.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, I ran till N :) Nobody hacked me, and I failed just on 26th test. How unfortunate.

      → Reply
»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

system testing is faster than usual .

→ Reply
»
11 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I'm new to CF and I read problem E first...

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

what was the correct way to solve DIV 2 B problem.i approached by first solving for day[i-1] and then for day [i] ...but got wrong answer on pretest 5 http://ideone.com/mWCTzM

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    at first you should sort them by day.

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    have three integer variables curPicked, prevDay and curDay. Then try to pick as many fruits as possible from the trees of prevDay and curDay while making sure that curPicked<=v.

    In my solution I created an array of 3000 elements for the days and for each day I saved all the different amounts of fruits that can be gathered on that day specifically. Note that the order doesn't matter.

    then it's just a matter of using the above 3 variables and the array effectively while taking care of the corner cases.

    Total time complexity: Θ(max of n)

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I see no reason, why you assumed that only for any particular day x, only one tree will have fruit at that day. Given your piece of code, day[st[i].day]=st[i].cap;.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      my mistake...at starting i remembered it but at last i forgot it.. AC by changing to day[st[i].day]+=st[i].cap; :'(

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    corrected...the days were repeated...did'nt noticed it just changed day[st[i].day]=st[i].cap; to day[st[i].day]+=st[i].cap; and AC :'(

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

waiting for editorials....

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Problem-C : Code implementation finished....contest 1 min remaining , when compiled--- several errors . After correcting errors...15 sec remaining>>>> finally, couldn't submit during contest !!!! Bad luck.. Anyways, contest problems are nice :)

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

what about editorials?

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

after solving probelm, A I could have solved problem B but I went for E because I found it really interesting but i failed to solved it in the end. Was it a wrong decision?

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

Can Any body tell me where is the main differnce between those two codes..???

  1. WA in test 10 Code -- B
  2. Accepted Code -- B

I use max value for the last limit for first one. And Use 3000 as last limit in 2nd one... Why I got WA... Cant find it.....

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess in the first code, you can still collect fruits that became available on day 3000, on day 3001, which you never visit, the second code, allowed for this case to occur, by having +2 beyond the maximum day.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you.... Feeling like i am the biggest idiot in the world... thanks for pointing the mistake out....

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Edited code of your first one : 6849997
    just written 3001 instead of 3000. Hope, you have got the point.

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

Rating is Updated

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

I have a bad day , i had WA on test 1 in problem C because i was use printf %d with a long long int without noticing , i don't know that it really cause many problems , in my local compiler the answer was the expected but in codeforces test no.

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hope to back ( green ) soon :)

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

That was a really fun round, thank you gridnevvvit!!

→ Reply
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

i_love_gridnevvvit Why unrated?

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

Anybody help me out with C?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    I tried solving the problem greedily

    we need k tubes, each with size >=2. Now k-1 tubes will be of size 2 and the remaining points will be the last tube. However I didn't have enough time to figure out how to print the final tube in a way that satisfies the condition

    for any integer i (1 ≤ i ≤ r - 1) the following equation |xi - xi + 1| + |yi - yi + 1| = 1 holds;

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

why the hacks list is not shown yet ??

Edit: Now they appeared :D

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

Would you please tell me what is wrong for this code? It is for 441B — Valera and Fruits :

http://mirror.codeforces.com/contest/441/submission/6850959

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Got it!, this is not optimal, because I should go for the trees that are getting rotten first.

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

Problem D was very nice for me; guess I learned about permutations solving it more than my recent abstract algebra course :D though I couldn't manage to debug my code in time :(

Thanks for the round!

→ Reply
»
11 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Round Stats

P.S. Take a look on the match winner (kuangbin10) and these accs:
kuangbin9 kuangbin8 kuangbin7 kuangbin6 kuangbin5 kuangbin4 kuangbin3 kuangbin2 kuangbin1 kuangbin

→ Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

6844888 I don't know why I get WA on test 11,I think my output at least in this test is correct.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Oh,I am sorry,I didn't understand the meaning of the problem C last night.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Me too, I didn't understand the problem C

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

I solve the problem B with O(n^2) (for 1 -> max_day {for 1 -> n}). If have test max_day = 3000 , n = 3000 then it will work O(3000*3000) = O(9000000), but it not TLE. I am surprising about this. Because this, I hacked some people with test 3000, 3000 and all unsuccessful. I am sad about this

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

Why can't I vote twice on a comment. It may happen that I voted somebody down by mistake but now I want to revert or give up

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can only vote once on a comment. So as need think carefully before vote for 1 comment. Good luck !

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      can we not have a feature to change the vote

      → Reply