MikeMirzayanov's blog

Codeforces Beta Round #8
By MikeMirzayanov, 15 years ago, In English
Welcome and good luck on the round! 

I'd like to remind that if you have any questions on the problems, the best way to ask them is to use the web interface on the problems page. 

Later in the same post we will discuss the round. 

Wish you high rating,
MikeMirzayanov.

UPD. For contest you may thanks team Saratov SU #5, namely, users Fefer, Gerald and Polichka.

UPD2. And better late than never: the presence of English statements we are obliged only to Julia. Many thanks to her for 8 wonderful translations of 8 rounds.
Announcement of Codeforces Beta Round 8
  • Vote: I like it
  • +22
  • Vote: I do not like it

Comments Comments (78)
| Write comment?
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Admin, Please release the Test Data??
  It is very tough for me think of all the test cases....
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    If it's tough for you, find more easy challenge then.
    Do you know any contests with test cases release?
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Yes. TopCoder.
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        Hm, yeah, I didn't think about TopCoder. Sorry then.
        But anyway, there's more sense to proceed solve problems in practice room without knowledge of the test cases, in my opinion.
        → Reply
    • 15 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it
      Hm... Let me think... Like IOI, TopCoder, COCI, USACO and pretty much everything IOI-style...
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        OK, I agree.
        But this competition is in ACPC style and in this way organizers hide test cases even after the end of the competition.
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it
          Well, in ICPC you also can't view other person code, I guess. But here, you can download Petr's solution and just randomize cases until you find a non-working case on your code (I tihnk, that's gonna happen not so rarely). So, it will just make possible task simplier to release test cases after the contest.
          → Reply
          • 15 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it
            Hi, where I can download Petr's solutions?
            → Reply
            • 15 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              Enter contest -> Click on a number, showing how many users solved this task -> Click on any submission number

              It seems, that you can't scroll through all submissions, but you will find some "Accepted" for sure.
              → Reply
              • 15 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                i thnk now no one (except admin) can get "petr"'s solution(i have checked each sort option)

                showing solution in this way is not quiet uncomfortable to access...

                it shud be accesible through STANDING page.....

                so that everyone can see the solution of high rankers comfortably...(well that another kind of sort i think....... :) )
                → Reply
                • 15 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  Actually you can view Petr's solutions, check this out:
                  http://codeforces.net/contest/8/status/B?order=BY_ARRIVED_ASC
                  → Reply
                  • 15 years ago, # ^ |
                      Vote: I like it 0 Vote: I do not like it
                    sorry I forgot mentioning....

                    actually i was searching for problem A...... :)
                    → Reply
                    • 15 years ago, # ^ |
                        Vote: I like it 0 Vote: I do not like it
                      http://codeforces.net/contest/8/status/A?order=BY_ARRIVED_ASC
                      You can view any problem, just append order=BY_ARRIVED_ASC manually to the URL.
                      → Reply
    • 15 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it
      I am a fan of constructive argumentation; I would, therefore, be happy to learn some advantages of not releasing official test data. Until that I support all the frustrated coders who just can't find bugs in their solutions. Contest is one thing, but in my opinion the process of practice would only benefit if test data was available - whether one decides to use it or not, it is totally his/her responsibility and choice of training techniques.
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        You can view accepted solutions and compare them with your one. It's useful excercise.

        What does Mikhail Mirzayanov think about test data release?
        → Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that open test would be useful.

    Especially when an error is in technical details e.g. array sizes etc.

    → Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
why can the problem C shows out the PE error?
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Same problem here. Any ideas on why the PE for problem C test 5?
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is not differ much from WA.

      Solution returned some time T, and some order P.

      PE returned when total time, needed to collect objects in order P differ from time T.

      → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      It also happened to me. It was path reconstruction.
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Thanks Fefer and Enric, got AC now.
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          hi~can you tell me how did you solved the PE problem on test 5?
          i've been stuck at it for more than 2 hours...and can't find my problem...
          → Reply
          • 15 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            In my case, it was that my program first attempted to pick up a pair of objects, and recorded the best option, and afterwards when it tried picking up only one and found a better solution, it forgot to say "only pick up one" and so the order it output was wrong.
            → Reply
15 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Really liked the problems, but 1 geometry would be really enough :)
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
i think this time,the judge is too terrible:(
→ Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
It's a pity that testing problem isn't fully solved... Especially it felt at the end of the round, where appeared a huge queue of problems to test.
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Could you please post the 9-th test for the B problem? :)
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I think the 9th case consist of something like this,
    UURRDL

    Here the answer should be "BUG", but if you don't check the adjacent squares, you'd get "OK".
    → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
please provide the #Test9 for A - Train and Peter
→ Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
how can i turn the pages in the status?
→ Reply
15 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Who wants to see a Petr in a train? =)
→ Reply
15 years ago, # |
  Vote: I like it +5 Vote: I do not like it
There are some odd effects with ratings. For example, before contest I was in Division 2, solved 2 problems and now I have rating 1603. MRoizner was in Division 1, solved 3 problems and now has rating 1567. It seems a little bit strange.  =)
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It's all right. He solved problems worse than average participant of his 1st div.
    → Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    What's the different between Div 1 and Div 2?
    I am a new for Codeforces.
    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Non-rated users (newbies) or those having less than 1500 rating points belongs to second division. Others ( >= 1500 rating ) belongs to first division.

      By the way at first contest you have rating 1500 and have changes with it participating in second division.

      → Reply
15 years ago, # |
  Vote: I like it +20 Vote: I do not like it
Thanks for the nice problems!

Although when I submitted D for the second time, I was almost completely sure it will fail again, since there're too many if's :)
→ Reply
15 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Hi.  Is it possible to have a public Google Calendar with the match times updated on it?  This saves me trouble of converting between Moscow and New York time all the time ;)
→ Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
still WA on problem B...

I've considered situations like UURD... 
and I used a BFS.

But always get WA on the 1st Test....

any help?
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can use hash……I AC it with a map[230][230].
    → Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    no cycle,and bfs
    → Reply
  • 15 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    http://codeforces.net/blog/entry/259#comment-2894

    galymzhan:

    Problem B doesn't need BFS. I solved it in linear time using followin approach:
    set all f[201][201] = 0;
    set f[100][100] = 1; // start location
    simulate moving and for each new location f[x][y], check the sum of four adjacent cells. If the sum > 1 then answer is BUG.

    → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      UP
      me too.I solve it without bfs.
      → Reply
    • 15 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      nice algorithm
      But my method should not be wrong =.=
      still can't find my error...
      Maybe I should wait till test cases are released. :(
      → Reply
      • 15 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Does the test UD gets a BUG?
        → Reply
        • 15 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          yep...I tried this.

          → Reply
          • 15 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Hey, I solved mine like your idea exactly and the same problem ...but i think there is something wrong in the judge.have a look in my BFS function and got AC when i add that line , have a look:

            #include <iostream>
            #include <queue>
            #include <memory.h>
            using namespace std;
            #define pb push_back
            #define rep(i,m) for(int i=0;i<m;i++)
            #define mem(a,b) memset(a,b,sizeof(a))
            #define mp make_pair
            typedef vector<int> vi;
            typedef vector<vector<int> > vii;
            typedef long long ll;
            #define oo ((int)1e9)
            int arr[1001][1001];
            int vis[1001][1001];
            int dx[]={0 , 1 , 0 , -1};
            int dy[]={1 , 0 , -1 , 0};
            int BFS(int ii , int jj){
            queue<pair<int , pair<int , int> > > q;
            q.push(make_pair(0 , make_pair(500 , 500)));
            vis[500][500] = 1;
            while(!q.empty()){
            int j = q.front().second.first , k = q.front().second.second , len = q.front().first;
            q.pop();
            if(ii == j && k == jj)return len;
            rep(i , 4)
            {
            if(arr[dx[i]+j][dy[i]+k] == 0 || vis[dx[i]+j][dy[i]+k])continue;
            q.push(make_pair(len+1 , make_pair(dx[i]+j, dy[i]+k)));
            vis[dx[i]+j][dy[i]+k] = 1;
            }
            }
                 cout << "It will never cout this !!" ;
                 return 0; // without this line it will get WA in test case 1 , Now AC
            }
            → Reply
            • 15 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              thx a lot...but that's not my problem .
              I will try to rewrite this problem again...maybe there are some small flaws in my program, though I tried thousands times to make sure it won't :D

              BTW: It's not the problem about the judge. 
              the line: "return 0; "
              gives the operation a signal that the program ends correctly.
              otherwise the operating system on the server would think this program has some wrong, because no signal inform it that the program is right. 

              → Reply
              • 15 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                The return 0 is not in the main, its in a function I call. Also control never reaches this statement (Thats why I added a cout before it to double check). 
                It compiles successfully at the judge? Why should not work?
                → Reply
                • 15 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  so sorry that I didn't read your post carefully...
                  and I added that line, finally got AC.
                  Thank you so much, and now I understand the reason...because maybe the BFS can't find a route.
                  ^_^

                  and, sorry again.
                  → Reply
                  • 15 years ago, # ^ |
                      Vote: I like it 0 Vote: I do not like it
                    I am glad to help :)...but please Can you post a test case that I can't find a route ??
                    → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Could anyone explain how to solve problem C, please ? Is it greedy ?
→ Reply
  • 15 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    dp
    → Reply
  • 15 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    dp(S), which has 2^n states, the cost of visiting all the vertices s_i in the set S.
    Then, you can just visit one node, or two. This leads us to a n^2*2^n algorithm, which is too slow.

    Coding it in n*2^n using the fact that you can start from the first element in the set should be enough. When you visit just one vertex do one recursive call, and when you have to visit a pair of vertices just iterate on the second one (you can choose s_1 always as the first one). Precalculating distances in an array may also be useful.
    → Reply
15 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks for the contest :) It was my first contest here. Problem C seemed to be killing problem for me. I've got TLE #12 too many times. Finally I found out that I can make it N-times faster and finally got Accepted.
→ Reply
15 years ago, # |
  Vote: I like it +2 Vote: I do not like it

UPD: And many thanks to Julia for her devoted help in translating the 8th round in a row.

Not modest, but true...

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

Can anyone tell me what can be bug with WA 6 in problem C?

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

    Seriously, can anyone tell me what is the test case #6? I really want to know.

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

      Still remember this problem. I only glanced at your code, so I can be wrong, but here is something that I really don't think should be in there:

      if(n%2==0){
        for(int i=2;i<=n;i+=2){

      The oddity of the number of the objects does not matter, also you I don't think you want to jump 2 objects at a time. It looks like you are trying to make as many groups as possible, when in fact some objects are better left alone. (Precisely, pairing up any 2 objects which make an obtuse angle with the purse will only increase the distance, given how it's calculated in this task).

      Consider a bitmask dp where you either pick the leftmost zero alone or in a group with any other zero.

      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why for problem C time n * 2 ^ n is good?
24 * 2 ^ 24 = 402653184 - is not pass into 7,5 second
Who can explain me, where I wrong?

P.S. I understand Russian
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

(C.Looking for Order) My solution gets TL 18. It is working O((2^n) * n), I think it's OK for 4 sec. Can somebody help me?

→ Reply