gridnevvvit's blog

Codeforces Round # 252 (Div. 2)
By gridnevvvit, 12 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?
»
12 years ago, hide # |
 
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
»
12 years ago, hide # |
← 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
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hope everyone good luck and success for the this contest

→ Reply
»
12 years ago, hide # |
 
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
»
12 years ago, hide # |
 
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
»
12 years ago, hide # |
← 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
  • »
    »
    12 years ago, hide # ^ |
    ← 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
  • »
    »
    12 years ago, hide # ^ |
     
    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
  • »
    »
    12 years ago, hide # ^ |
     
    Vote: I like it +43 Vote: I do not like it

    Black? Dat's racist.

    → Reply
    • »
      »
      »
      12 years ago, hide # ^ |
      ← 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
»
12 years ago, hide # |
 
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
»
12 years ago, hide # |
 
Vote: I like it -28 Vote: I do not like it

give me '-' pls

→ Reply
»
12 years ago, hide # |
 
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
»
12 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

Great round! Pretty interesting problems :)

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

Very hard D and E :(

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

Statements was unclear.

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

How to solve problem D?

→ Reply
  • »
    »
    12 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      12 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        12 years ago, hide # ^ |
         
        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
    • »
      »
      »
      12 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        12 years ago, hide # ^ |
        ← 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
      • »
        »
        »
        »
        12 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it

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

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

How to solve B?

→ Reply
»
12 years ago, hide # |
 
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
»
12 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

system testing is faster than usual .

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

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

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

    at first you should sort them by day.

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

waiting for editorials....

→ Reply
»
12 years ago, hide # |
← 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
»
12 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

what about editorials?

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

Rating is Updated

→ Reply
»
12 years ago, hide # |
 
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
»
12 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Hope to back ( green ) soon :)

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

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

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

i_love_gridnevvvit Why unrated?

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

Anybody help me out with C?

→ Reply
  • »
    »
    12 years ago, hide # ^ |
    ← 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
»
12 years ago, hide # |
← 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
»
12 years ago, hide # |
 
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
  • »
    »
    12 years ago, hide # ^ |
     
    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
»
12 years ago, hide # |
 
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
»
12 years ago, hide # |
 
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
»
12 years ago, hide # |
 
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
»
12 years ago, hide # |
 
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
»
12 years ago, hide # |
 
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