akirakaze's blog

Codeforces Beta Round #17
By akirakaze, 16 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?
16 years ago, hide # |
 
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
16 years ago, hide # |
 
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
  • 16 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    You can contact admin by his profile
    http://mirror.codeforces.com/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
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
How Problem B can be solved?

using map in c++?
→ Reply
  • 16 years ago, hide # ^ |
     
    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
  • 16 years ago, hide # ^ |
     
    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
    • 16 years ago, hide # ^ |
       
      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
  • 16 years ago, hide # ^ |
     
    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
16 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it
Nice problem set!. Any hints on how to solve C? =)
→ Reply
  • 16 years ago, hide # ^ |
     
    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
    • 16 years ago, hide # ^ |
       
      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
16 years ago, hide # |
 
Vote: I like it +21 Vote: I do not like it
Thank you brainail, thank you tourist! It was really good contest!
→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
So, how was D solved?
→ Reply
  • 16 years ago, hide # ^ |
     
    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
  • 16 years ago, hide # ^ |
     
    Vote: I like it +12 Vote: I do not like it
    Use identity b^(10*x+y) = (b^10)^x * b^y
    → Reply
  • 16 years ago, hide # ^ |
     
    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
    • 16 years ago, hide # ^ |
       
      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
16 years ago, hide # |
 
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
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
Why is the task of E so little decided? and C? =)
→ Reply