Hi Codeforces community! I am glad to announce that at 27 November 16:35 (GMT time) will take place Codeforces Round #382 for participants of both divisions.

Author of this round is me (albertg). I am from Armenia ~~ and the only Armenian author of any Codeforces round yet. ~~ (Sorry Edvard). This round is my second round and ~~ I hope this is not the last one! :) ~~ it is the last one. As usual, I'm thankful to the coordinator of Codeforces Gleb Evstropov (GlebsHP) for helping to prepare this round and Mike Mirzayanov (MikeMirzayanov) for wonderful platforms Codeforces and Polygon. Also special thanks to Super_azbuka for an idea of a problem.

As usual, contestants will have 5 problems and 2 hours to solve the problems. In this round you should help Ostap Ibrahim Bender to reach Rio-de-Janeiro. Good luck and have fun!

**UPD1:** Scoring: div1 750-750-1500-2000-2500, div2 500-1000-1750-1750-2500.

**UPD2:** Editorial is posted.

**UPD3:** If somebody has question(s) about solutions of problems, please write me a personal message.

**UPD4:** Please read this.

**UPD5:** Editorial of problem div2E/div1C is posted.

Clashing with another contest

One of them (HR preferably), please reschedule, so we can participate in both.

If you want HR to reschedule why are you posting it here?

Who is Ostap Ibrahim Bender ?

He is a famous rapper from Odessa.

normal time again

Is it rated?

yes.

.

Its fu*king rated..! Dont ask is it rated or not !

see this

5 problems round again! Wish it to be an interesting round~: )

Hey, I'm new to codeforces. Can you please explain me what is Division 1 and division 2? Thanks.

Please

Thanks! Just one more query. Do we have to register separately for the contests (for instance, this one) or if we are on codeforces, we can directly give them? If we have to register separately, how to do so? Thanks again.

Yes, you have. Registration opens about 24 hours prior the contest.

waiting to see your performance in your first round

good luck

Thank you :)

I'm just a rookie. I hope to improve my coding on codeforces.

Again....5 problems!!!

18:35

Perfect time for me

Codeforces always helped me to improve my thinking capability , thank you codeforces :)

The comment is hidden because of too negative feedback, click here to view it

Lol, let's make it real!)

Petr has register for DIV 1. He must be aiming to get his second spot. Wish it to be exciting round!

TooDifficuIt has registered too. He will try to prevent this.

Actually he can get his second spot without participating :D

Tourist used that trick before, remember?

Is it all? Just a comment? Aren't you gonna write a blog?

Actually you also got second spot without participating :D

Seems like its too difficult to get positive rating change when you are among top rated contestants.

how can i help Ostap Ibrahim Bender to reach Rio-de-Janeiro?

I hope I can help Ostap Ibrahim Bender to

notreach Rio de Janeiro.Life is not the best right now here :P

You don't have to help, by the way, but I warn you, we have a long reach

Ostap Bender is a fictional con man who appeared in the novels The Twelve Chairs and The Little Golden Calf written by Soviet authors Ilya Ilf and Yevgeni Petrov.

So we should expect graph theory problems in this contest.

After a long time :D Back to home , codeforces ! The love! <3

Is it rated ?

Man, why? ;D

Nope)But it's rlly rated .

Yes, it is rated !!!

Ohhh....TY man!

Question of the day)

Hello.

This is my first contest.

Wish me good luck.

Also every Punjabi add me.

Jai babe di

Good Luck!

Thank you for your wishes.

I was solved with 4 problems .

I do coding and get a job and a girl friend and a happy life with some naughty time .

Also I am trying to get girlfriends on CodeForces.

Add me.

Stay strong guys! Good luck and happy coding.

## NeverSayNever

Score Distribution?? Not declared yet, 17 minutes left

"scoring will be posted just before the contest" might mean 30 seconds before the contest :)

30 secs left, still nothing)

Where is scoring?

So the contest is gonna be delayed again?

At least I don't have to worry about system test (and can sleep early)

A=B=C=D<E

That sad moment when you're certain of your solution but it won't pass and you can't find where is the error

rip rating :/

Same as you, WA test 5 C and WA test 6 D

RIP rating :(

Plese someone tell me what where those tests so I can go cry myself to sleep

WA 5 C, hacked D ;_;

on D instead of searching for highest prime I searched for any prime P with

n-P< = 500 and it passed test 6, the pure greedy solution isnt correct it seemsCheck out Goldbach Conjecture

I repeat this 1000 times: while (n > 0) { x = calc(n) // calc(n) = the biggest prime number which is <= n; repeat x = calc(x — 1) 0 -> 3 times if n — x = 1 then x = calc(x — 1); res++; }

No need of searching.

If prime, print 1.

else if even, print 2

else if n-2 is prime, print 2

else print 3

You know, before the contest I knew nothing about Goldbach Conjecture and never used logN prime test. I learnt all of this just during the contest and implemented this: if prime ans = 1, if even ans = 2, if odd ans = 3. But why if n-2 is prime then ans = 2? I understand that this is true, but why namely n-2? Why not n-4? Maybe I just dont know math good enough :(

Because 2 is the only even prime number.

Yeah, thanks. I should have thought about that...

because 4 is not prime. You check for n-2 because 2 is also prime, and then that odd number would be written as a sum of 2 primes. if you checked for n-4, then you would decompose the number in one prime plus 4, which would give 3 instead. The only case that an odd number is a sum of two primes, is when one of them is 2.

Sorry, n-4 is my mistake. Then why not n-3? I see that 2 is somehow more unique in this case, but why namely 2? Is there a theorem or you just logically deduced this?

man, seriously!! are you even thinking? (no offence) this is too trivial.

The comment below explained it good and I really couldnt understand it. What is trivial for you may not always be trivial for every one. P.S. If you say "no offence" it is still an offence.

If an odd number can be split in 2 primes, one of them must be a 2, because in order for 2 numbers to add an odd number, one must be odd and the other one must be even. Then, the only posible split is 2 and n-2, if n-2 is prime.

Damn, how could I not get it before. :( Thanks, man!

Because 2 is the only even prime.

Are you talking about D? Cause I'm pretty sure mine is right too lol (unless I just entirely misunderstood the problem).

yeah, just found out it gives WA for 2e9 as input :/ fml

Lol that was my wrong answer too. Guess I should've googled a bit harder to find out about the Goldbach Conjecture.

Lol exactly same happens for me

rank dropped from 11 to 600 , just because of a stupid blunder :/

Overflow?

corner case in D . Dont know why i locked D so early :(

same with me

same here

D- WA on 6

C- WA on 5

How to solve Div1 C and D?

Div 1 C:

`DP(u, dist, nearest_one)`

is number of ways to color:`nearest_one`

.Edit: I am mistaken :P

How to solve Div2 C? Every time I see a problem about any kind of paired tournament I become sad.

It should be a Fibonacci Sequence...

https://www.quora.com/What-is-the-best-way-to-solve-SPOJ-problem-code-TENNIS1

Contest quality is going down nowadays :/

Wow, it even has tennis statement as well. I wonder how many people googled this.

Yes they didnt even bother to change the statement :P

and author of this problem is albertg and it is posted in 2014?

Well , even though this problem was googleable.

I reduced this problem to taking out the maximum possible height of an AVL tree for given number of nodes.

Then you can solve it using Cheating

Fibonacci Number relation.

Analyze that minimum number of players required for x number of games at top:

1 — 2 players

2 — 3 players

3 — 5 players (One having played 2 matches and other 1)

4 — 8 players (One having played 3 matches and other 2)

....

The answer is maximum index where fib[i] <= n

Think of it this way. To have a 1-game tournament, you must have 2 players. You can consider 1 player to be a 0-game tournament since there already is a winner. In order to have an n-game tournament, the winner of an n-1 game tournament must play the winner of an n-2 game tournament. This is simply a Fibonacci sequence and can be calculated using dynamic programming. (Extra players beyond the target Fibonacci number cannot make a difference because they cannot reach a high enough game depth to challenge the current champion).

Think recursively. Let the winner has to play x games. Then he has to play at-least x-1 games and the other player has to play at-least x-2 games. Now you can see the pattern. It's Fibonacci. Hope it's help.

I understand what you are saying but i do not get how does this recurrence relation F(n) = F(n-1) + F(n-2) give optimal answer(maximum possible played matches)...Even if it came on my mind during the contest there is no way i would be able to prove that it works..I used ceil(log2(n)) logic which turned out to be a complete mistake...

Cheers

Can anyone explain how to Div 2 D? I did it greedily where I took the largest prime less than n where n-x >= 2 and then continued to take the smallest prime under that number until I got to 0.

But it seems that way is wrong. Did I miss the correct way entirely?

Two words: Goldbach Conjecture

Yeah I figured that and that's what I was doing so I guess I just had a bug in implementation.

If even (and not 2) the answer should be 2. If odd, then the answer is 3 unless N-2 is prime, in which case the answer is 2. Of course if prime, answer should be 1.

Yeah the one that breaks my code is 2,000,000,000 (it prints 4). Thanks for the help!

I used Goldbach's conjecture, though my solution was hacked.

Did you take care of case where n-2 is prime? Because in this case you can split in numbers: 2, n-2 and the answer would be 2.

I was "lucky" to get hacked by this case and could correct in time!

No, that is the reason. Unfortunately I was hacked a bit late so I didn't manage to fix the solution in time

why less than n? If n itself is a prime number then the answer would be just 1. I didnt get the solution but this might be your mistake.

I checked for that initially (I should've mentioned that I guess) so I don't think that was it.

I included this case too, but still WA

I used this. I hope this passes system tests.

Hint: Every number can be written as sum of 3 or less primes. So check if it is possible to write as 1 or 2 primes, if not it must be 3.

So that's what it was. When I input 2,000,000,000 I got 4 but I couldn't find a set of primes that made it sum in 3. Could I ask how you came up with that? Did you already know that you could express the numbers that way or did you just think about it?

That is not true, 2000000000 can be written as a sum of 2 prime numbers. Following is a list (all of them are primes):

My solution (apparently correct) was based on Goldbach's conjecture. The answer was always going to be 1, 2 or 3.

Yeah that turned out to be what was wrong (my code prints 4 for some numbers).

Yeah it's wrong. There is Goldbach's conjecture which says that every even integer can be expressed as the sum of 2 primes and every odd integer can be expressed as the sum of 3 primes. But in some cases we can use less primes, take it as an simple exercise.

Alright good to know. Thanks for the help!

If the number is prime, return 1 (all prime numbers obviously have a tax value of 1, and this is key to the following algorithm). Otherwise, if it's even, then the Goldbach conjecture follows (every even number >2 is the sum of two primes) and you can return 2. If that is not the case, then check if n-2 is prime. If so, then the number is the sum of two primes (2 and another prime) and you can return 2. Otherwise, it is the sum of a prime and an even number (which itself is the sum of two primes), and you can return 3.

Could you please explain why to check namely n-2? Upd.: Got it, 2 is the only even prime.

Greedy is flawed here. I initially thought it can be solved with greedy. Later, found that it fails if n == p+1, when p is a prime, greedy algo will try to split it as {p,1} but in the description it was given each of split elements should be greater than 1.

Div2 B hack?

Int overflows

Yeah that's what I thought, Thank you.

Any idea of prestest 5 of C ?

Suppose, it is "n = 13", answer is 5.

Can you please draw tournament tree for n=13 ?

You can get it from comment below about n = 8 by adding subtree of 5 leftmost participants to the right.

Sorry, that tree for 8 contradicts main rule of tournament. Please provide tree where that rule holds independent of outcome of each game.

Thanks. It turned out that grid is not known before tournament starts.

I think pretest 5 would have been 8.

Answer for 8 is 4 and not 3 as the Maximum number of matches increases when the total number of participants is a Fibonacci number.

Can someone actually draw a tournament grid (tree) for n=8 ?

1 2

1 3

4 5

1 4

6 7

6 8

1 6

in order of games played.

If player 8 wins 6 in their match, then in the finals it will be second game for him, but 4th game for player 1. That is contradiction with the main condition of problem statement (difference between played games no more than 1)

behold the power of MS paint

Thanks, but this picture contradicts main rule from the problem statement. If player 8 and player 1 go to the final, they will have number of played games differ more than 1.

We are assuming the best case scenario (maximum number of games played), so we can assume that 6 will win in this case.

Organizers cannot assume that someone will win or lose. By definition of the problem they need to construct a tournament grid to match a rule: "two players can play against each other only if the number of games one of them has already played differs by no more than one from the number of games the other one has already played"

No, it is not the problem statement. By definition you should find a maximal possible number of games. You don't create a tournament grid, you only should take the best from all possible scenarios of grid+games.

I copied this from problem statement. Problem statement says that main rule should be applied for the grid (independent of games). But grid above is not valid for the main rule. It can produce sequence of games which contradicts that rule.

But the grid is not fixed. At that point, it does not exists. And it is not obvious what is grid in that problem.

I think the grid is not completely defined at the beginning. This way it makes perfect sense. Anyway, this is not clear at all.

I might be wrong, but I think the statement is a little bit unclear. This tournament grid is not valid in general, right? I mean, player 1 can't face player 8 according to the rules.I didn't realize that we could consider this kind of grid. :(

Why player 1 need to face a player 8? It is a set of games 1 2 / 4 5 / 6 7 / 1 3 / 1 4 / 6 8 / 1 6 / and some other stuff, when games are valid only if all players won all their games before that. In case that drawn on a picture, we have answer 4.

I get the answer, but why not? The statement says the tournament is being organized. Why would someone organize a possibly invalid tournament? You're right, but it could be a little bit more elaborated.

Is tournament grid known before games are starting? Or organizers can just randomly pick players during the tournament. Problem statement is very clear about "tournament grid", so I assume it should be finalized before tournament starts.

It

mustbe the second option. They can pick players along the tournament.Problem statement is very misleading than. It describes the different problem.

I think it's ambiguous. The expected interpretation is not invalid, so as ours.

Loved the idea behind problem D div. 2 (B div. 1).

what idea? i couldn't find the idea behind it! i thought it was greedy but did n;t accept it.

Goldbach conjecture

Is it an idea? If you are not familiar with the conjecture, it is highly unlikely that you will solve the problem.

True. This truthfully was the worst contest that I've participated.

steps to perform well on codeforces contest , steps 3 & 4 are enough in this contest i think :/ ....

UPD : you'll need step 2 also , but you should read all the old problems on spoj ..

I try hacking solution before 5 min of ending contest .why hack is ignored? someone plz answer

One hell of a tricky contest!

How do you solve C? I was so certain my solution was going to pass but it didn't :( I think many others struggled on it as well.

Dp[i] = the minimum number of players needed such that the winner can take part in i games

Wow I didn't think of it as a DP problem. How would you transition between states?

Fibonacci sequence, where dp[0] = 1 and dp[1] = 2.

This was a hacking contest. 1 integer input problems for C,D. "7" and "9" were hack cases for D.

I've attempt to hack div2 A using the following test input, on the codes that did not handle negative indices (for example, 22533346):

However, they output correctly. Is there something I have mistaken?

At first: Thank you for hacking :D.

A few minutes later: Sorry for hacking :(. I don't want to lose my rating (significantly).

Hack-ers aren't cruel at all, what is? Seeing a wrong solution and ignore it! :v

Solved D for the first time! I hope it will pass system test. :)

Dooms Contest :/ GG Rating

I wonder how this guy might be feeling after hacking 5 solutions for D and getting hacked back by one of those users.

awful contest!!! especially for problem div2 D , it needs to know Goldbach's conjecture. Is it related to problem solving skill?!???

I do think that Goldbach's conjecture is a kind of common sense instead of solving skill.

I don't know about him but bvd is very relieved after getting revenge I think.

I'm sorry to tell, but truth should not be concealed : Awful problems on C and D (they don't deserve their intended points) :(

Couldn't agree more.

I agree. Almost no algorithmic skills were needed to solve these two.

Actually contests require problem-solving skill, not only popular algorithms and data structures :D

I think C is ok. It's something you can figure out with a piece of paper, D is just about whether you've encountered the conjecture or are googling during the contest.

What's wrong with C?

I got disappointed with my result in this contest. I am pretty sure I have become better in algorithms as I usually practice in TopCoder. According to the new rating in Codeforces, I got moved to Div2. Then, I decided to participate in this contest to reach div1 here, too. Generally, I have difficulty with these kinds of problems since instead of thinking about algorithms, I am forced to find corner cases. I don't really like these kinds of problems though I have the great respect for the author.

Regarding other comments, I found out that the Problem C has been available on SPOJ. I think albertg does not know anything about Self-plagiarism.

i used this code for problem C i got WA in pretest 7 any idea ?

while(n>1){ if((n%2)==1){ans++;}; ans++;

n>>=1; }

For Problem C I think it's a fibonacci problem.

Could u please explain it ?

Yes I can.

We define f(n) to be the minimum number of players required such that the winner can play n games at most.

So the ideal situation(to make the number of players minimum) is that the last game the winner played is with another player who played n — 2 games already(since the winner played n — 1 games at this point).

So we have: f(n) = f(n — 1) + f(n — 2)

then the final answer is just the maximum number m which satisfied f(m) <= tot_number_of_players.

else A&B(div1) problems were fun.

thanks.

Yes, both A and B are terrible. I wouldn't recommend them to anyone of any level. Maybe if the author used only one of them it would have been suited for Div.1 A

My friend just told me that he solved C and D (Div.2) by finding other peoples' codes on ideone. This is so unfair -_-

If it is matched with some other code that submissions will be skipped :)

If people are smart enough to find codes on ideone, they will definitely modify it as they know about this dirty trick. I was surprised to see the rising submissions for C and D.

Report him.

Since when did this start happening on codeforces? Same author, Same problem.

How is this even possible ? is the author foolish or something ? How can he repost one of his own problems ? Lol

the contest should be made unrated . Div1 A was copied and Div 1B was google-able :(

kingofnumbers was right in his blog for which he faced so much criticism. The author of this round did not even care to change the title of the problem. -_- People cheating from ideone and authors making one problem googleable and one problem exactly same(again googleable). Bye bye albertg. Hope this second round is your last round.

this not convincing reason to make unrated this mean that they have to make all previous contests unrated

there he is ^

lol i'm such a shitty friend

who are you -_- I don't even know you -_-

Bro, if you want people to believe you, at least don't make any more lies that I can easily prove wrong

Come on, you gotta be smarter than this!

LOL :v

So you want to cheat from ideone and then fight for whether the reason is convincing or not to make the round unrated?

I didn't cheated you can confirm from my status -_-

Did anyone used prime numbers to solve D?

Yeah (D2 D was the same as D1 B). The key insight is the Goldbach conjecture (any even number >2 is the sum of two primes).

Yes, the key is Goldbach Conjecture

Yes, I am

Problem D/B be like:

haha thats funny.

problem D can anybody google it

this is unfair

Yeah, no problem is fare. Or did you mean fair?

Such a troll problem,simply not fair..

in problem C:

"Don't miss the unusual constraint for k."

is just a lie :|

Hope I can jump to div1 for the second time.

Div.1 A I wonder how many people could google this http://www.spoj.com/problems/TENNIS1/ during the round.... -_-

I've actually learned something new from this contest, thanks!

1) Google exactly the problem statement because apparently...

you might get lucky(same author, same statement)2) After #1 is done...

you know what to do next3) If everything fails, try checking other people's code on ideone.com because apparently...

well, you got the ideaGo Googleforces!

https://www.quora.com/What-is-the-best-way-to-solve-SPOJ-problem-code-TENNIS1

HELLO FROM 2K15 BOYZ

this contest reminds me of april fools day contest :D :D

Actually April fools day contest is more interesting than this contest.

Is it fair to repeat your already existing problems? albertg

http://www.spoj.com/problems/TENNIS1/

Vah beta :P

Can you please translate?

mdakeklol

I don't want to sound rude or anything, but this contest was very bad and in my opinion should be unrated, and I'm not saying that just because I participated badly. The main reason is that problem C was on SPOJ — link and was posted there by the author of this contest! Anyone could just google it. Also D was an ugly problem, and the only way to solve it was to either somehow already known about Goldbach's conjecture, which is not all that well-known, to search it on google which shouldn't be a way to solve a problem, or to guess it, which would be just luck.

For D, If someone is able to deduce that answer will equal to minimum number of primes whose sum is equal to n then google search will take you to Goldbach's conjecture. So I feel it's ok. BTW it was similar to Dima and Lisa which was blocked during contest.

Deducing that was easy for a D level problem, the hard part of the problem was finding the number of primes, so 90% of the problem was solved through google

Are we supposed to be using Google during contests?

I didn't know about Goldbach's conjecture, so I bruteforced the first few answers and OEISed them. Still bad though

Div 2 D is just the same with #324 div 2 D. (http://codeforces.com/contest/584/problem/D)

In this round's problem you have to prove that you should only pick primes. Minor difference, but at least something

While it's true that the author may have used one of his own problems and this was a mistake, it's important not to consider the entire contest as bad just because one or two tasks were not optimal. It takes a lot of time to prepare these contests, especially for both divisions, so at the end of the day, we are all in the author's debt, not the other way around.

Although I didn't participate but we aren't talking about optimality here. You were an author before and you know it's not an easy task to come with the problems but you also know that it's a huge responsibility, in case it's a dup problem we can excuse him assuming he didn't know it existed but here he was the author and it had been there for 2 years.

There was no problem solving in Div2 D also just using a well know theorem.

Not really. Authors are paid to create problems for a contest, and if they are reusing one of their older public problems, they are basically cheating.

make it unrated is the most stupid thing CF can do

I don't participate in one contest and the freaking problem D can be done with the Goldbach Conjecture , fml.. They should make it unrated, this isn't fair!

One of the problems was a straight copy, and the other one was a google search problem. Making this round rated cheapens the value of one's rating.

In Div1-D, is it enough to check for each relation if it is contained in exactly one valid permutation?

I solved using the following:

Let

Abe such matrix thatA_{i, j}= 1 ifpermutation_{i}can equal j, and 0 otherwise.We know that the number of all valid permutation is a permanent of

A, and in . So we have to check for some queries (x,y) thatM_{x, y}= 1 (in , hereM_{x, y}is the respective minor). It's known thatM_{x, y}=A^{ - 1}_{y, x}, so we just calculateA^{ - 1}forn^{3}/ 32 and win.UPD:andA^{ - 1}exists since .Nice solution!

I haven't got the only thing about

M_{x, y}=A^{ - 1}_{y, x}. Could you please clarify or give me a link or whatever.https://en.wikipedia.org/wiki/Minor_(linear_algebra)#Inverse_of_a_matrix

is contest rated?

now it's a good question

Actually, problem D is the direct application of Goldbach's conjecture. I think this is the 'ABC' in the world of math/number theory.

I remembered that I've learned this when I was really really young, maybe the time when I was a primary student or a middle school student.

Even though, I failed to come up with this quickly in the contest and tried several wrong ideas, wasting my time.

From the view of problem setting, I don't think this problem (as well as C) is good. I think people don't want to train their

knowledgeof commen sense in problems like D in div2. These problems can be better if they engage more thoughts. As for me, I enjoy harder D, even if I can't solve it.But from the view of a problem solver, I think div2D is still good problem. It reminds us that we should not forget the most fundamental thing when we are solving hard problems. If tourist competed in this round, I think he would solve div2D easily. We as problem solver should think of how we can deal with such problems quickly under adverse condition instead of complaining about it. Life is not always fair, right?

Anyway, thanks for the problem setters. It is not easy to prepare a contest. And somehow, it is not easy to come up with easy problems. Hope the next round will be better and I can become purple. :)

Regarding the repeated problem issue, if I were in charge I would zero out all results from 1A/2C but not unrate the entire contest. The problem lies exclusively in a single question, and yes it is a major problem, but it's not like all of the questions leaked or anything.

Also, some here are saying 1B/2D was "unfair"; I have to say I personally disagree, with the caveat that maybe this wasn't the best problem to have in Div 2 because of this. Yes, 1B/2D relied on some knowledge/research -- but in the end, what harder problem doesn't to some extent? At the ICPC Mid-Central Regionals, one of the hardest problems anyone solved (and, in the end, the one that put my team over the top to go to Worlds) seemed intractable -- until, that is, I realized that the problem of deciding whether a given power level is possible reduces to 2-SAT. Without knowledge of 2-SAT and its reduction to the strongly connected components problem, this problem would be impossible to solve. In addition, most geometry problems have some innate knowledge requirement in order to reach the key insights involved. Maybe this problem was a bit irksome because its knowledge difficulty was above its algorithmic/implementation difficulty, but overall I don't think it was a bad problem (though, again, maybe it should have been replaced with something else for div 2).

But some people spent most of the time thinking about it, wasting the time which they could've spent searching on google D's solution

'some people' doesn't mean only you.

What about someone who had no idea about the repetition of problem C and solved it by himself giving maximum of his contest time? Will it be fair to zero out his accepted code?

Look at the code of winner of div2 round. Who uses DPDPDP as a variable? I wish there was no find and replace option built.

I guess it turns out that KSL who was previously first place cheated. Maybe people downvoted you a little too early, because there definitely was something fishy about that guy.

blokes ya just have butthurt cuz you didnt solve these problems. great contest, well done.

And it doesn't look like you solved anything at all ;)

Hi. Can anyone help me with div.2 B? My code works fine on my computer, including the first test case. But on codeforces the output is -2 on first test. http://codeforces.com/contest/735/submission/22553933

I think you algorithm is incorrect to begin with. The correct answer is taking the first min(n1,n2) to the smaller set and the next max(n1,n2) to the larger set.

Thank you, but I swap the values if n1 > n2: "if(n1 > n2) n1^=n2^=n1^=n2;"

change long double to double

Thank you very much! But why is it so?

You shouldn't have used long double. Make the sums with long long and then cast to double when printing... Got AC here with it: http://codeforces.com/contest/735/submission/22558151 :/

Could you also tell me why long double didn't work? edit: I googled it.

I think there is a problem with codeforces and long doubles. I also submitted with long doubles and had WA in test 1. Better use double.

Well I don't know the actual size/range of long double but it seems like some kind of weird overflow (? overflow with sum 6?? lul wut??)

Looked it up and on wikipedia they basically say it's unspecified so I guess it's better not to use it on contests... I recommend always using long long and cast, works well for me :s

The problem is with printf and not long doubles!

In my opinion, tests for problem D are not enought. Some accepted solutions are checked only prime numbers to 1e5. I think there are no complete test cases.

I mean you are right!

Why do people use Google during the contest in the first place? And if one uses the argument "everyone else is doing it" then how different is that person from all the other googlers?

Correct me if I am wrong, but the purpose of these contests is to hone one's skills. Although the problem setter made a mistake posting one of his own problems, take into consideration that the author took his time to put this contest together.

Without using Google, I find Div. 1 A&B very reasonable. It definitely took me more time to come up with Div. 1 A but I came up with that so why should I care that someone looked it up online. I didn't even know about Goldbach's conjecture but managed to solve B with some kind of brute force. It seems that the problems were more or less balanced if not for the googlers. But googlers are googlers, why should one compare himself or herself to them.

Agreed. Your non-Goldbach's conjecture version makes me feel better about that problem.

There's never going to be a way to stop people from cheating anyways.

I spent most of time working on problem D... There seemed to be a fancy conclusion as the solution to problem D, but I hadn't got it. Umm... I should improve the level of knowledge.

why my code got WA in test 11 Div2B

submission

I think overflow in sum1 and sum2 might be the problem here. Try using long instead of int.

yes it was the overflow i wish i did it before :(

Ah well, you won't do it next time :D

I got my rate down :(

How to solve Div 2 E / Div 1 C?

Does anyone know why the problem C of Div.1 use unusual constraint for k?

There is a solution with O (2^k * n).

We iterate over the vertexes, which will be painted (this vertex is removed no more than k from the root), brute over her mask and update dp.

I cannot understand it still. Q_Q

Personally, I don't see why it's considered unusual?

I say it is unusual because the statement say that. And I cannot think out one solution using this constraint. My solution can be done in O(n^3). In order to use the constraint, I take some time in thinking it bug I give up in the final.

There is

O(n·k^{4}) solution. Dynamic programming with`dp[2][n][k]`

— the number of ways to fill a subtree that either the topmost black vertex is at some height or the topmost non-satisfied white vertex is at some height.Just googling round)

thanks the author for ruining my 2 hours:/

i should have participated in HR ICPC contest :(

All problems there were OLD HR problems :) People Googled/Searched HR archive and submitted :) So, by your logic, you would have complained about HR contest too!

So the best solution for you would have been shutting down your system for the time being :D

It's better to stop complaining and learn :)

If you cared about improving you wouldn't say that (unless ofc you have solved all the problems on hr)

waiting for Edtutorial just to give you your deserved downvote

Wow, they actually made it rated.

Did anyone take advantage of a problem div1A being googlable? There is no editorial or any comments under that problem. I've just tried to submit a solution there and got ERROR — so I guess it wasn't possible to test one's solution by submitting a problem there. The only possible issue I see is that someone may have already read that statement. There is a tag "hidden" though and maybe it means that a problem isn't showed in the global list of problems. Still, maybe someone managed to find it in some way before, but it doesn't look like a likely scenario.

Uh the solution is on quora.

Erm... https://www.quora.com/What-is-the-best-way-to-solve-SPOJ-problem-code-TENNIS1

This author should be banned permanently for giving the same problem twice. There should be no reasonable explanation for such behaviour. Giving one more problem on "Goldbach's conjecture" totally sucks as well. This round is ridiculous.

Yeah, also take a look at his other problem on SPOJ. Not an exact copy paste as in Div1-A, but it requires Goldbach's conjecture. I wonder why he would need to copy-paste and/or re-use ideas from his own problems. This is utterly absurd.

I can understand giving a problem which appeared before, you might not know about it, it happens from time to time. But when it's

YOUR OWNproblem...I didn't know that a solution is described somewhere. Ok, then it's a bad situation.

Codeforces really wants me in div1 :)

well, the round is rated for both division, same shity problem for the same author and with the same statement

everything is fine , don't you think that at least we own you an apology ?

Cmon, problem C div 2 was nice. The only mistake imo was to copy the exactly same statement.

THIS IS RIDICULOUS!!

Most contestants are complaining that problem A Div.1 is repeated with the same statement and the same author & problem B Div.1 can be googled easily and all we can get is IGNORANCE..

I downvoted the contest, it should be UNRATED!!

Yes, the ratings have been published already mate. It is RATED.

This contest is just terrific!

Wow, another account standing in the "Ban queue"! :D

you didn't do this round, why you are so emotional now? My dear "Trump"

now , i think that Edvard is the only Armenian author in codeforces . :3

Just for fun: problem with (a bit) similar idea to D2-D / D1-B: https://community.topcoder.com/stat?c=problem_statement&pm=11607

I wonder if albertg will write an editorial for Div1/A or he'll just post the Quora link.

Let's make the contest editorial post the most downvoted post on codeforces....

I'm poor in math; Then I got a 75 ratings decreasing..; Horrible math....; However,This is a Nice round; Thank you! (I'm poor in ENGLISH too.TAT)

I thought it would be unrated, maybe I will back to blue when I wake up tomorrow ...

I like mathematics so I think C and D were good problems. Maybe it was too easy to copy them from google but beside that they were interesting and challenging.