### gridnevvvit's blog

By gridnevvvit, 8 years ago, translation,

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:

Editorial

Good luck!

• +296

 » 8 years ago, # | ← Rev. 3 →   +27 Just why on Christmas Eve?Check out: http://polishchristmasguide.com
•  » » 8 years ago, # ^ |   +131 Definitely to make you miss the round!
•  » » 8 years ago, # ^ |   +36 Good luck to everyone :)
•  » » » 8 years ago, # ^ |   +25 Pleas accept my apology, But is the women in the picture you or someone else?
•  » » » » 8 years ago, # ^ |   +52 Yes. Why such strange questions ?
•  » » » » » 8 years ago, # ^ |   -57 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.
•  » » » » » » 8 years ago, # ^ |   +74 public flirting? XD
•  » » » » » » » 8 years ago, # ^ |   +31 Excuse you ?
•  » » » » » » » 8 years ago, # ^ |   -18 Bite me, does that count as flirting? I even don't know how sooooorrrry is pronounced and I talked with the maximum officiality.
•  » » » » » » » » 8 years ago, # ^ |   -38 tabreer el 7ak
•  » » » » » » » » » 8 years ago, # ^ |   -11 What??
•  » » » » » » 8 years ago, # ^ |   -31 batal 7ak ala 7okaha_tetla3_banfsegey
•  » » » » » » 8 years ago, # ^ |   -32 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.
•  » » » » » » 8 years ago, # ^ | ← Rev. 2 →   +54 .
•  » » » » » » 8 years ago, # ^ |   +35
•  » » » » » » 8 years ago, # ^ |   +8
•  » » » » » 8 years ago, # ^ |   +23 sooooorrrry is not the girl she claims to be in the picture. See this: http://goo.gl/5h1gYJ — sad, everyone was so excited.
•  » » » » » » 8 years ago, # ^ |   +43 - ... you or someone else?- Yes.Why do you think that she claims to be on the picture? Don't you know about "or" operator?
•  » » » 8 years ago, # ^ |   +4 [Fake beautiful profile picture] = UPVOTE! :)
•  » » » » 8 years ago, # ^ |   -13 Excuse you ?
•  » » » » » 8 years ago, # ^ |   -8 Come on people, Same comment +3 !! :|
•  » » » » » » 8 years ago, # ^ |   0 Why are you still commenting and going down in contribution? :3
•  » » » » » » » 8 years ago, # ^ |   +2 Because, still he has +16 contribution and the girl stolen his heart! :)
•  » » 8 years ago, # ^ |   0 put me minus !!!
 » 8 years ago, # |   +53 I will just leave this here: http://codeforces.com/blog/entry/10034#comment-155087Exactly 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.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +49 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.
•  » » » 8 years ago, # ^ |   -52 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.
•  » » » » 8 years ago, # ^ |   +36 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.
•  » » » » 8 years ago, # ^ |   -43 Dude watch yourself when leaving a comment in a site full of Russian.
•  » » 8 years ago, # ^ |   +12 I also find completely unacceptable that so many contests on Codeforces take place on Fridays after the sunset or on Saturdays before the sunset.
 » 8 years ago, # |   +57 I celebrate my birthday today. And I hope, this round will be a gift from CodeForces for me! GL && HF!:)
•  » » 8 years ago, # ^ |   +55 Happy Birthday!
•  » » » 8 years ago, # ^ |   +40 Thanks a lot.
•  » » 8 years ago, # ^ |   +89 This is a scene that you won't see a lot...
•  » » » 8 years ago, # ^ | ← Rev. 3 →   +176 I laughed at this for hours :D
•  » » » » 8 years ago, # ^ |   +17 I am still laughing. :P
•  » » » » 8 years ago, # ^ |   +2 Have you notice the third position? Check this
•  » » » » 8 years ago, # ^ | ← Rev. 3 →   -11 :D
•  » » » » 8 years ago, # ^ |   0 oh,it must be a fun for chritmas!
•  » » » 8 years ago, # ^ |   +16 anyone noticed this. SAKT :p leave dreammoon alone :p
 » 8 years ago, # |   +2 i am new in codeforces i want to see problems in codeforces round #284
•  » » 8 years ago, # ^ |   +23 wait for 15 hours and you can see those.
 » 8 years ago, # |   +113 Your bets — will dreamoon_love_AA win div2 tomorrow? :)
•  » » 8 years ago, # ^ | ← Rev. 2 →   +11 We 2nd division participants will make sure he doesn't
•  » » » 8 years ago, # ^ |   +3 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
•  » » 8 years ago, # ^ |   +45 Maybe he will cha to get -inf score,and integer overflow to +inf score and get the first place
•  » » » 8 years ago, # ^ |   +137 You shouldn't be drinking so much during christmas .
•  » » » 8 years ago, # ^ |   +28 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!
•  » » 8 years ago, # ^ |   +46 I bet 100 Quatloos that he won't.
•  » » » 8 years ago, # ^ |   -7 Is it because you are gonna participate with a fake account?
•  » » » » 8 years ago, # ^ |   +5 No, it wouldn't probably change much and I'm most likely not going to participate at all.
•  » » » » » 8 years ago, # ^ |   -7 Is sorry_dreamoon participating in your place?
•  » » 8 years ago, # ^ |   -18 btw,can you imagine that oneday tourist's rating overflow to -inf and worse's rating overflow to +inf?
•  » » » 8 years ago, # ^ |   -9 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 .
•  » » 8 years ago, # ^ |   +8 Maybe He/She is challenging worse !
 » 8 years ago, # |   +81 Merry Christmas to everyone !
 » 8 years ago, # |   0 Good luck to everybody!
 » 8 years ago, # |   -171 dis like me plz
•  » » 8 years ago, # ^ |   +35 Your wish will be granted
•  » » 8 years ago, # ^ |   -17 Try harder!!!
 » 8 years ago, # |   -8 Hi!thanks gridnevvvit !your last contest had vary nice problem (Codeforces Round #275):) thanks :)
 » 8 years ago, # |   -45 Hope for high rating.
•  » » 8 years ago, # ^ |   0 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 :)
•  » » » 8 years ago, # ^ |   0 I think guys like you are the reason he has a low contribution :)))
•  » » » 8 years ago, # ^ |   -17 Can you give me evidence for this letter?
•  » » » » 8 years ago, # ^ |   -10 "I guess : choghok , clashofclans , contest1234 and delairer." he guesses
•  » » » » » 8 years ago, # ^ |   0 Of course I guess, cause there might be more :)
•  » » » » » » 8 years ago, # ^ |   0 Well i thought you meant that you "guessed" these are his accounts my bad
•  » » » » » » 8 years ago, # ^ | ← Rev. 3 →   -13 What do you mean ?contest1234 => last online 3 weeks ago!delairer => Last visit: 5 months ago!tourleader => last online 3 weeks ago!
•  » » » » » » » 8 years ago, # ^ |   0 Isn't that obvious? you make an account give some contests with it and then you just leave it by,
•  » » » » » » » » 8 years ago, # ^ |   -25 It is against the rules and i never do it!
•  » » » 8 years ago, # ^ |   +2 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 .
 » 8 years ago, # | ← Rev. 2 →   +8 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 ...
•  » » 8 years ago, # ^ |   +5 I am firstly joining it too!I am also a chinese.
•  » » » 8 years ago, # ^ |   +5 Good Luck to you two!
•  » » » » 8 years ago, # ^ |   0 LOOK your headpicture ，and I guess you are a Chinese。
•  » » » » » 8 years ago, # ^ |   +16 "head picture" = =
•  » » » » » 8 years ago, # ^ |   +5 i agree with you. but the headpicture... er maybe who is not chinese can't understand you.
•  » » » » 8 years ago, # ^ |   0 Thanks!
 » 8 years ago, # | ← Rev. 2 →   +248
•  » » 8 years ago, # ^ | ← Rev. 6 →   -51 ok ok !I'm loser!you are winner !
•  » » 8 years ago, # ^ |   0 worse is win,dreamoon : GaMeOVeR
 » 8 years ago, # |   0 My first contest on Codeforces. n feeling sleepyyyy :)
 » 8 years ago, # | ← Rev. 3 →   0 Merry Christmas to all :)All the best for the Round #284.
 » 8 years ago, # |   +18 Merry Christmas! GL && HF!
 » 8 years ago, # |   0 Hope to gain some rating points this Christmas ;)
 » 8 years ago, # | ← Rev. 2 →   -15 I hope all Specialist be candidate master (!) and all Expert be master (!!) and dreamoon_love_AA be grand master !
•  » » 8 years ago, # ^ | ← Rev. 2 →   +7 poor pupils and newbies then ...
•  » » 8 years ago, # ^ |   0 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. :)
•  » » » 8 years ago, # ^ |   0 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
 » 8 years ago, # |   0 Merry Christmas!
 » 8 years ago, # | ← Rev. 2 →   0 Merry Christmas
 » 8 years ago, # | ← Rev. 2 →   -10 Scoring system will be Dynamic , don't know is it good for me or not ! My curious mind want to know what others think ?
 » 8 years ago, # | ← Rev. 3 →   0 Dynamic Scoring.while(true) System.out.println("NOOOOOOOOOOOOOOOOOOOO");
•  » » 8 years ago, # ^ |   +24 TL, mate
 » 8 years ago, # |   -11 Hope for much [pure] math
•  » » 8 years ago, # ^ |   0 (And strong pretests!!)
•  » » » 8 years ago, # ^ |   0 Eh, well it is a matter of opinion. I personally believe that hacking creates more suspense, especially right after you try to hack someone.
 » 8 years ago, # |   +3 We can see about dynamic scoring system here.
 » 8 years ago, # |   +19 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 !
•  » » 8 years ago, # ^ |   +13 sorry_dreamoon...?
•  » » » 8 years ago, # ^ |   +9 sorry_dreamoon uses Java 7. So, I don't think it can be tourist.
•  » » » » 8 years ago, # ^ |   +28 tourist also uses Java 7 click here
•  » » » 8 years ago, # ^ |   0 I think he is Petr
•  » » 8 years ago, # ^ |   +3 :) Really nice... poor dreamoon
 » 8 years ago, # |   0 Let's Pa Pa Pa tonight. :D
•  » » 8 years ago, # ^ |   0 one more chinese say something chinglish o(╯□╰)o
 » 8 years ago, # |   0 Many Thanks to you <3
 » 8 years ago, # |   0 GL HF
 » 8 years ago, # |   -42 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.
 » 8 years ago, # |   -9 sorry_dreamoon is now at first place! dreamoon_love_AA's only chance now is to solve E quickly and find lots of hacks!
•  » » 8 years ago, # ^ |   +38 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
 » 8 years ago, # |   0 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...
•  » » 8 years ago, # ^ |   0 In my opinion, brute force solutions are quite prone to errors
 » 8 years ago, # |   0 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.
 » 8 years ago, # |   +10 How hard it is!!! Poor rating...
•  » » 8 years ago, # ^ |   0 I don't know why sorry_dreamoon want to do this. I think it is so cruel.
 » 8 years ago, # | ← Rev. 2 →   +8 contest is not attractive :( without Top rank in Div2 :)
 » 8 years ago, # |   +15 interesting competition between sorry_dreamoon and dreamoon
 » 8 years ago, # |   0 I just want to know who is sorry_dreamoon :P Comment guesses :D
•  » » 8 years ago, # ^ |   +1 someone from top 10
•  » » » 8 years ago, # ^ |   +9 yeah he seemed highly confident when saying "we will see it soon".
•  » » 8 years ago, # ^ |   0 It's some evidences... :D http://codeforces.com/comments/with/sorry_dreamoon
•  » » » 8 years ago, # ^ |   0 Kinda obvious hehe http://codeforces.com/blog/entry/15336#comment-202784
•  » » » 8 years ago, # ^ |   0 Does he know Java 7 ?!
•  » » 8 years ago, # ^ |   -15 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 .
 » 8 years ago, # |   +10 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!
•  » » 8 years ago, # ^ | ← Rev. 2 →   -11 It ended...they accept all of problems surly...
•  » » » 8 years ago, # ^ |   0 No, it hasn't ended yet. There are 10 minutes left.
•  » » 8 years ago, # ^ | ← Rev. 3 →   +21 sorry_dreamoon can get banned for double-account (surely he is from div1) and dreamoon_love_AA will be top1 :D
•  » » » 8 years ago, # ^ |   +25 Can you prove it is a double account?
•  » » » » 8 years ago, # ^ |   -9 it is just like proving 2+2=4
 » 8 years ago, # |   +10 liymsheep on the lines of worseDoing so many unsuccessful hacks, so the first three contestants will have dreamoon in their handle name :D
•  » » 8 years ago, # ^ |   0 It's such sad story...after letting the top 3 places to dreamoons, liymsheep fails D him/herself and becomes 10th instead of 4th :(
 » 8 years ago, # |   0 What a Christmas gift!!!
 » 8 years ago, # |   0 It was a nice contest! easy problems A & B and normal Problem C!
 » 8 years ago, # |   +2 How to solve div. 1 498B - Name That Tune and 498C - Array and Operations?
•  » » 8 years ago, # ^ |   +10 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.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 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...
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   0 @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.
•  » » » » 8 years ago, # ^ |   0 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.
•  » » » 8 years ago, # ^ |   0 How is the tree built?
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +1 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)
 » 8 years ago, # |   +186
•  » » 8 years ago, # ^ |   +8 Poor dreamoon_love_AA :D
•  » » » 8 years ago, # ^ |   0 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.
•  » » » » 8 years ago, # ^ |   +39 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 :P
•  » » » » 8 years ago, # ^ |   +16 dreamoon_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.
•  » » » » » 8 years ago, # ^ |   0 No, he can't. It's against rules :).
•  » » » » » » 8 years ago, # ^ |   +3 So you think it is his first and only account?
 » 8 years ago, # |   0 Div. 2 Problem C. I thought that answer is number of lines between two points. Where i am wrong?
•  » » 8 years ago, # ^ |   0 You are right, watch for overflow though.
•  » » » 8 years ago, # ^ |   0 You are right too. I'm using double instead long double... what a shame...
•  » » » » 8 years ago, # ^ |   +1 You are wrong now. Use integer arithmetics only, avoid double or long double.
•  » » » » » 8 years ago, # ^ | ← Rev. 3 →   0 Actually, double will pass; I just tested it. 9262061Unfortunately I made some other stupid mistake which led it to fail on system test :(
•  » » » » » 8 years ago, # ^ |   0 Yeah. Long long int is good here.
•  » » » » » 8 years ago, # ^ |   0 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 :)
 » 8 years ago, # |   0 Epic Standings . Sorry Dreamoon
 » 8 years ago, # | ← Rev. 2 →   0 So sadGot 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.
•  » » 8 years ago, # ^ |   +3 SQRT decomposition is pretty bad for this problem :(
 » 8 years ago, # |   +4 Is this contest too?
 » 8 years ago, # |   -43 I think that sorry_dreamoon is another account of dreamoon_love_AA
•  » » 8 years ago, # ^ |   -18 And dreamoon_fan too. He registered 4 hours ago and sorry_dreamoon 7 hours ago.
 » 8 years ago, # |   0 System was very good !!! Thanks... :)
 » 8 years ago, # |   +6 It is a bit annoying that there are a little hacks int the 2nd division
 » 8 years ago, # |   -6 Nice problem thanks gridnevvvit!
 » 8 years ago, # | ← Rev. 2 →   +2 Happy Christmas Everyone!!Especially to dreamoon... Awesome scoreline XD
 » 8 years ago, # |   +4 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?
 » 8 years ago, # | ← Rev. 2 →   -8 How to solve DIV 2 D?
 » 8 years ago, # |   0 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.
•  » » 8 years ago, # ^ |   +6 Next time use "define ONLINE_JUDGE".
•  » » » 8 years ago, # ^ |   0 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.
 » 8 years ago, # |   +10 I got 'judgement failed' on my submission for Div1 B: http://codeforces.com/contest/498/submission/9246565. What does this mean?
 » 8 years ago, # |   +4 Contest in hack is not !!!
•  » » 8 years ago, # ^ |   +1 Yes.
 » 8 years ago, # |   0 Mery Christmas :) Good problems!But Today, I'm not lucky (I've been seen dinosaurs on chrome :D)
•  » » 8 years ago, # ^ |   0 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 :)
 » 8 years ago, # | ← Rev. 2 →   +29 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...
•  » » 8 years ago, # ^ |   0 he/she will be in div.1 for next contest
 » 8 years ago, # |   +16 I dont know dreamoon But It's for him/her (...) I hope best ranks in goodbye 2014 for you :D
 » 8 years ago, # |   +43 Merry Christmas dreamoon_love_AA!
 » 8 years ago, # |   0 http://codeforces.com/contest/499/submission/9254466can someone point out why its giving wrong answer?
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 use long long intstead of long int
•  » » 8 years ago, # ^ |   0
•  » » 8 years ago, # ^ |   0 You must use long long not long :D
•  » » 8 years ago, # ^ |   0 I noticed it later, cost me the whole contest.
 » 8 years ago, # |   +19 I have a gut feeling that dreamoon_love_AA will again try to return to Div. 2 in the next contest.
 » 8 years ago, # |   +1 dreamoon_fan is also there, is it possible to change your handle??
 » 8 years ago, # | ← Rev. 2 →   +27 is tourist sorry_dreamoon ? Because sorry_dreamoon finished the contest in 48 minutes.
•  » » 8 years ago, # ^ |   +2 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).
•  » » » 8 years ago, # ^ |   0 And the codes were is JAVA, i dont think tourist would have done that, even though thats not hard for a redcoder!!
•  » » 8 years ago, # ^ |   0 Too sad.
•  » » 8 years ago, # ^ |   +38 I think sharing Personal talks publicly is not cool.
 » 8 years ago, # |   -89 pls,plz,pls,plzdis like me plz
•  » » 8 years ago, # ^ |   0 As you say sir, DONE :D
 » 8 years ago, # |   0 Is dreamoon_love_AA girl or boy?
•  » » 8 years ago, # ^ |   0 boy
•  » » 8 years ago, # ^ | ← Rev. 2 →   +2 Be to Che
•  » » 8 years ago, # ^ |   0 definetely boy:http://codeforces.com/blog/entry/8528
 » 8 years ago, # |   0 A little bug in my submission for problem A div.1 ... I want to kill myself now :D
 » 8 years ago, # |   0 Rating Updated.
•  » » 8 years ago, # ^ |   +1 Congratulations...
 » 8 years ago, # |   +3 sorry_dreamoon . Please can you reveal yourself .
 » 8 years ago, # |   +49 After 42 contests I finally reached Div1. What a great Christmas gift! :)
•  » » 8 years ago, # ^ | ← Rev. 2 →   +9 congratulations, my friend!
•  » » 8 years ago, # ^ |   +20
 » 8 years ago, # |   +5 Div.1 B is really hard to understand for me... Sad story...
 » 8 years ago, # | ← Rev. 4 →   +138
•  » » 8 years ago, # ^ |   0 hahahaha I like
 » 8 years ago, # |   0 http://codeforces.com/contest/499/submission/9260829 in my above solution of problem 499B lecture in java when i am executing it on my system it is not showing any error but when i am submitting, it is showing runtime error and null pointer Exception. please point out the mistake.
 » 8 years ago, # |   +5 The amount of dreamoon_love_AA is too damn high
 » 8 years ago, # |   +11 Div2 only top 3 ... Why? because... dreamoon :)
 » 8 years ago, # |   +13 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)?
•  » » 8 years ago, # ^ |   +19 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(nT2), 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.
•  » » » 8 years ago, # ^ | ← Rev. 6 →   0 Apparently the jury was trying to kill O(n * T2) heuristics with breaks.They did quite a good job. For example: http://codeforces.ru/contest/498/submission/9260678I 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 * T2) solutions that passed though: http://codeforces.ru/contest/498/submission/9250130.
 » 8 years ago, # |   0 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)
•  » » 8 years ago, # ^ | ← Rev. 4 →   +8 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.
•  » » » 8 years ago, # ^ |   0 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.
•  » » » » 8 years ago, # ^ |   0 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?
•  » » » » » 8 years ago, # ^ | ← Rev. 2 →   +24 Without having i + j is odd. Graph might had triangles. That's why one can not use bipartite matching anymore.
•  » » » » » 8 years ago, # ^ | ← Rev. 5 →   0 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: 6 6 2 2 2 2 2 2 1 2 1 3 2 3 4 5 4 6 5 6 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.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 8 years ago, # ^ |   +1 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])
•  » » » » 8 years ago, # ^ | ← Rev. 3 →   +1 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, (here b[i] is the number of factors of the prime in a[i]) and m good pairs, find the number of operations you can do where each operation consists of subtracting the 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 just b[i]), make the capacity of the flow from any node representing i to the supersource/supersink equal to b[i]. Then, for each good pair connect the two nodes, with capacity equal to the minimum of the numbers of factors of p (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 3Here, a = {8, 12, 8}. Consider the prime p = 2. The resulting b = {3, 2, 3} (the number of factors of 2). Now, the flow graph looks like this:
•  » » » » » 8 years ago, # ^ |   0 Thanks both of you! It is totally clear now. :)
 » 8 years ago, # |   0 Where are the editorial ?? :/
•  » » 8 years ago, # ^ |   0
 » 8 years ago, # |   0 When could I get the editorial for 284 div 2?
•  » » 8 years ago, # ^ | ← Rev. 2 →   0
 » 8 years ago, # | ← Rev. 2 →   -66 .
•  » » 8 years ago, # ^ |   0 You can get partial scores on Hackerrank for test cases you got correct. But in Codeforces and Topcoder there is no partial scoring system.