Soon you are lucky to participate in Codeforces Round #284, and problems have been prepared by Vitaly Gridnev (gridnevvvit), Ilya Los (IlyaLos), Danil Sagunov (danilka.pro).

We want to thank Max Akhmedov (Zlobober) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

Scoring system will be dynamic. Problems will be arranged in ascending expected difficulty order.

Round finished, congratulations to winners!

Div1:

Div2:

Good luck!

Just why on Christmas Eve?

Check out: http://polishchristmasguide.com

Definitely to make you miss the round!

Good luck to everyone :)

Pleas accept my apology, But is the women in the picture you or someone else?

Yes. Why such strange questions ?

Well you see, I really didn't thought that there is/are pretty women(s) who like coding and codeforces and your actually the first one I see.

public flirting? XD

Excuse you ?

Bite me, does that count as flirting? I even don't know how sooooorrrry is pronounced and I talked with the maximum officiality.

tabreer el 7ak

What??

I guess, users in cf like to see the comments which have low cont. and give them dislikes, cause that comment was +5 and now it's -12.

.

sooooorrrry is not the girl she claims to be in the picture. See this: http://goo.gl/5h1gYJ — sad, everyone was so excited.

- ... you or someone else?- Yes.

Why do you think that she claims to be on the picture? Don't you know about "or" operator?

[

Fake beautiful profile picture] =UPVOTE!:)Excuse you ?

Come on people, Same comment +3 !! :|

Why are you still commenting and going down in contribution? :3

Because, still he has +16 contribution and the girl stolen his heart! :)

I will just leave this here: http://codeforces.com/blog/entry/10034#comment-155087

Exactly the same situation as year before or even worse, because year ago time was not that bad, but 19:30 (17:30 in Poland) it's definitely too late. I think you shouldn't expect many Polish coders tomorrow missing one in a year feast and ignoring whole family which gathered in their home.

This. I registered thinking that I have no idea whether I'll find the time to participate...

although it's a chance for a very good (absolute) place... so much win.

Also, working name of this contest: basement dweller check.

Don't you think that in all countries except Western Europe and US/Canada nobody cares about celebrating Christmas because New Year is our national holiday? We will not miss you today, take it easy.

New Year is only the main holiday in Russia (and countries with similar traditions), because Julian and Gregorian calendar. It kind of explains why there's a contest on this date, but the argument still stands for most of the world, Central Europe included.

Dude watch yourself when leaving a comment in a site full of Russian.

I also find completely unacceptable that so many contests on Codeforces take place on Fridays after the sunset or on Saturdays before the sunset.

I celebrate my birthday today. And I hope, this round will be a gift from CodeForces for me!

GL && HF!:)Happy Birthday!

Thanks a lot.

This is a scene that you won't see a lot...

I laughed at this for hours :D

I am still laughing. :P

Have you notice the third position? Check this

:D

oh,it must be a fun for chritmas!

anyone noticed this. SAKT :p leave dreammoon alone :p

i am new in codeforces i want to see problems in codeforces round #284

wait for 15 hours and you can see those.

Your bets — will dreamoon_love_AA win div2 tomorrow? :)

We 2nd division participants will make sure he doesn't

Haha, div2 guys defeating international grandmaster sounded pretty hilarious, but dreamoon seems to be taking this contest seriously, cause he solved 3 problems, but you are on better position now, so I see that your words were pretty serious :D

Maybe he will cha to get -inf score,and integer overflow to +inf score and get the first place

You shouldn't be drinking so much during christmas .

if the hack points is defined by short, he can do it... if it is int..I think codeforces may break down.... if long long...the internet of the world may break down..What a DDOS!

I bet 100 Quatloos that he won't.

Is it because you are gonna participate with a fake account?

No, it wouldn't probably change much and I'm most likely not going to participate at all.

Is sorry_dreamoon participating in your place?

btw,can you imagine that oneday tourist's rating overflow to -inf and worse's rating overflow to +inf?

He would have to take part in atleast 58040011 contests assuming he keeps getting the first rank and the first rank fetches him a gain of 37 points like it happened for his previous contest .

Maybe He/She is challenging worse !

Merry Christmas to everyone !

Good luck to everybody!

dis like me plz

Your wish will be granted

Try harder!!!

Hi!

thanks gridnevvvit !

your last contest had vary nice problem (Codeforces Round #275):) thanks :)

Hope for high rating.

why do you hope it when you always make another account? seriously dude tell me how many accounts do you have? I only know about 4 of them I guess : tourleader , Majid , contest1234 and delairer. The funny fact is in all of them your contribution is negative :)

I think guys like you are the reason he has a low contribution :)))

Can you give me evidence for this letter?

"I guess : choghok , clashofclans , contest1234 and delairer." he guesses

Of course I guess, cause there might be more :)

Well i thought you meant that you "guessed" these are his accounts my bad

What do you mean ?

contest1234 => last online 3 weeks ago!

delairer => Last visit: 5 months ago!

tourleader => last online 3 weeks ago!

Isn't that obvious? you make an account give some contests with it and then you just leave it by,

It is against the rules and i never do it!

I don't think Majid and contest1234 are the same . You can check out their contest history . There are 2 contests in common (273 and 277.5) and they solved different number of problems in both .

Christmas Round && My first CF Round ... Sounds nice ;-) But the time is not convenient for Coders at GMT+8 ... such as China. It is 00:30 to 02:30 , which means we might be very sleepy ...

I am firstly joining it too!I am also a chinese.

Good Luck to you two!

LOOK your headpicture ，and I guess you are a Chinese。

"head picture" = =

i agree with you. but the headpicture... er maybe who is not chinese can't understand you.

Thanks!

ok ok !

I'm loser!you are winner !

worse is win,

dreamoon : GaMeOVeR

Merry Christmas to all :)

All the best for the Round #284.

Merry Christmas! GL && HF!

Hope to gain some rating points this Christmas ;)

I hope all Specialist be candidate master (!) and all Expert be master (!!) and dreamoon_love_AA be grand master !

poor pupils and newbies then ...

Well don't hope cause he is challenging worse so he is going to become specialist or or if he wins the challenge maybe pupil. :)

He isn't challenging worse he is trying to get first place which he didn't achieve in div1 so he's trying it in div 2

Merry Christmas!

Merry Christmas

Scoring system will be Dynamic , don't know is it good for me or not ! My curious mind want to know what others think ?

Dynamic Scoring.

`while(true) System.out.println("NOOOOOOOOOOOOOOOOOOOO");`

TL, mate

Hope for much [pure] math

(And strong pretests!!)

Eh, well it is a matter of opinion. I personally believe that hacking creates more suspense, especially right after you try to hack someone.

We can see about dynamic scoring system here.

Seems like tourist didn't register for Div.1 .Could it be that he made a Div.2 account to beat dreamoon_love_AA ? By the way, good luck to everyone, and Merry Christmas !

sorry_dreamoon...?

sorry_dreamoon uses Java 7. So, I don't think it can be tourist.

tourist also uses Java 7 click here

I think he is Petr

:) Really nice... poor dreamoon

Let's Pa Pa Pa tonight. :D

one more chinese say something chinglish o(╯□╰)o

Many Thanks to you <3

GL HF

I have seen the problems and have decided to not participate. I don't see myself solving any problem other than A and B and that's not good enough for me. Maybe, I will have better luck next time.

GG.

sorry_dreamoon is now at first place! dreamoon_love_AA's only chance now is to solve E quickly and find lots of hacks!

Hmmm ... dreamoon_love_AA is in my room ... I can make wrong submissions so that he can hack them and get to the top ... interesting idea ... ;) :D

In first 2 problems(div.2) the limits of numbers were to low...

so all coders will accept them by terrible codes...

It's the reason of less hacks than other contests...

In my opinion, brute force solutions are quite prone to errors

dreamoon_love_AA has solved all 5 problems now. He needs to find 5 hacks to get to first place. He has currently locked C. I think that is a very good choice.

How hard it is!!! Poor rating...

contest is not attractive :( without Top rank in Div2 :)

interesting competition between sorry_dreamoon and dreamoon

I just want to know who is sorry_dreamoon :P Comment guesses :D

someone from top 10

yeah he seemed highly confident when saying "we will see it soon".

It's some evidences... :D http://codeforces.com/comments/with/sorry_dreamoon

Kinda obvious hehe http://codeforces.com/blog/entry/15336#comment-202784

My guess is that he is a person who can write code in Java and some International Grandmaster must be helping him during the contest to solve the problems .

Highlight of this match: will sorry_dreamoon beat dreamoon_love_AA? There's probably no way for hacks to change the current situation, but there are still pretests! What if one (or both) fail something? Resubmissions are also possible...

Find out next time, on Dragon Ball Z!

It ended...

they accept all of problems surly...

No, it hasn't ended yet. There are 10 minutes left.

sorry_dreamoon can get banned for double-account (surely he is from div1) and dreamoon_love_AA will be top1 :D

Can you prove it is a double account?

it is just like proving 2+2=4

liymsheep on the lines of worse

Doing so many unsuccessful hacks, so the first three contestants will have dreamoon in their handle name :D

It's such sad story...after letting the top 3 places to dreamoons, liymsheep fails D him/herself and becomes 10th instead of 4th :(

What a Christmas gift!!!

It was a nice contest! easy problems A & B and normal Problem C!

How to solve div. 1 498B - Name That Tune and 498C - Array and Operations?

If I'm not mistaken, Array and Operations was a maximum matching problem (so maxflow). You separate each number into its primes, and then built a tree based on that, and find the maxflow.

Wait really? This is what I did (hope it doesn't time out), but since it doesn't use the i+j is odd condition (AFAIK), I was assuming it wasn't the intended solution...

@waterfalls it should be using the i+j condition...

Well some people did it in <=7 minutes, so this may be a harder way to solve it.

The i + j odd condition just enforces a bipartite graph. I don't think it was really necessary, but maybe there was a simpler solution if you took advantage of that.

How is the tree built?

What I did is the following:

Make a supersource and supersink.

Make two*n nodes, one in-node and one out-node for each number in A.

Connect the supersource to all the in-nodes, and the out-nodes to the supersink, with capacities equal to the number of factors of the prime p being considered.

Connect, for each pair, each in-node to each out-node, with capacity equal to the number of factors of p the number in A shares.

Find the maxflow of this.

Divide by 2 (everything is counted twice)

Nooooo WA on test #26 -> took like a minute to fix it... (for those who are wondering, with big primes must run maxflow again instead of just counting pairs that work and removing, which I did because I incorrectly thought since each could only have one of a prime, it would be ok)

Poor dreamoon_love_AA :D

Well, he only needs to lose 89 rating points and he can try again. At the same time, sorry_dreamoon has to lose 85 rating points to challenge dreamoon another time. Moreover, if this battle continues for a longer time and sorry_dreamoon wins all the matches, his rating will get higher than rating of dreamoon_love_AA, so he will also have to become more efficient in losing his rating.

I asked dreamoon_love_AA and he said that he will not try it again. As he said,

It's just like you can participate World Final only twice :Pdreamoon_love_AA wants to have a div 2 win to his account, but sorry_dreamoon does not. So sorry_dreamoon does not need to lose rating: He can just create new accounts.

No, he can't. It's against rules :).

So you think it is his first and only account?

Div. 2 Problem C. I thought that answer is number of lines between two points. Where i am wrong?

You are right, watch for overflow though.

You are right too. I'm using double instead long double... what a shame...

You are wrong now. Use integer arithmetics only, avoid double or long double.

Actually, double will pass; I just tested it. 9262061

Unfortunately I made some other stupid mistake which led it to fail on system test :(

My solution using double passed. The fact that the points are only integers and that the house and university cannot be on the roads helps :)

Epic Standings . Sorry Dreamoon

So sad

Got D solution produced correct answer for sample case after the deadline 2 seconds !!!!

I use 60 segment trees (for all the possible modulo).

UPD: that code got Accepted T_T. Life is so harsh.

SQRT decomposition is pretty bad for this problem :(

Is this contest too?

I think that sorry_dreamoon is another account of dreamoon_love_AA

And dreamoon_fan too. He registered 4 hours ago and sorry_dreamoon 7 hours ago.

It is a bit annoying that there are a little hacks int the 2nd division

Nice problem thanks gridnevvvit!

Happy Christmas Everyone!!

Especially to dreamoon... Awesome scoreline XD

The only fail of the contest factor of ax!

The most fun part of it is I asked once about it and they gave me no comments. Anyone else had the same problem?

How to solve DIV 2 D?

Look at my submission 9258135 , I forgot to remove the "freopen", surprisingly my code outputs zero instead of getting RTE on test 1. and unfortunately because the answer of first test is zero I got WA on test 2 making me lose 50 points.

Next time use "define ONLINE_JUDGE".

but I want to know why I didn't get RTE , I used to think that it will make RTE so it will not decrease 50 points.

I got 'judgement failed' on my submission for Div1 B: http://codeforces.com/contest/498/submission/9246565. What does this mean?

Contest in hack is not !!!

Yes.

Mery Christmas :) Good problems!

But Today, I'm not lucky (I've been seen dinosaurs on chrome :D)

Same thing happened with me, I know how it feels when you finish both the problems in 10 mins and can't submit till 20 mins due those dinosaurs, btw Merry Christmas :)

Poor dreamoon_love_AA, he still can't win a codeforces round...

sorry_dreamoon named all his class as Dreamoon... maybe he does love dreamoon_love_AA...

he/she will be in div.1 for next contest

I dont know

dreamoonBut It's for him/her (...)I hope best ranks in

goodbye 2014for you :DMerry Christmas dreamoon_love_AA!

http://codeforces.com/contest/499/submission/9254466

can someone point out why its giving wrong answer?

use long long intstead of long int

http://codeforces.com/contest/499/submission/9259776 :D

You must use long long not long :D

I noticed it later, cost me the whole contest.

I have a gut feeling that dreamoon_love_AA will again try to return to Div. 2 in the next contest.

dreamoon_fan is also there, is it possible to change your handle??

is tourist sorry_dreamoon ? Because sorry_dreamoon finished the contest in 48 minutes.

Take a look at top of div1 standings. There are quite a lot of contestants who did div1A-div1C in less than 48 minutes, so it is clear that you don't need to be a tourist to solve div2 problemset in 48 minutes (even if you still need to be a strong contestant to achieve this).

And the codes were is JAVA, i dont think tourist would have done that, even though thats not hard for a redcoder!!

Too sad.

I think sharing Personal talks publicly is not cool.

pls,plz,pls,plz

dis like me plz

As you say sir, DONE :D

Is dreamoon_love_AA girl or boy?

boy

Be to Che

A little bug in my submission for problem A div.1 ...

I want to kill myself now :D

Rating Updated.

Congratulations...

sorry_dreamoon . Please can you reveal yourself .

After 42 contests I finally reached Div1. What a great Christmas gift! :)

congratulations, my friend!

Div.1 B is really hard to understand for me... Sad story...

The amount of dreamoon_love_AA is too damn high

Div2 only top 3 ... Why? because... dreamoon :)

Many O(nT) solutions for Div.1 B get TLE...I think the time limit is a bit tight, or maybe there is a solution faster than O(nT)?

That's indeed the case, TL is quite evil IMO. Many solutions encounter problem with double performance for small numbers (it is well-known that double arithmetic is much slower if numbers are very small); in this particular problem the issue results in ~2 times slower running time. E.g.: this 9261764 gets TLE, while this one 9261771 (the same with rounding numbers below 1E-200 to 0) — AC in 483ms. Moreover, compiler choice matters; the same solution in Java 7: 9261791 (I guess it's because the startup time of Java VM is accounted to TL).

In general, many failed B's were due to TLE for random reasons, and the actual running time was borderline. Increasing TL to 2s would resolve this. So I wonder why the TL was set to 1s, what wrong solution did jury try to kill? The only TLE-incorrect solution I can think of is

O(nT^{2}), which would run forever. It's sad that even good problemsetters continue to set TL without thinking, randomly killing many correct solutions as a result.Apparently the jury was trying to kill

O(n*T^{2}) heuristics with breaks.They did quite a good job. For example: http://codeforces.com/contest/498/submission/9260678

I am not sure how much time it takes to pass the failed tests, but the author of the code believes it is close to pass.

There are still some

O(n*T^{2}) solutions that passed though: http://codeforces.com/contest/498/submission/9250130.Can anyone explain me Div 2 E which involves Max. Flow? I was trying the greedy approach, which is wrong. (Realized after system test. :P)

Here's what I did, which isn't the same as the editorial, but I find it easier to understand. (I got WA26 due to a small bug, but got it AC after) EDIT: See here for a more detailed explanation.

For each prime that divides some a[i], we make a flow graph and find the number of operations that can be made using only that prime. The first thing to notice is that it is best if v is always a prime, since otherwise that operation could be split into operations using v's prime factors. Then,

Make a supersource and supersink.

Make two*n nodes, one in-node and one out-node for each number in a.

Connect the supersource to all the in-nodes, and the out-nodes to the supersink, with capacities equal to the number of factors of the prime p being considered.

Connect, for each pair i,j given, each in-node to each out-node, with capacity equal to the number of factors of p the number in A shares.

Find the maxflow of this. A flow from an in-node to an out-node corresponds to using some prime factors of the two numbers the nodes represent in an operation.

Divide by 2 (everything is counted twice)

I'm not sure how clear this is, so feel free to ask questions (particularly on the modelling which I didn't really explain.

Actually, there is no need to make 2n nodes. According to the statement, the sum of each pair is odd, so one of the numbers is odd and another is even. That's why the given graph is bipartite, and more than that, the first part contains the numbers with odd indices, and another — with even ones. So we can make edges from superstore to the ventices with odd indices, from the vertices with even indices to supersink and the given edges, directed from odd to even vertex.

Ah ok that's why i+j is always odd... (I did think if there was a way to split the nodes to avoid an in and out node, but came up with nothing)

Why would such a condition be added if it only helped a little bit with implementation (if at all, I'm not sure it would have been easier with the cases involved)? Was there another solution that used it more?

Without having i + j is odd. Graph might had triangles. That's why one can not use bipartite matching anymore.

How does your flow solution ensure that if we are sending k flow down (i in) -> (j out), we are also sending exactly k flow down (j in) -> (i out)? Surely for any feasible solution they should be equal, otherwise you can do crazy things with e.g. a triangle graph and get an answer that is actually impossible.

For example, your accepted code fails with this non-bipartite-graph test case:

On a bipartite graph this does not matter because your flow graph is essentially just two bipartite graphs that are equivalent (i.e. even positions on one side, odd positions on the other side, edges represent number of prime factor p shared), with one being the mirror of the other, so you are guaranteed to get 2X the correct answer.

If it's not a bipartite graph, then the problem essentially reduces to maximum matching on a general graph, which is not solved with flow as far as I know. See 9250097 for example on solving it for the general case.

Hey waterfalls, I didn't quite understand the graph making part. Let me ask some clarifications.

For each prime that divides some a[i], we make a flow graph and find the number of operations that can be made using only that prime.Connect the supersource to all the in-nodes, and the out-nodes to the supersink, with capacities equal to the number of factors of the prime p being considered.I didn't understand those two parts properly. Would you please explain with a sample test case?

Thank you.

Here is what I did:

(The number of p in A[i] means the number of times A[i] can be divided by p)

Make a source and sink node.

Add a directed edge from source to all nodes with odd index i. The capacity of each edge is the number of p in A[i].

Add a directed edge from sink with all nodes to even index i. The capacity of each edge is the number of p in A[i].

For each good pair (i,j), add an edge from an odd indexed node to even indexed node. (If the good pair is (3,4), add an edge from 3 to 4. If (6,7), add an edge from 7 to 6) The capacity of each edge is the number of p in gcd(A[i],A[j])

Although some of my reasoning was wrong, as ikbal pointed out above, I'll try to explain this (if HidenoriS didn't already clear it up)

Basically, you want each operation to be made on a prime. Then, split the operations into the different primes to perform them on. This results, for each prime, in a different (but similar) problem:

Given

b[i] for 1 ≤i≤n, (hereb[i] is the number of factors of the prime ina[i]) andmgood pairs, find the number of operations you can do where each operation consists ofsubtractingthe same number from both numbers in the pair.For this, use flow. Make a supersource and supersink, and (I'll use the even-odd thing now) connect the supersource to the odds, and the evens to the supersink. To ensure the flow is limited by the factors of

p(which is justb[i]), make the capacity of the flow from any node representingito the supersource/supersink equal tob[i]. Then, for each good pair connect the two nodes, with capacity equal to the minimum of the numbers of factors ofp(which is (min(b[i],b[j])).Running maxflow on this from the supersource to the supersink gives the number of operations that can be made with a certain prime

p, and repeat for all primes.Sample:

`3 2`

`8 12 8`

`1 2`

`2 3`

Here,

a= {8, 12, 8}. Consider the primep= 2. The resultingb= {3, 2, 3} (the number of factors of 2). Now, the flow graph looks like this:Thanks both of you! It is totally clear now. :)

Where are the editorial ?? :/

Here.

When could I get the editorial for 284 div 2?

^ There

.

You can get partial scores on Hackerrank for test cases you got correct. But in Codeforces and Topcoder there is no partial scoring system.