RAD's blog

Codeforces Beta Round #27 (Codeforces format, Див. 2)
By RAD, 14 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?
14 years ago, # |
  Vote: I like it +13 Vote: I do not like it
Can you please translate this post to English?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I want to know the 22nd test of problem E!!!!!
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
D is just a 2-sat problem???
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What's 11th test of problem C?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    +1
    Also need this test!
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      Copy AC solution and generate some test(for example 50), and check it. Or read right idea more carefully. 
      P.S. sorry for my poor english =(
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Some big test. N = 10^5, but there are only 2 different numbers. The answer is:
    3
1 3 4

    May be your program does not work properly with equal numbers?
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Now I need 18th test of problem C
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      This test helped me:
      5
      -1 -2 -6 -3 -4
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Looks like you and I are facing same problem.
        Btw, how are you getting the tests?
        → Reply
14 years ago, # |
  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
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    6th pretest is:
    4
    2 3 3 1
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      The answer is not
      4
      1 2 3 4
      ??
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I think it's 
        3
        1 2 4

        But I'm not too sure, I didn't get this problem right either
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Yes, that is one of the solutions. If there is a solution, then the shortest is always of length 3.
          → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        nope!
        answers are:
        (1)
        3
        1 2 4

        (2)
        3
        1 3 4
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Yes, yes, sorry, I only gave what my program would output, but you're right
          → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
We can't see others solutions?
→ Reply
14 years ago, # |
  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
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    try test:
    3000
    1 2 3 4 5 6...... 3000

    ;)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      My program outputs junk memory, god dammit. Should it output 3001 ?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        yep!
        the answer is 3001
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Hmm, i fixed that and upload it again, but now it fails on 4th test case.
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Try this:

            Input:

            1

            2

            Output:

            1

            → Reply
            • 14 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Without executing the code, i would guess the answer of my code, probably 3, obviously i misunderstood the problem, i thought the number should be bigger then the minimal number.
              → Reply
14 years ago, # |
  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
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    N = 9, answer is 36
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thanks, I found my bug.
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I Have Right Answer when I tested this test case on my computer  , why i still get WA on 4th Test case
      My Submission ID is 111986
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is the 7th test case for E?
→ Reply
14 years ago, # |
  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
  • 14 years ago, # ^ |
      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
  • 14 years ago, # ^ |
      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
14 years ago, # |
  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
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    pls, show your code.
    → Reply
    • 14 years ago, # ^ |
        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
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        lol, same idea as mine :)
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          same idea as right ;)
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            but i got P.E. T_T
            → Reply
            • 14 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              after i changed content of your inner cycle to:

              if(i==j) continue;
              if(!games[i][j])
              {
              if(getsToWinTo(i,j))
              cout<<i<<" "<<j<<endl; 
              else
              cout<<j<<" "<<i<<endl;
              return 0;
              }

              it got AC

              explanation: sometimes there is no such ii, that we can exactly determine outcome of battle between x and y.

              example:
              3
              1 2
              1 3
              → Reply
              • 14 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                forgot about reason of PE:
                seems, that ' ' is not valid char constant, but " " is
                → Reply
                • 14 years ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it
                  Original solution outputs nothing on test
                  3
                  1 2
                  1 3
                  That's the reason of PE, not the ' '.
                  → Reply
                  • 14 years ago, # ^ |
                      Vote: I like it 0 Vote: I do not like it
                    You're right, I thought, that PE appear at PreTest#1, not MainTest #1.
                    PS. I never tried to use ' ' (and haven't any lections at C) so post above is just theory.
                    → Reply
14 years ago, # |
  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
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    Test 18 for C is big random test, test 10 for D:
    6 4
6 3
1 3
6 4
5 3
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Now can I have test case 23 for D please. :)

      It'll be really great if the test cases were available in practice mode, just like in TC. 
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
can i know what is the test case 3 for Problem B???
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone post an idea for Problem E ?

Thanx ! :)

→ Reply
14 years ago, # |
  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
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is the test case #3 for problem E?
→ Reply
14 years ago, # |
  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
14 years ago, # |
  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
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hmm, probably someone hacked the same defender's solution before you.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      oops, This solution hadn't been hacked until failed on system tests.
      → Reply
14 years ago, # |
  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
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I want to know the test 15th of problem B
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It is big random test where N=50
    → Reply
14 years ago, # |
  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
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can I see D's test 11?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    6 5
5 3
4 1
2 6
5 1
5 2
    → Reply
    • 14 years ago, # ^ |
        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
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is C's test case 19 ?
I`m getting WA :((
→ Reply