Hello!

A few hours later, on May 19th at 17:00 MSK, you are lucky to participate in Codeforces Round #184 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by: Gridnev Vitaliy (gridnevvvit), Ignatyev Alexander (dudkamaster). It’s our second round and I hope not last. We want to thank Gerald Agapov(Gerald) for help in preparation of this round, Michael Mirzayanov(MikeMirzayanov) for marvelous Codeforces and Polygon systems, Mary Belova(Delinur) for translating the problems.

We hope you will like these problems, and that it will be fun to solve them.

Also we strongly recommend you to read all the problems.

We wish everyone good luck and high rating!

**UPD1: Scoring will be standart: 500, 1000, 1500, 2000, 2500.**

**UPD2**: Editorial

**UPD3**: Congratulations to winners:

I like the previous contest of gridnevvvit. i hope this contest is similar to previous.

window is open, you can easily jump out.

I think it will be interesting.:)I hope that contest would be easier than last time(181 round)

I'm hope too :D

try it

two successive rounds that starts at 17:00(MSK) I hope this starting time keeps on.

"pretest 3" what a pretest!

Problem A ?... i can't imagine what is wrong in my code :(

in problem A,

it means you cant get sum of (10, 20) but you can get sum of(1,0), (100, 11), ... Maybe it's the 3th test

it says

at leastso I assumed that if both numbers had a digit that was 0 we could add them.also what exactly does

thisrefer to?For each digit p in number a and number b, at least one of a_p and b_p has to be 0.

e.g.: a = a_2 a_1, b = b_2 b_1 => a and b can be added if a_1 equals 0 or b_1 equals 0 (or both) AND [same condition for a_2, b_2] (=> a and b both have 2 digits, so a_2 and b_2 are non-zero => they can not be added)

In problem A, the maximum number of the chosen integers is between 0 & 4. Because if you choose a 2 digit integer, you cant get another one( If you choose another 2 digit number, the first digit of both of them is !0 & you cant sum that pair). And you cant choose more than one of 1 or 3 digit numbers with same reason. So in maximum case, Vasya can choose 4 numbers

a,_b_,_c_,_d_,a=="0",b= a one digit integer,c= a 2 digit integer,d= a 3 digit integer &d= "100" Sorry for my terrible English!this is not always true. what about the input

`1 0 0 0`

? he can choose all the 4 integers!UPD: just re-read the problem statement. the input i mentioned is invalid, because all the integers must be distinct! sorry about that!I_Love_WJMZBMR

This handle made my day.

Jump from the window.

I do not understand problem A's statement!!!

Can Anybody explain to me what problem A means? Thanks in advance.Problem A is weird.

Can you please explain this test case:

Can you explain with an example?

I thought that having two numbers

AandB, thenif and only ifeither of those numbers hasat leastone digit that is equal to 0, then the two numbers can be added.So for example 90 18 can be added, 11 99 can not be added and 10 100 can be added.

Sorry I also misinterpreted the question!

actually 90 and 18 cannot be added because at 10's place there are 9 and 1 and none of them is 0.

Yeah, this was my worst contest ever, A problem was very strange

It seems like I will never understand what the author wants to get in Problem A. Problem Statement: "...pairs of integers (a, b), such that for any decimal place at least

one numberhas digit0in this place ..." Step 2 of tutorial: "If we got number greater than 0 and less than 10, we take it." I really do not understand then test case 2.The Round #184 is displayed "finished" here. What happen?

what was the pretest 3 in problem A?

Horrible !!!!

What a case is pretest 3 !!!! :/

This was a hard contest.

worst contest ever for me.... :(

I can't connect to "yandex.st" website. This issue increases time of loading each page to 4-5 minutes for me. I should have waited a long time for reading problems or to see the result of my submitted code during contest. Anybody else having the same problem? Can the moderators fix this?

What? yandex.st?

Codeforces get js from

jandex.st. You can view the source code of this page and you can findyandex.stthere.Iraninan users have the same problem, but today I used mozilla and I didn't have the problem

I think in these cases, you should go to codeforces.com through a proxy, just a simple proxy could be fine since we don't need any JS in codeforces ;) : here is mine : www.jabeja.tk/p/index.php

ideas for solving C ??

Think of the binary representation of the sum and the binary representation of a 2^v -1 decimal number.

2^V-1=2^0+2^1+2^2+...+2^v-1 if array consist of distinict elements ans=MAX(a1,a2,...an)+1-n; there is only one problem if you have same powers in array.In this situation you need to transform your powers in such way that get distinict powers, for example: if you have 2^8,2^8,2^8 you can tranform it and get 10^8,10^9 if you have 2^4,2^4 you can tranform it and get 2^5

sorry for my poor english

2^0 + 2^1 + . . . + 2^n = (2^(n+1)) — 1 Your task was just to find the biggest power of 2 and count how many of the powers from 0 to the biggest are not shown in the sequence. but dont forget to change two a s to one a + 1 for example : 2^3 + 2^3 = 2^4...

During system testing it showed that my C got accepted. Now, it shows that it failed on test case 26. What happened?

It was retested, but i don't know the reason

Maybe they saw my solution and decided to add a new case. :(

Dynamic scoring would work better!

How to use long arithmetic in this solution?

Don't think you eally need it. What about d=gcd(p,q); p=p/d;q=q/d? :)

WA43. I think that we need long arithmetic because of p = big prime number and q = big prime number => their gcd equal to 1 and it doesn't change our p and q.

I am not talking about overflow. For example you have p=100, q=50. And your algo will find Pn=2 and Qn=1 which is quite the same.

And another question. Why thistakes AC and WA43? What is the difference?

In first one you use BigInteger by default so it is OK.

Can someone please explain this testcase for problem A: Input: 2 1 2 Output: 1 1

consider answers: (0), (1 1), (1, 2), if you can choose (0), you can choose(1 1), in both answers you couldn't choose two numbers that can add together.

Could someone, please, help me? I can't find mistake in my solution for C problem. Here is my code.

I think you need to delete (or count) elements that become 0 again.

Oh, damn. You're right, thank you! Such a stupid mistake :)

cool bug in the codeforces! http://nic.p.ht/up/c70903297fe1.png

it means that your solutions is in a queue and not now accepted :)

But I didn't pass the pretest of problem C :(

Jump from the window.

Conteste fogholade chert!! Maskhare bud...

what!?!?

http://translate.google.com/

Kudos to problemsetter for D. A really nice problem, in how a lengthy statement with many conditions can be visualized in a way that leads to a simple solution (although with several special cases to be checked).

To explain what I mean, my solution:

it's clear that the original graph, as well as any target graph, must be a DAG without multiple edges

the first condition for the target graph means that it contains a directed path through vertices 1->2->3->...->N; then, the 4th condition means that between any 2 corresponding vertices, there is no other (shorter) path, so "any edge from vertex i must lead to vertex i+1 or at least i+K+1"

the 5th condition boosts this to "any edge from vertex i must lead to vertex i+1 or exactly i+K+1"; you may view the graph as an incomplete cycle with additional "bowstring" edges

the 5th condition also implies that if there's a vertex i (with the smallest possible i) in any target graph that there's a bowstring edge from i to i+K+1, then all other bowstring edges may only lead from vertices i+1..i+K to the corresponding +K+1 vertices (if these exist); these conditions are also sufficient for any target graph

so if the input graph contains an edge from i to neither i+1 nor i+K+1, the answer is 0; similarly if there're 2 bowstrings i->i+K+1 and j->j+K+1 such that j >= i+K+1

if those conditions aren't satisfied, we must add all edges i->i+1 and then we can choose a suitable first bowstring edge (if the first bowstring in the original graph is a->a+K+1 and the last one is b->b+K+1, then the chosen first one must start at vertex at least b-K and at most a, inclusive, but also at vertex at least 1 and at most N-K-1, obviously); iterate over all those possibilities, or over all vertices from 1 to N-K-1 if there's no bowstring in the original graph

if we've chosen the first bowstring from i to i+K+1, the answer is 2^(maximum number of bowstrings we can add-number of bowstrings already starting at vertices between i+1 and i+K in the initial graph); the second part of the exponent is fixed due to all bowstrings having to start at vertices i+1..i+K, and the first is simple min(K,N-K-1-i) when indexing vertices from 1

precompute powers of 2 up to 2^K; then simply iterate over all possibilities and add them to get the answer

Details are skipped, feel free to ask if you find something lacking. Code: 3746010

Thanks. I am a setter of this problem, but there was another statement. There were no initial edges in graph. But Gerald gived idea to add initial edges in graph

for problem a test 3, the array of my output is :

[70, 40, 30, 100, 50, 60, 0, 16]

why it's get WA, if we sum from 70 until 0, the total is 350, and 350 + 16 is valid operation, i think...

thx

30, 40, 50, 60 and 70 can't be in the same output. Vasya can only sum pairs of integers (a, b), such that for

any decimal placeat least one number has digit 0 in this placeIn the second decimal place, none of them has 0

You cannot sum 40 and 30, for example

why ? isn't one of them has digit 0 ?

"Vasya can only sum pairs of integers (a, b), such that

for any decimal placeat least one number has digit 0 in this place."oohhh, took so long to understand that important sentence,

at first glance what crossed in my mind is, vasya can sum pair of integer (a,b) if a has at least one 0 or b has at least one 0

I made the same mistake and got two wrong answers. Two of my friends also misunderstood the statement. I think it would be better if there were more clear examples or sample tests

I wonder why updating ratings takes a lot of time!

Checking solutions is a way easier problem than updating the ratings I guess

You know, they have to change colors of nicknames at every single subdirectory. Manually. It takes time.

In Problem A. How can a single number form a pair?

We're looking for such numbers that if we choose any pair, their addition is allowed. But if there's just 1 number, there are no pairs, so we never get a situation which is not allowed, so 1 number is a valid output :D

But there is no addition as well if there are no pairs :/

Vasya wants to choose some integers from this set so that he could sum any two chosen numbers.

But the set dosn't contain two numbers! So the output cannot be a single number i guess.

Read "so that he can sum any 2 chosen numbers" as "there are no 2 chosen numbers that he can't sum". 1 number satisfies that.

I think sometimes CF expects us to read the mind of the problem setter. :/ no more arguing.

Sorry, but that's the standard convention in mathematics. I've encountered it several times (once with the warning that the problem statement uses strict mathematical logic :D).

hang yourself

taking long time to update ratings!!!

Congratulations!:)

Rating?

The contest time is too early for me! It's better if the contest starts two or three hours later.

Yeah, For me too!

The best contest ever... Problem C was easier than A!

Повесься

what does it mean?? "Повесься"