RAD's blog

Codeforces Beta Round #27 (Codeforces format, Див. 2)
By RAD, 16 years ago, translation, In English
We want to congratulate you with a happy new school year with this contest. We wish you excellent marks, easy exams and many Accepted in the contests. Let this year bring you many new and interesting knowledge!

Artem Rakhov and Codeforces team 

P. S. Note that the round will be held on the Codeforces Format Rules. Read the rules before the competition. Good luck!

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

Comments Comments (85)
| Write comment?
16 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it
Can you please translate this post to English?
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
I want to know the 22nd test of problem E!!!!!
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
D is just a 2-sat problem???
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
What's 11th test of problem C?
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
What is the 6th test case for C??
Or any hints about C?
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
We can't see others solutions?
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
Can anyone tell me why my solutions for the first problem is not good. I cant find any mistake.
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
RAD, could you tell me the input and output for the 4th test case in problem E? Thank you.
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
What is the 7th test case for E?
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
What about the second problem. Is it possible to solve it using DFS ?
→ Reply
  • 16 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    Easiest way to solve is to use transitive property of comparison.
    i.e. if for x and y participants exist such another participant(z), that 
    • p_x>p_z & p_z>p_y (won x and lost to y) => p_x>p_y (y better x)
    • p_x<p_z & p_z<p_y (lost to x and won y) => p_x<p_y (x better y)
     Otherwise we cannot define outcome and able to output any.

    PS. IMHO TopSort absolutely crazy for that problem ;)
    → Reply
  • 16 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    yes. because everyone has a "pj", we can think the input as a directional Graph. if a and b appear less than N-1 times, then dfs(a,b)-bool. if a can reach b, we can see a win b.

    Just as SKYDOS 's TopSort.
    → Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
In problem B how it's supossed to write the numbers??
I did it like
cout<<num1<<" "<<num2<<endl;

but I got P.E. on test 1
→ Reply
  • 16 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    pls, show your code.
    → Reply
    • 16 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it
      here is my code:

      #include <iostream>
      #include <cstring>
      using namespace std;

      int games[60][60];
      int winsto[60][60];

      bool getsToWinTo(int i, int j)
      {
           for(int ii=1; ii<=60; ii++)
           {
               if(winsto[i][ii] && winsto[ii][j])
               return true;         
           }
           return false;
      }

      int main()
      {
          int n;
          cin>>n;
          int a,b;
          memset(games,0,sizeof(games));
          int t=n*(n-1);
          t/=2;
          t--;
          //cout<<tope<<endl;
          for(int i=0; i<t; i++)
          {
                  cin>>a>>b;
                  games[a][b]=1;
                  games[b][a]=1;
                  winsto[a][b]=1;
          }
          bool done=false;
          for(int i=1; i<=n; i++)
          {
                  for(int j=1; j<=n; j++)
                  {
                          if(i==j) continue;
                          if(!games[i][j] && getsToWinTo(i,j))
                          {
                                cout<<i<<' '<<j<<endl;
                                done=true;
                                break;   
                          }        
                  }       
                  if(done) break;
          }
          //cin>>a;
          
          return 0;    
      }
      → Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
RAD: Can I please have test case 18 for C, and 10 for D...? Thanks
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
can i know what is the test case 3 for Problem B???
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone post an idea for Problem E ?

Thanx ! :)

→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
my solution about A B C.
hope can do something to you.

i want to know how to do C and E.
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
What is the test case #3 for problem E?
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
Hey, 

How can I view others solutions? The popup box which appears doesn't have the  other  code.
→ Reply
16 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it
I generated a huge data to hack a TLE solution, but the judge says 'submit already challenged'. What does this mean??? 
I wasted a lot of time to try to hack it, But this solution hadn't been hacked until faild on system tests.
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
Can someone please have a look at my solutions to problem C and D and help me identify the flaws in it...

→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
I want to know the test 15th of problem B
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
Nice problem set (Y).

Other solution for problem E could be:
* Factorize N (assume that M will be the number of prime factors) -- O(sqrt(N))
* Calculate all the possible arrays b[1..M'] (M' <= M) multiplying i prime factors of N (with i: 0 <= i <= m) -- O(M * 2 ^ M))
* Sort the resulting array b[1..M'] in non-increasing order -- O(M' log M')
* Calculate a number X (X = 2 ^ (b[1] - 1) * 3 ^ (b[2] - 1]) * 5 ^ (b[3] - 1) ...) -- O(M' log N)
* Take the minimum X among all the possible arrays -- O(sqrt(N) + M * 2 ^ M * (M' log M' + M' log N)). This algorithm will run in time.

For example,
N = 16
* b = [2, 2, 2, 2] -> 210
* b = [4, 2, 2] -> 120
* b = [4, 4] -> 216
* b = [8, 2] -> 384
* b = [16] -> 32678
(Some arrays may appear several times)

I wanted to share this information with you, but, IMO DP is a more elegant (and shorter) solution for this problem =).
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
Can I see D's test 11?
→ Reply
  • 16 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it 
    6 5
5 3
4 1
2 6
5 1
5 2
    → Reply
    • 16 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it
      I have this solution for this problem. This is the exact same solution I submitted during the contest (I corrected only couple of identations). I have tested it against your test and got ioioi, which seems to be correct answer. Still I get wa 11 when submitting. Any ideas of flaws in my algorithm?
      → Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
What is C's test case 19 ?
I`m getting WA :((
→ Reply