brainail's blog

Codeforces Beta Round #17
By brainail, 14 years ago, In English
Welcome all to Codeforces Beta Round #17, which will be held 10 June (Thursday) 2010, 19:00 (UTC +4, Moscow time). This contest will represent I.
I would like to thank Mike Mirzayanov who made this contest possible, Artem Rakhov for helping to test authors solutions and Julia Satushina for nice the translation of problem statements into English. Great thank Gennady Korotkevich for preparation problem, writing authors solution and nice idea's. Hope you will like the problems.

I hope that number 17 would be interesting for you!

You can discuss the problems here in the comments after the end of the contest.

UPD: Contest the ended, thank you all for participation!
UPD: 
  • English tutorial is available here. 

Announcement of Codeforces Beta Round 17
  • Vote: I like it
  • +31
  • Vote: I do not like it

Comments Comments (41)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Is the link to number 17's page on wikipedia some kind of a hint on the type of problems for today's match? :P Prime numbers???
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
It is very disgusting. I have registered for the event and solved the problem but when I am submitting the solution it is saying "You should have registered". And there is no admin available to contact..
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can contact admin by his profile
    http://codeforces.net/profile/MikeMirzayanov
    There you can send a personal message if you want, ofc.
    Also, there were a link on the contest page to publish a question.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How Problem B can be solved?

using map in c++?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I've solved it using topsort, and then we must going from bottom to top and get the edges with minimal cost.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      It's Kruskal's algorithm.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        No it isn't. Test 1 provides a counterexample.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          I did Kruskal and it was fine :P
          → Reply
        • 14 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it
          It seems to me that certain problems have a time limit that's too strict for Java. The same code in C/C++ works, while Java gives a TLE. Can we have extra time for Java solutions and for other slower languages?
          → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what about this?

        3

        3 2 1
        3
        1 2 400
        1 3 100
        2 3 100

        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          I forgot to say that we mustn't allow situation, when anybody has more than 1 supervisor. It's little difference between Kruskal's algorithm and this problem.
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            How do you handle that? I was going to write

            3
            3 2 1
            3
            1 2 400
            1 3 200
            2 3 100

            → Reply
            • 14 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              I think, this algorithm is valid for this example.
              → Reply
              • 14 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                In case above Kruskal takes edges with weights 100 and 200, resp. so node 3 has 2 supervisors, and the correct answer is 600
                → Reply
                • 14 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  well, I have used Kruskal in contest time and a greedy approach later. I only assured that no node has indegree greater than 1 when i used Kruskal. And for the above case, the correct output should be 500.
                  → Reply
                • 14 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  I write above, that we will not allow such situations. If I said it incorrectly, please, sorry for my English.
                  → Reply
                • 14 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it
                  I solved it using the idea of kruskal but with little modification.  I pick the smallest non-supervised  node. In your case, 1st you pick "2 3 100", now par[3]=2;. next minimum cost is "1 3 200" but par[3] is not -1 so just continue and don't pick it up. Next cost is "1 2 400". Since par[2]=-1 then pick it and update it's parent. Total cost is 200+400=600
                  → Reply
                  • 14 years ago, # ^ |
                      Vote: I like it 0 Vote: I do not like it
                    You have made a mistake in your calculation. It should be 500, not 600.
                    → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Well, then why not Prim's? :P
        I think it should do better with Prim's.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          You're not trying to compute an MST. A simple counterexample has edges with weight 1 all connecting to one vertex; what happens is you want all but one vertex to have an ancestor. The MST that you find will violate the above condition.
          → Reply
  • 14 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it
    Simple greedy: for each employee i, we assign to the employee j if q[j] > q[i] and the cost is min (i.e. pick the smallest possible cost).
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      It can be easier..
      The problem assure us that the input is well formed (q[j]>q[i]). So we don't need to process the q value and the name of the employee that made the offer.
      At the end we only need to check if at most one employee is without a boss.
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    This is making Minimum Directed Spanning Tree out of a DAG. It can be solved in O(n+m) time, just remember the cheapest supervisor for each employee.
    → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Nice problem set!. Any hints on how to solve C? =)
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    N^4 - dynamic programming. It turns out that it's enough to fit the TL :)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thank you e-maxx =)
      For some reason during all the contest I thought that the string could contain any characters from 'a' to 'z' . I just realized that the only allowed characters are 'a','b' and 'c' =(
      I will try to solve it using DP as you suggested =)
      → Reply
14 years ago, # |
  Vote: I like it +21 Vote: I do not like it
Thank you brainail, thank you tourist! It was really good contest!
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
So, how was D solved?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    I've solved it in the following way.
    If n is quite small (say, less than 5 digits), then you can simply calculate
    bn - 1(b - 1) modulo c.
    Otherwise, let c = c1c2 with c1 and c2 coprime, and c1 consisting of primes dividing b. Then bn - 1 = 0(modc1) (because n-1 is very large), and bn - 1 = b(n - 1)modφ(c2)(modc2) (because b and c2 are coprime).
    And if we know the remainders modulo c1 and c2, then we can calculate the remainder modulo c, using the GCD representation kc1 + lc2 = 1.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it
    Use identity b^(10*x+y) = (b^10)^x * b^y
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I have a "solution"  which use fast exponentiation and it has TLE.
    Instead of dividing the bignum by 2 directly I multiply it by 5 and divide it by 10, and just keep a variable to point the first number before the decimal point.

    let n = 10^k,

    my solution is O(klogk) and k is at most 1 million. Most problemas I've done it's enough to pass.

    So can someone please explain the problem with this approach? Or the idea it was intented to pass and the implementation was bad?

    Thank you in advance.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I tried this too, but where it fails is that if N is d digits long, then to arrive at zero by iteratively dividing by a constant number, you will need to divide O(d) times. Every division takes O(d) time to execute since you're touching all digits (this value goes down as N shrinks of course, but not fast enough to make a difference for the complexity analysis.)

      So in the end you have an O(d2) algorithm which is too slow when d~106 as in this problem.
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
damm, the number of divisions is log(10^k) not log(k) =\, stupid mistake, thank you for replying.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why is the task of E so little decided? and C? =)
→ Reply