Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### brainail's blog

By brainail, 13 years ago,
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 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
• +31

| Write comment?
 13 years ago, # |   0 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???
 13 years ago, # |   0 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..
•  13 years ago, # ^ |   0 You can contact admin by his profilehttp://codeforces.com/profile/MikeMirzayanovThere you can send a personal message if you want, ofc.Also, there were a link on the contest page to publish a question.
 13 years ago, # |   0 How Problem B can be solved?using map in c++?
•  13 years ago, # ^ |   0 I've solved it using topsort, and then we must going from bottom to top and get the edges with minimal cost.
•  13 years ago, # ^ |   +3
•  13 years ago, # ^ |   0 No it isn't. Test 1 provides a counterexample.
•  13 years ago, # ^ |   0 I did Kruskal and it was fine :P
•  13 years ago, # ^ |   +3 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?
•  13 years ago, # ^ |   0 what about this?33 2 131 2 4001 3 1002 3 100
•  13 years ago, # ^ |   0 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.
•  13 years ago, # ^ |   0 How do you handle that? I was going to write33 2 131 2 4001 3 2002 3 100
•  13 years ago, # ^ |   0 I think, this algorithm is valid for this example.
•  13 years ago, # ^ |   0 In case above Kruskal takes edges with weights 100 and 200, resp. so node 3 has 2 supervisors, and the correct answer is 600
•  13 years ago, # ^ |   0 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.
•  13 years ago, # ^ |   0 I write above, that we will not allow such situations. If I said it incorrectly, please, sorry for my English.
•  13 years ago, # ^ |   0 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
•  13 years ago, # ^ |   0 You have made a mistake in your calculation. It should be 500, not 600.
•  13 years ago, # ^ |   0 Well, then why not Prim's? :PI think it should do better with Prim's.
•  13 years ago, # ^ |   0 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.
•  13 years ago, # ^ |   +17 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).
•  13 years ago, # ^ |   0 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.
•  13 years ago, # ^ |   0 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.
 13 years ago, # |   +1 Nice problem set!. Any hints on how to solve C? =)
•  13 years ago, # ^ |   0 N^4 - dynamic programming. It turns out that it's enough to fit the TL :)
•  13 years ago, # ^ |   0 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 =)
 13 years ago, # |   +21 Thank you brainail, thank you tourist! It was really good contest!
 13 years ago, # |   0 So, how was D solved?
•  13 years ago, # ^ |   +8 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.
•  13 years ago, # ^ |   0
•  13 years ago, # ^ |   +11 b1 = b mod Cif n is less than 1000 then n1 = n;else n1 = n mod phi(c) + 10 * phi( c );answer is b1^n1 mod C
•  13 years ago, # ^ |   0 Nice!
•  13 years ago, # ^ |   0 phi(c) is divisible by phi(c2) and phi(c1)
•  13 years ago, # ^ |   +12 Use identity b^(10*x+y) = (b^10)^x * b^y
•  13 years ago, # ^ |   0 cool :)
•  13 years ago, # ^ |   0 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.
•  13 years ago, # ^ |   0 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.
 13 years ago, # |   0 damm, the number of divisions is log(10^k) not log(k) =\, stupid mistake, thank you for replying.
 13 years ago, # |   0 Why is the task of E so little decided? and C? =)
•  13 years ago, # ^ |   +24 Decide = принять решениеSolve = решить (задачу)
•  13 years ago, # ^ |   0 Yes, bad English :-D