RAD's blog

By RAD, 8 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  

8 years ago, # |
  Vote: I like it +13 Vote: I do not like it
Can you please translate this post to English?
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I want to know the 22nd test of problem E!!!!!
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
D is just a 2-sat problem???
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What's 11th test of problem C?
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    +1
    Also need this test!
    • 8 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 =(
  • 8 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?
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      thanks for a hint about equal numbers! it helped me!
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Now I need 18th test of problem C
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      This test helped me:
      5
      -1 -2 -6 -3 -4
      • 8 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?
8 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?
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    6th pretest is:
    4
    2 3 3 1
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      The answer is not
      4
      1 2 3 4
      ??
      • 8 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
        • 8 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.
      • 8 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
        • 8 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
          • 8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            U r right too! There are 2 solutions, so there are two answers to choose to output!
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
We can't see others solutions?
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    try test:
    3000
    1 2 3 4 5 6...... 3000

    ;)
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      My program outputs junk memory, god dammit. Should it output 3001 ?
      • 8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        yep!
        the answer is 3001
        • 8 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.
          • 8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Try this:

            Input:

            1

            2

            Output:

            1

            • 8 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.
8 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.
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    N = 9, answer is 36
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thanks, I found my bug.
    • 8 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
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is the 7th test case for E?
8 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 ?
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    yep)
    I solved it using Topological Sorting
  • 8 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 ;)
  • 8 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.
8 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
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    pls, show your code.
    • 8 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;    
      }
      • 8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        lol, same idea as mine :)
        • 8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          same idea as right ;)
          • 8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            but i got P.E. T_T
            • 8 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
              • 8 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
                • 8 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  you are right, I didn't see that case, thank you very much
                • 8 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 ' '.
                  • 8 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.
8 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
  • 8 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
    • 8 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. 
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
how to see others code??? 
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You cant see others solutions.
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      thank you
      • 8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Sorry dude, my bad, it is not obvious but actually you can see others code. Go to problem status and click on the left link, you should get solution pop up.
8 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???
  • 8 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it
    5
    3 5
    2 5
    1 5
    1 4
    4 3
    1 3
    2 3
    4 5
    4 2
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      what is the output?? 
      lets talk about sample input and output, output is 4 3, if it comes 3 4 then it should be WA, so how to differ that???how to be sure about the format
      ??
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      can you do me a favor? may i know test case 6?
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone post an idea for Problem E ?

Thanx ! :)

8 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.
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is the test case #3 for problem E?
8 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.
8 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.
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hmm, probably someone hacked the same defender's solution before you.
    • 8 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.
8 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...

8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I want to know the test 15th of problem B
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It is big random test where N=50
8 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 =).
  • 8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I am little confused, can you tell me why this code fails on the first test case?
    #include <cstdio>

    #define MAXN 3001

    int main() {
        int n, i;
        bool m[MAXN];

        scanf ("%d", &n);

        while (n--) {
            scanf ("%d", &i);
            m[i] = true;
        }

        for (int j=1; j < MAXN; j++) {
            if (!m[j]) {
                printf ("%d\n", j);
                return 0;
            }
        }
    }
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      First test != Sample test
      So try this test:
      3000
      1 2 3 4 5 6 7 ...... 3000
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can I see D's test 11?
  • 8 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
    • 8 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?
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
can I see E's test10?Thank you!
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is C's test case 19 ?
I`m getting WA :((
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
whats the 10th test case of problem c i  get tle in this case
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
My code is giving presentation error on Test case 4.

may i please see the case 4?? please?