HolkinPV's blog

Codeforces Beta Round #72
By HolkinPV, 13 years ago, translation, In English

Welcome to Codeforces Beta Round #72.

The authors of the round are: Kholkin Pavel, Nikolay Kuznetsov and Kaluzhin Alexander. This round is for both divisions. You will get different problems and we hope that every participant solve as much problems as he can.

Thanks to Rakhov Artyom and Pavel Kuznetsov  for their help, Mary Belova for translating problems and Mike Mirzayanov for the perfect system.

The main hero of the problems is Valera. Today you should help him in everything. =)

Good luck and high rating for everyone =)

Upd: the contest is over, congratulations to winners:
in div1 - tourist
in div2 - StelZ40494
  • Vote: I like it
  • +93
  • Vote: I do not like it

Comments Comments (53)
| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
System test is too slow! Are you facing problems?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    It started late, but it was pretty fast (at least for div 1).
    → Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
New here,and ask a question.
Where can I see the changes of my rating in a picture?
Please help me. :)
→ Reply
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Hi,

May I know how do I access the full testcase for testcase 56 problem C? The testcase got cut off halfway :S
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    No way, you can just see a part of it (if it was large test case).
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Ugh, then how do I find out where my bug is? :S
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Thinking'll help you :)
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        May be an admin can help you with it and post it here like before.
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Its okay, I have found my bug. Thanks!

          Ugh, if I swap the order of 2 of my lines of code, I would have gotten AC for what qn :S
          → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Practice room for div2 already please!!! I am dying here to see why my B failed on test case 32.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Problems were really nice and varying in ideas and difficulty! At least for div 2 :)
→ Reply
13 years ago, # |
  Vote: I like it +11 Vote: I do not like it
In div 2 it is showing "system testing 100%" since long time. It should show "Contest Finished" now. Did something go wrong ?

→ Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Statements were needlessly lengthy.
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Rating graphs disappeared?!
They are back now.
→ Reply
13 years ago, # |
  Vote: I like it +9 Vote: I do not like it
Is that normal: tourist made his last hack after 2hrs?
02:00:32  D  Successful hacking attempt of portal
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi, I was looking at some of the solutions for 83C Track.  There were two very fast solutions (runtime ~ 50ms).  I checked them out and they seems to be doing fairly straight forward path search.  Any ideas on why they are so much faster than the other solutions (which are also ding path search)?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hey, I have solved C but on pretest No 1 I got WA, even on local machine it worked. I'm using C#. My code is here http://codepaste.net/pzyu3k. On first test case locally I get correct answer but on Codeforces site I get 0 -1 -1 -1. Is it BinarySearch broken on Mono or something else? Can anyone point it out?
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Hi,

May I know how should problem D be done? Here are some ideas I have.

1. K must be prime. If not, the number will have some divisor smaller than K.

2. Suppose K >= 10000. Then, suppose X is a valid number. Then X/K <= 2*10^5. We can check the factors of each X/K up to min(K,sqrt(X/K)). Then the complexity is thus on the order of 10^7.

3. Suppose K <= 10000. I was thinking of applying PIE, but I am not sure how to compute that in a fast manner. :S

Thanks in advance for your help!
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    This problem has recently appeared in a harder version in the Facebook Hacker Cup, you can see a small discussion in the main thread of the Hacker Cup in the TC's forum.

    Also, there's an old editorial for the problem SquareFree

    The main idea is the following:

    As you said, assume K is prime, or the answer is 0.

    If K > 45000, then the answer can only be 0 or 1. 1 in the case a <= K <= b.

    If not, you may try the inclusion exclusion principle in the following way:

    Add all divisors of K (b/K - (a-1)/K)

    subtract all divisors of K*2, K*3, K*5... (last prime less then K)*K. This means all combinations of K with another prime.

    Add all divisors of K*2*3, K*2*5, ... This means all combinations of K with another two primes.

    Basically, all combinations with an odd number of other primes will be subtracted and all combinations with an even number of other primes will be summed back.

    Why is it possible to test it? Because 2*3*5*7*11*13*17*19*23*27 > 2*(10**9). This means you can cut your search in the worst case having the maximum of 10 primes.

    This recursive function will do it:

    Assuming primes has the prime list generated and that kp is the index of the prime K.

    void go(ll val, int p, int sign) {
      if (val > b) return;
      res += sign*(b/val - (a-1)/val);  
      while (p < kp) {
        go(val*primes[p],p+1,-sign);
        p++;
      }
    }

    initial call: go(k,0,1)

    Unfortunately I didn't realized my first condition, of having K > 45000 and answer 1 =/, during the contest.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
System Testing is too slow. I coded for 2 hours and waited to see the result for another 2 hours. Hope the performance of the system can be improved. 
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    You don't wait. You do another works, after 2 hours, you see the result :d.
    → Reply
13 years ago, # |
  Vote: I like it +25 Vote: I do not like it
For Div. 2. : Doctor, is he male or female?
important for him. Since the doctor works long hours and she can't get distracted like that after all, she asked you to figure it out.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
If someone can tell me some specail tests about problem c...
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is the editorial out yet?
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Russian ones:

    http://codeforces.net/blog/entry/1961

    http://codeforces.net/blog/entry/1976

    http://codeforces.net/blog/entry/1979

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Hi,

      Thanks for the links. However, do you know when will the English analysis be ready?
      → Reply
13 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Can somebody explain part of the solution to problem C - track? I would just like to know how to find the lexicographically smallest shortest path from S to T, when you have fixed set of letters that you can use. I have translated version of the russian analysis but I don't understand it.


Edit. Finally, I managed to solve it.
→ Reply