### hogloid's blog

By hogloid, 5 years ago, ,

Hello everyone!

snuke, wolf_sothe and me would like to invite you to Codeforces Round #263 for both divisions. It will be held on Tuesday, August 26th at 18:00 MSK. Note that this round starts on different time from normal rounds.

Great thanks to Gerald for helping us prepare the round, MikeMirzayanov for creating a fine platform, and Delinur for translating the statements.

You'll help men named Appleman and Toastman in this round. Good luck and have fun!

UPD. In Div.1 and Div.2, scores will be standard, that is , 500-1000-1500-2000-2500 for each problem.

Now the contest is over! Thank you for participating!

Here are the winners:

Div1.

Div2.

Congratulations on WJMZBMR, who solved all the problems !

Editorial is here

•
• +420
•

 » 5 years ago, # |   +42 Today is Saturday, the 23rd.Contest is on Sunday, the 26th.OK.
•  » » 5 years ago, # ^ |   +22 Oh, I missed fixing. Thanks.And I was surprised by how fast you found this post :)
•  » » » 5 years ago, # ^ |   +2 :)
•  » » » 5 years ago, # ^ |   0 Seriously, What kind of contest was that?! Top 20 of Div2, had totally hacked 118 solutions. And so on for other contestants :|
•  » » 5 years ago, # ^ | ← Rev. 3 →   +9 Good Job ! It's time to fight in div1 .hope to up rating ^_^
 » 5 years ago, # |   +63 A Div1 + Div2 round :)) It 's time for the "newly registered army" to take off their mask ^^
 » 5 years ago, # |   +40 Www,long time no see div.1
•  » » 5 years ago, # ^ |   +11 Open your mouth!
•  » » » 5 years ago, # ^ |   +1 Come On, Who dare who!
•  » » » » 5 years ago, # ^ |   +5 What happened ? calm down,please.
•  » » » » » 5 years ago, # ^ |   +2 Just a joke :)
 » 5 years ago, # |   -14 I think problems will be very hard and logical.
•  » » 5 years ago, # ^ |   -10 Thanks for your opinion, it means so much to me!
•  » » » 5 years ago, # ^ |   -11 i hate to see this comment getting too much down votes!
•  » » » » 5 years ago, # ^ |   -19 Okay, let me translate how I understood it: "STFU NOBODY CARES ABOUT THAT!". Would you not downvote it?
•  » » » » » 5 years ago, # ^ |   0 what a coincidence!! i understood it as "STFU NOBODY CARES ABOUT THAT!" too! we have a lot of common man! you might up-voted it as i did it so.
 » 5 years ago, # |   +61 Finally a round by animals (cat, wolf and squirrel, right?) from Japan!Oh, god, the start time is 7:00 am in LA, it will be a tough round for me. :)
•  » » 5 years ago, # ^ |   +8 It's a chance to keep early hours for you ;)
•  » » 5 years ago, # ^ |   +10 Maybe one of them is a pony.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 .
•  » » 5 years ago, # ^ |   -14 Tough round for red contestant, yes, sure...
 » 5 years ago, # |   +3 Why there's still no upcoming contest now???
 » 5 years ago, # |   +22 Wow, blog is earlier than upcoming contest list.
 » 5 years ago, # |   +9 Wow. So early blog postAnd I like the contest time which is a bit early than usual :D don't have to stay up to midnight :D
 » 5 years ago, # |   +20 At least, names of heroes are easy to pronounce this time :D
•  » » 5 years ago, # ^ |   +11 Compared to other characters, they have a bit longer names, though ;)
 » 5 years ago, # |   +1 OMG ..In korea the time is 23:00.. and I'll be home at 12:30...I can't participate this round :<
 » 5 years ago, # |   +10 at last a DIV1 round after 2 contests :)
 » 5 years ago, # |   -7 My first div1 round ever.. so.. lets hope for math!
•  » » 5 years ago, # ^ |   +14 According to your comments on CF i suppose that you love math very much:)
 » 5 years ago, # |   +5 Appleman looks much better than official Apple logo. :)
 » 5 years ago, # |   +3 Let's not hope for math, and for dp and graph theory [by the way kudos to SRM 630 writers]. Also, I knew that this will be a lucky contest for me right after I saw the apple. Apples are graphs >:D.
•  » » 5 years ago, # ^ |   +14 Let's also hope for clear problem statements! Sometimes I become confused reading them for the first time!+long editorial :)Good Luck.
•  » » » 5 years ago, # ^ |   +7 Let's also hope short problem statement , short solutions :)also Good Luck.
 » 5 years ago, # |   +4 good time for contest :) hooooray !
 » 5 years ago, # |   +6 Waiting for a great contest! Hope the problem easy to understand.
 » 5 years ago, # |   +3 Continuous rating down......
 » 5 years ago, # | ← Rev. 2 →   0 If we fail pretests 2 times is the penalty = -(50*2) or (-50) ? Same question for failed hacks .
•  » » 5 years ago, # ^ |   +1 -50 for every failed pretest (not counting failed on pretest 1), but only if you eventually solve the problem. -50 for every failed hack. So that means two failed pretests are -100 and so as two failed hacks.
•  » » » 5 years ago, # ^ |   0 How much penalty for failing pretest 1 two times ?
•  » » » » 5 years ago, # ^ |   +8 Failing pretest 1 doesn't give any penalty (because the reason might be selecting the wrong file, among other things, that is just a minor error). So failing pretest 1 twice doesn't take any points either.
•  » » » » » 5 years ago, # ^ |   0 "selecting the wrong file". Happens with me most of the time.:/
 » 5 years ago, # | ← Rev. 2 →   -6 IGNORED
•  » » 5 years ago, # ^ |   -11 look on the bright side — then u will be able to compete in Div-2 only contests. :)
•  » » 5 years ago, # ^ |   0 All the best!. :D
 » 5 years ago, # |   +16 Wow, long time no see Div1!Come on, let's enjoy it~ ^+^
•  » » 5 years ago, # ^ |   -7 Solo!
•  » » » 5 years ago, # ^ |   0 Come on!Who pa who!
•  » » » » 5 years ago, # ^ |   -8 Can I join in you, if you guys don't mind?
•  » » » » » 5 years ago, # ^ |   -6 Wahaha,come on!Together if solve 0 problems then eat keyboard(or xiang?)!
 » 5 years ago, # |   0 The contest is a little early in the day than usual. Its coinciding with my mess timings for dinner! :(
•  » » 5 years ago, # ^ |   +6 as a BITSian who has participated in contests at such time, let me tell u this.we both know that the mess food sucks. so go to mess around 7, take some extras, and come back to your room. do the contest, while eating/drinking the above stuff. then go to ANC (very close to ur SK bhawan, AFAIK) and eat to ur heart's content. :D hopefully system testing will be over by the time u return.
•  » » » 5 years ago, # ^ |   +4 That is quite prudent. I agree.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +3 Well I think I will most probably compete then ! :) No more excuses for not participating !
 » 5 years ago, # |   +6 give yuo a plus please — http://codeforces.ru/blog/entry/13439 !!! P. S. not minus me !!!
 » 5 years ago, # |   +10 Oh , I missed to be Candidate master with (4) rating last contest. I hope to raise to Div1 tomorrow :)
•  » » 5 years ago, # ^ |   +1 All the best!! :)
 » 5 years ago, # |   +2 "May the Odds be in your favor!" :D
 » 5 years ago, # |   -24 Hope for good problem, long time no see div.1. Good luck and have fun for everyone.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +89 I hope you will not use fake account this contest
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 we should register only one account. :)
•  » » » 5 years ago, # ^ |   +2 kuangbin11 and kuangbin12 also! probably they will become Candidate Master in the next two Div-2 only contests.
•  » » » » 5 years ago, # ^ |   +18 Bad new for kuangbinkuangbin13 isn't emtpy anymore
•  » » » » » 5 years ago, # ^ |   -12 Bad news for you, if you are the one who took the handle, they may ban you :)
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   +22 Good news for me He isnt me :D
•  » » » » » » » 5 years ago, # ^ |   +5 HAHA, these are not my handle~~~
•  » » » » » » » » 5 years ago, # ^ |   0 However, they all use the same header that you use in your code... With "kuangbin" written in the top... Such a weird coincidence...
•  » » » 5 years ago, # ^ |   +13 I've seen those accounts being posted around a few times already and it's clearly against the rules to make more than one account and compete, so can someone tell me why the hell isn't he banned?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 we can't agree more !
•  » » » » » 5 years ago, # ^ |   +4 Well it just quite angers me. I see blogs and comments non-stop complaining "there are so many fakes in Div2, why would they do this" and then when you see someone with 10 accounts, all of them with participations only until they reach Div1, which is obviously cheating, no one really cares. I thought people wanted to reduce fakes? I mean, as JuanMata showed, he has 2 more waiting for a Div2 round, doesn't seem like he will stop doing it.
•  » » » » » » 5 years ago, # ^ |   +2 ofcourse we want to reduce fakes!but i don't agree with no one really cares — i mean, surely one of the reasons why muratt posted these two comments was so that admins could see them and ban those accounts.as to why these accounts don't get banned — probably the admins want to prove without doubt that they are fakes before taking any action, lest they ban an innocent newly registered user (who will have no idea wtf just happened, and start disliking CF for wrong reasons)!
•  » » » » » » » 5 years ago, # ^ |   0 I get that you post this so the admins can see it, but my point was that this is not the first time someone posts names of obvious cheaters. Thing that frustrates me is that sometimes I see posts from months ago where someone reported a cheater, and when I check the cheater's account, it is perfectly unharmed!Now I get the "prove without doubt" part, and I don't try to sound arrogant in some way since I'm not familiar with the things admins can do, but couldn't they simply check the IPs of the users? Surely that would still leave room for cheating as you can hide it or change it, but most of them will most likely use the same IP. Obviously if your cheating accounts have just another digit added to the end of their name, I doubt you'd go as far as hiding your IP.I guess you could argue further that same IP is still not reliable (a brother, a friend from your computer) but in some cases such as the above one it's just kinda obvious that cheating is going on.
•  » » » » » » 5 years ago, # ^ |   0
•  » » » 5 years ago, # ^ |   +3 Stierlitz still was never so close to a failure...
•  » » » 5 years ago, # ^ |   0 It is outraging to see this in Div. 1. Previously I thought such detestable things only occurred in Div. 2.
•  » » » 5 years ago, # ^ |   0 kuangbin have really ability.He always have good rank in my contry's match！this is a evidence(recent match)：http://www.bnuoj.com/v3/contest_show.php?cid=4340#standing maybe you misunderstand him! I have studied much knowledge from his blog. so I am very like him!
 » 5 years ago, # |   -11 thanks for u.....Oracle Training in Chennai
 » 5 years ago, # |   0 long time no taking div2:) Ok, let me do it tonight!
 » 5 years ago, # |   0 We better take a break from math problems today, I hope :)
 » 5 years ago, # |   +7 What do you guys do before contest?
•  » » 5 years ago, # ^ |   +19 Live.
 » 5 years ago, # |   +3 I have a question: Can I participate in div 2 contest? or just Div 1?
•  » » 5 years ago, # ^ |   +4 If your rating is >=1700 you can not participate in Div2 contests when a div1 contest is scheduled at the same time.However if there is a solo div2 contest and the organizers allow , then you can participate in it, but that would be unrated for you.
•  » » 5 years ago, # ^ |   0 If you can do all problems in both, why not.
 » 5 years ago, # |   -14 Wow! Amount of div1 participants is very close to amount of div2 participants. :D Amazing)
•  » » 5 years ago, # ^ |   +18 1329 registrants for Div1 and 3988 for Div2. Yes you are right, very close :|
•  » » » 5 years ago, # ^ |   +3 yep last digit of two numbers 8 & 9 is very close :D
•  » » 5 years ago, # ^ |   0 How sir?
•  » » » 5 years ago, # ^ |   0 he didn't mention he is joking :D
•  » » 5 years ago, # ^ |   0 When I wrote that comment, they were very close. Why --------?? You can't understand it without my hint? (Sorry for bad English :D)
•  » » » 5 years ago, # ^ |   +4 Nope. You wrote that comment 15 minutes before the contest started. Are you implying 2500 users registered in 10 minutes? Because I won't believe that.
 » 5 years ago, # |   -10 I hope that contestwill be intresting, good luck for evrybody :)And one question — who is Toastman? Is it a worm?)
 » 5 years ago, # |   +11 Toastman is him.He appears in this problem.
 » 5 years ago, # |   -28 hello ~ why my B problem hack failed... my generate program is print 100000,100000 a = [] for i in xrange(100000): a.append('A') print "".join(a) thx~
•  » » 5 years ago, # ^ |   -6 consider endlines
•  » » 5 years ago, # ^ |   0 I think it's not good to publish a generator to B, which would break 50% of submissions, before the contest ends...
•  » » » 5 years ago, # ^ |   0 mine is broken too :(
 » 5 years ago, # |   0 The worst feeling in the world — when you lock your solution to problem B for in D2 and realize minutes after that you are not going to pass the system test cases...At least I got some points back by hacking people in the rooms. How lucky some people are! With 15 hacks on the same problem, while I only got 7...
 » 5 years ago, # | ← Rev. 2 →   0 I made some stupid mistake at A and B, and it results in -100p for A and -50p for B =='Problem D & E are hard for div2 ==' btw problem B is a nice problem for hacking...
 » 5 years ago, # |   -9 Awful problem statements (were they in english !?) .It doesn't matter how good your problems are if they are not readable .
•  » » 5 years ago, # ^ |   0 I agree with that!!! Especially on problem B. I asked " I cannot understand the method by which coins are given, because the problem statement's English language is [cannot be understood at all]. How are coins awarded? " and they answered me " No comments "! Unbelievable! Someone REALLY MUST build a platform like CodeForces, but on U.S.A. servers and with people having passed the ECPE!!
•  » » 5 years ago, # ^ |   +2 it is pretty obvious when three geek red coders prepare some round. they don't speak english/japaneese/chineese or russian. they only speak c++ :p
•  » » » 5 years ago, # ^ |   +7 English is pretty much of a prerequisite for coding, as most of textbooks available are in English language and not in Russian! And since they are geeks, which more or less means that they have read A LOT and know A LOT, they should now English to a sufficient level (maybe ECPE is too much, but ...)!
•  » » » » 5 years ago, # ^ |   0 its not about knowing English sir, its about using right word at right place. its about explaining something, making something understandable to me. Except B all the problems were well written , i think. though it would be fine if the explanation of problem E would express test case one completely instead of just updates. but I think it was fair enough... My suggestion would be to evolve at least one purple coder to test div2 problems.
•  » » 5 years ago, # ^ |   0 totally agree.I submitted so late problems A and B because they were not clear. Wasted much time in understanding the problem statement.
•  » » 5 years ago, # ^ |   0 I agree, the English problem statement for B was impossible to understand without looking carefully at the test case and guessing what it meant. We need a translator for (English -> Russian) and for (English -> English).
•  » » » 5 years ago, # ^ |   0 Absolutely agree... This should be seen AND corrected by the Codeforces Government (meaning Headquarters!!!)
 » 5 years ago, # |   +39 Доминируй, властвуй, унижай!
 » 5 years ago, # |   +8 :'( nah, hard problems, but I still love it :)), I love the way I can't solve this :'(
 » 5 years ago, # |   0 Hacking is really fun :D
 » 5 years ago, # |   +13 Wow!
 » 5 years ago, # |   0 No simple for problem D,E Div2
 » 5 years ago, # |   +4 Contest's ended. How to solve 462D - Яблов и дерево?
•  » » 5 years ago, # ^ |   +2 DP on states "there's 1 black vertex in subtreee of v left" and "there's 0 black vertices in subtree of v left"
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +2 Would you care to elaborate. If your solution is correct, please explain it.
•  » » » » 5 years ago, # ^ |   0 I'm kind of lazy here, so: if you want to think about how to solve the problem, this should be enough of a hint if you don't, just wait for the editorial
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Thanks anyway.
•  » » 5 years ago, # ^ |   +3 Dynamic on tree, save two value — how many ways to get black from component with root in current vertex and how many to get white from it. Then answer will d[0].black.
•  » » » 5 years ago, # ^ |   0 What do you mean by: "how many ways to get black"?
 » 5 years ago, # |   +3 I've never seen so many hacks..that's amazing.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +30 It's not that much, anyway (Codeforces Beta Round #60)
•  » » » 5 years ago, # ^ |   0 wow! just crazy, nothing to say :-)
•  » » 5 years ago, # ^ |   0 I've never seen so few hacks (granted, I usually don't watch them, but div1 was as poor in that regard as div2 wasn't).
 » 5 years ago, # |   0 A lot of participants in room 58 were inactive, would have been even more interesting had more people taken the contest :P
 » 5 years ago, # |   +1 Nice problems... :) And nice round for Hack Lovers... :D
 » 5 years ago, # |   0 The hack swarm had to happen :-P
 » 5 years ago, # |   0 No hacks this round. :)) Liked it though. I'm curious about A's proof, liked B and nearly finished C. Keep it up.
 » 5 years ago, # |   0 hack with OVERFLOW :)
 » 5 years ago, # | ← Rev. 3 →   +3 C(div1) is a joke :D. Didn't have enough time to code it unfortunately. Great contest anyway.
 » 5 years ago, # |   +2 I was at the blessing room. 19 successful hacks :D
 » 5 years ago, # |   0 Please make the difficulty distribution of questions more uniform. for example 1-3 were submitted by about 1500 coders and count dropped to about 100 in 4th question.BTW enjoyed the contest. Waiting for editorial
 » 5 years ago, # | ← Rev. 2 →   0 Is this the correct solution for Div 2 C? http://ideone.com/AhciANEdit: It's not.
 » 5 years ago, # |   0 In Div,1 contest, half of submissions are for problem A. It seems that no one fail system tests on A. I think it's a quite simple problem, therefore, the number of participants today is much more than other contests.
 » 5 years ago, # |   0 982 official users in div 1 Awesome!!
 » 5 years ago, # |   +3 I don't think i've ever loved integer overflow so much :D
 » 5 years ago, # |   0 Am I right saying that in Div1D 4x4 corner determines all other cells, because rows and columns have to be periodical with period 4?
•  » » 5 years ago, # ^ |   +16 No, it's not true.
•  » » » 5 years ago, # ^ |   0 Thanks, I realized my mistake while ago. I had to mess something during the contest.
•  » » 5 years ago, # ^ |   +8 Very simple example: ....o... ...o.o.. ..o.o.o. .o.o.o.o o.o.o.o. .o.o.o.. ..o.o... ...o.... What you can do is fix the first row and then there is exactly one way to fill the rest (it's obvious that there is not more than one, and you just believe that it's always possible after looking at small cases with brute force)
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 In fact, the first row determines all other cells. Moreover (I didn't prove that, but the brute-force showed that), it seems that each combination of white and black cells in the first row generates a correct board.// Oops, too late answer :D
•  » » » 5 years ago, # ^ |   0 What do you mean by "each combination"? It has to be consistent with already filled cells.
•  » » » » 5 years ago, # ^ |   0 So you can guess that he means "for an empty board".
•  » » » » 5 years ago, # ^ |   +8 Okay, I forgot to add that if there are no cells which are already set, then we can color the first row in any way we want and generate exactly one correct solution from it (as yeputons said).This observation (as long as the very similar one: if we set 'O'=1, 'X'=0, then the value (mod 2) of each cell can be computed very easily from the values of the first row). Look at the example: a0 a1 a2 a3 a4 a5 a6 a1 a0+a2 a1+a3 a2+a4 a3+a5 a4+a6 a5 a2 a1+a3 a0+a2+a4 a1+a3+a5 a2+a4+a6 a3+a5 a4 a3 a2+a4 a1+a3+a5 a0+a2+a4+a6 a1+a3+a5 a2+a4 a3 a4 a3+a5 a2+a4+a6 a1+a3+a5 a0+a2+a4 a1+a3 a2 a5 a4+a6 a3+a5 a2+a4 a1+a3 a0+a2 a1 a6 a5 a4 a3 a2 a1 a0 (the addition is mod 2, i.e. the same as xor). If we count the prefix sums of the same parity (that is: 0, a0, a0+a2, a0+a2+a4, a0+a2+a4+a6, ... and 0, a1, a1+a3, a1+a3+a5, ...), we are able to write all the constraints in the form [one prefix sum] xor [another prefix sum] = (c=='o'). Number of such solution (and existence of them) can be computed/checked easily. Somehow I got WA, so maybe I'm not that right... :D
•  » » » 5 years ago, # ^ |   +8 Yes. We take x = 0 and o = 1. If we put ui = A[1][i], then we can write explicit formulas for A[i][j] int terms of ui. Each formula is like u2s + u2s + 2 + ... + u2t or u2s + 1 + ... + u2t + 1. So we have system of equations in F2n. We can find the number K of independet equations using Find-Union, Polish guys knows that trick from KUGLARZ (potyczki 2014).The answer is 2K or 0...
•  » » » » 5 years ago, # ^ |   +3 Lool, that is indeed a Kuglarz problem :D. Nice. So bad that I messed computations and came up with other formulas, Kuglarz was so nice it would be really fun to use that task in other problem. Btw, hi Maciek :).
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Sorry, doubled post, CF was not responding xd.
 » 5 years ago, # |   +13 Div1 — A was easy than usual and and Div1 — B was hard than usual.
•  » » 5 years ago, # ^ |   0 Why i got WA 19 div2A ? code
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +3 You need to check the boundary conditions of the 2-d array. For exampleif(x[i-1][j]=='o') should be changed to if(i>1&&x[i-1][j]=='o').Similarly for all boundaries.Hope this helps.
•  » » » » 5 years ago, # ^ |   0 but why ?
 » 5 years ago, # |   -8 Congratulations : — Div 1 : WJMZBMR — Div 2 : yyt16384
 » 5 years ago, # |   0 Compare Div 2 A with Div 1 D and Div 2 B with Div 1 E
 » 5 years ago, # | ← Rev. 2 →   0 IGNORED
 » 5 years ago, # |   0 I still see unrated genius users in Top 10 Div2...
 » 5 years ago, # |   0 I misunderstood problem C's description... This point specifically: Each time Appleman gets a group consisting of a single number, he throws this group out.What I understood was that if the group consisted of equal numbers, then he throws that group but it turns out this meant that a group is thrown away if group consists of a single number(Just as the sentence said...). Never thought of it that way until one of my friends explained.Just wanted to mention it so that if someone did the same, he wouldn't be puzzled too much.
•  » » 5 years ago, # ^ |   0 For the next time , look at the explanation of the test cases to avoid such mistakes :D
•  » » » 5 years ago, # ^ |   0 I did indeed but the explanation was working well with my assumption :D
 » 5 years ago, # |   0 how could so many people hack problem B(div.2) solutions? mine is also hacked as well, but i can't find my mistake. can anybody please tell me why this could happen? thanks :)
•  » » 5 years ago, # ^ |   0 Integer Overflow :D
•  » » 5 years ago, # ^ |   0 overflow occurred when you calculate bonus*bonus :(
•  » » » 5 years ago, # ^ |   0 ah as i expected, but the answer must be integer right? as the problem says : "print a single integer"
•  » » » » 5 years ago, # ^ |   0 I don't think "integer" in the problem does not mean int type
•  » » » » » 5 years ago, # ^ |   +3 i see, i will take that as a lesson for future contests :) thanks for helping me..
•  » » 5 years ago, # ^ |   0 In your code variable bonus should be long long.
•  » » » 5 years ago, # ^ |   0 i see, thanks for the correction :)
•  » » 5 years ago, # ^ |   0 I wish I was in your room...:P
•  » » 5 years ago, # ^ |   0 you have taken bonus in int and that will overflow.Imagine test case like 100000 100000 DDDDDD.....(100000) times so 100000*100000 would overflow int range
 » 5 years ago, # | ← Rev. 2 →   0 How long does it usually take, after the contest, to recalculate the rating of each participant? This is my first time competing on Codeforces. I was on a train for the first half of the competition, and didn't realize that the points for each problem decrease over time :\
•  » » 5 years ago, # ^ |   0 Depends. Sometimes a few minutes, sometimes a few hours.
 » 5 years ago, # |   +5 I was just about to use Splay in problem C when I found interval flip operations are not really needed. ...Anyway, the problems are nice.
 » 5 years ago, # | ← Rev. 2 →   0 yeputons, can you please explain how you solved 462D - Яблов и дерево?
•  » » 5 years ago, # ^ |   +37 Codeforces do not send any kind of notification for mentions in comments at all.Algorithm: we have system of linear equations modulo 2 (each variable is one cell of the field), there are n2 equations from the statement, and k equations from the input.Improvements and some ideas: If we fix the first row, we can deduce the rest. There fore, only n variables and only n equations from the statement (for the last row). In turns out that if we fix the first row, there will be no problems with the last one. I checked this for small n and believed. Now we have n variables and k conditions. Each conditions can have up to variables — it's still too much to just store it. Next notice: each cell is XOR of some continuous segment of cells with fixed parity from the first row. More details are available here. Now we can easily calculate all the k equations in form 'xor of variables from L to R is V'. If we run Gaussian elimination now, it's still very slow. However, if we sort equations by (L,R) lexicographically, it's easy to see that on each step of elimination all equations are still in the form 'xor of variables from L to R...', which is cool, because we don't have any problems with memory Next thing is to make elimination without actually editing each of the segments. I use the 'merge smaller to the larger and it'll be NlogN' trick here.
•  » » » 5 years ago, # ^ |   +25 You have answered Div1D, however dude above had asked you about Div2D which is Div1B :)
•  » » » » 5 years ago, # ^ |   0 Whoops. I'm sorry, didn't notice that, I saw 'D' and answered :)
•  » » » » » 5 years ago, # ^ |   +1 however, your answer on Div1B would be appreciated :)
•  » » » » » » 5 years ago, # ^ |   0 Done, hope that helps.
•  » » » 5 years ago, # ^ |   0 I am sorry, but I do not really get yours "I use the 'merge smaller to the larger and it'll be NlogN' trick here." Could you kindly clarify it? p.s. I spent come time looking into your code, but for me it looks like O(N2) :(
•  » » » » 5 years ago, # ^ |   +3 I think the thing that confuses you in my submission (7594572) is MagicSet. This structure is a set of some items with one addition: I can append one set to another. Obviously, I can add set A to set B in by just inserting all elements of A to B. Here is the magic: if (sz(this->data) > sz(b.data)) this->swap(b); If I do the job in instead of just and I move elements instead of copying (i.e. each element can be in one set only at every moment — like in Disjoint Set Union), the whole thing works in (amortized). Analysis is very simple and similar to what is used for DSU: let's take a look at each element. When it's moved from one set to another, the 'holder' set's size is increased twice at the least. There cannot be more than of such operations for each element, therefore we have operations with sets and the whole thing takes time. I'd also like to notice that one of these logs is from amortized analysis and has very little impact on constant factor, i.e. this is rather fast.
•  » » » » » 5 years ago, # ^ |   0 Thanks for clarification! I like your solution even more because it is clear you invented it by your own. btw, your trick works thanks to C++0x and its moving semantic, right? I mean this line: if (sz(this->data) > sz(b.data)) this->swap(b);
•  » » » » » » 5 years ago, # ^ |   +3 it is clear you invented it by your own. Well, it's pretty well-known trick. In the several past years I met it dozen times, starting with summer school training camp 2011 and IOI-2011 (problem 'race') which followed it. I've also met this on some Codeforces rounds for sure, on Petrozavodsk training camp... btw, your trick works thanks to C++0x and its moving semantic, right? No, move semantics is not used here. You know the swap function from STL (like swap(a, b)), and almost every STL structure has member function with the same name: a.swap(b), which does the same in constant time (for example, to swap two vectors you just need to swap two pairs of pointers, no need to copy the content). It was in C++03 for sure. Moreover, std::swap is overloaded for some STL structures to work without copying everything too. I personally prefer using a.swap(b) in places where I definitely need constant time complexity, because I don't remember exactly whether or not std::swap is overloaded.If you look in my code, you can see that I implemented this swap member function myself (using set<>::swap inside)
•  » » » » » » » 5 years ago, # ^ |   0 Well, it's pretty well-known trick. In the several past years I met it dozen times, starting with summer school training camp 2011 and IOI-2011 (problem 'race') which followed it. I've also met this on some Codeforces rounds for sure, on Petrozavodsk training camp... Could you kindly tell me a couple problems to solve? I think to really understand problem one has to solve a couple of similar ones.
•  » » 5 years ago, # ^ |   +7 Wrong problem, I'm sorry.Well, it's very straightforward for me: if you have tree (especially rooted one) and have to select some subset of vertices/edges and minimize/maximize some function of the resulting partition, you're gonna have a tree DP.Usually tree DP in partition problems looks like this: you've already partioned some sub-tree and are currently constructing a component to which a root of the subtree belongs. In this particular problem the only required property of a component is whether or not it contains one black vertex. It's the state of DP. Transition is another simple DP (please don't be scared by that): you start with one obvious way (depending on subtree's root's color) and then add children one-by-one. There are several possible ways of merging a child: it either has or not black vertex already, and you and also just cut an edge leading to the child.You can look at my code (7583221) for details — dfs() is doing the DP. I don't store results of DP anywhere — it's just passed as return value of dfs().
•  » » » 5 years ago, # ^ |   0 can you please explain how we can calculate the merging of childs , I mean if color of x is one , then we must cut all the edges to children right?cause If we add the edge then there will be an component with two black vertices. But , what are the calculations if x is white?
•  » » » 5 years ago, # ^ |   0 Learned a lot from your comment, thank you ! It would be great if you can provide some related problems which uses this method. (links to OJ problems would be appreciated)
 » 5 years ago, # | ← Rev. 2 →   0 IGNORED
 » 5 years ago, # |   0 Sir I got -1 on Div 2 problem 2 even though I did not submit any solution to the problem. Please look into the matter soon. :(
 » 5 years ago, # |   +141 Nice problem! D&E is really interesting to solve :).I am so lucky to get E right at 1:58:) ...Also It is my 7-th CF win!(For my darling sevenkplus :) )... Many years passed since I join CF, and the pleasure I get from it never decreased :).
•  » » 5 years ago, # ^ |   +42 Congratulations! <3
•  » » 5 years ago, # ^ |   +6 Congratulations! Wish to enjoy yourself with 7k+~!
•  » » 5 years ago, # ^ |   +8 Congratulations. Wonderful problems! Especially problem E. Although I have failed to discover the most important part :(
•  » » 5 years ago, # ^ |   +41 Professional!(which is a typical way of congratulating others or just greeting in Japanese geeks. In reply to this, one usually answers "Hobby")
 » 5 years ago, # |   +8 how to know what was the test case used by another person to hack my solution in the contest?
•  » » 5 years ago, # ^ |   0 you can't see it during the contest
•  » » 5 years ago, # ^ |   +2 You can't =(. But you can ask him/her directly =P
 » 5 years ago, # |   -10 http://codeforces.com/blog/entry/13563 Please upvote if u agree :)
 » 5 years ago, # |   0 When will div 2 rating be updated ? Div 1 rating is already updated.
•  » » 5 years ago, # ^ |   0 congrats :)
 » 5 years ago, # |   0 aah today I forgot to hack :)
 » 5 years ago, # |   +26 Finally DIV1 ,Now I can RIP :D
•  » » 5 years ago, # ^ |   0 What do you want to rip so much that you'd write it in caps? :D
•  » » » 5 years ago, # ^ |   0 RIP stands for "Rest In Peace" , I didn't want to rip anything Xellos :D :D
•  » » » » 5 years ago, # ^ |   +3 I hoped the :D at the end would make it clear that I know and it's a joke. Oh well.
•  » » » » » 5 years ago, # ^ |   0 yep I know you are joking and the same :D :D at the end of my sentence make it clear that I know you are joking and I make another joke replying to your joke :D
•  » » 5 years ago, # ^ |   +3 Me too =P
•  » » » 5 years ago, # ^ |   +3 Congraaaaaats :)
•  » » 5 years ago, # ^ |   +17 after 111 contests, u have finally become Div-1. maybe this means that ur lucky number is 1. :)
•  » » » 5 years ago, # ^ |   0 Yep you are right 1 is my lucky number also I have contribution 111 on my 111 contest :D :D
•  » » 5 years ago, # ^ |   +3 congratulation! :D
•  » » 5 years ago, # ^ |   +3 I try to say congratulations to you, from rating update, but there is a message issue :(
•  » » » 5 years ago, # ^ |   0 Thanks :)
•  » » » » 5 years ago, # ^ |   +3 You're welcome :)
 » 5 years ago, # | ← Rev. 2 →   +1 Please can anyone give the proof for why the solution for div1 A / div2 C works ?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +5 You can prove by induction.Let's consider that for all arrays with sizes n' < n it is true that the next algorithm Alg is optimal:1) Sort an array.2) Divide an array from left to right, taking at each step first element.Suppose we have an array a and it's size n. res = Alg(a). Let's sort it and divide by any index q. By induction we know that it's optimal to use Alg for these subarrays. But it's easy to see that the result sum  ≤ res.
 » 5 years ago, # |   0 Why did I get WA even when I used long long for sum?? http://codeforces.com/contest/462/submission/7590781
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 sum+=(F[i]*F[i])*1LL;When F[i] = 100000 , (F[i]*F[i])*1LL = 1410065408 when you have declared F[] as an int array (I tried it on custom invocation)Hence overflow !
•  » » » 5 years ago, # ^ |   0 What change will u suggest?
•  » » » » 5 years ago, # ^ |   0 sum += F[i] * 1LL * F[i];
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 Either declare F as long long F[SIZE] or elsedo sum += ((long long)F[i]*F[i])Edit: Or you can do as in the above comment
•  » » » » » 5 years ago, # ^ |   0 Your approach still does not work ??http://codeforces.com/contest/462/submission/7597974
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 You have written (ll)(F[i]*F[i]) but I suggested ((ll)F[i]*F[i])
•  » » » » » » » 5 years ago, # ^ |   0 Still not working ... plz help me outhttp://codeforces.com/contest/462/submission/7598137
•  » » » » » » » » 5 years ago, # ^ | ← Rev. 3 →   0 read my reply to your question bellow.7597800
•  » » 5 years ago, # ^ |   0 you should multiply 1LL by first operand in F[i]*F[i]. but it's easier to declare your variable 'long long' instead of 'int'.
 » 5 years ago, # |   0 How is Div2 E supposed to be solved?
 » 5 years ago, # |   0 What is the purpose of custom invocation ?How can we lock our solution ? What is its advantage?
•  » » 5 years ago, # ^ |   0 Custom invocation: in case you're too lazy to actually get a compiler/interpreter of your language of choice and want to test out codes with Codeforces platform.Locking solution: You can now hack other solutions for possible points if you're correct.
 » 5 years ago, # |   0 This is my submission for : Div 2 CIt passed tests for similar sized inputs but failed on the 24th test case. I've used Python 2.7 to submit that. Isn't it unfair that I have been penalized just for using Python? My algorithm uses a priority queue and is O(nlogn)
•  » » 5 years ago, # ^ |   0 Here is exactly the same algorithm used in Java 8. Submission in Java 8I have used the SAME algorithm and it comfortably passed the tests.
•  » » » 5 years ago, # ^ |   0 Yes, when you see large input, don't rely on Python. You can blame the problem setters for having no better problem to put where every language can pass, or you can try learning a faster language. I decided to pass on this contest for the same reason.
•  » » » » 5 years ago, # ^ |   0 Well there should be some sort of additional time for Python to process large inputs then. I lost out on a lot of points because of that. I think the organizers of the contest should look into it. Nevertheless, I think I will use Java from the next round. It's quite frustrating to lose out on points just because of a language choice!
•  » » » » » 5 years ago, # ^ |   0 I think there was a discussion about giving time limit multiplier (so Java has double time, Python has triple time, etc) long time ago, but it hasn't been pursued ever since.
•  » » » » » » 5 years ago, # ^ |   0 That's sad! I will Java from now on.
•  » » » » » » » 5 years ago, # ^ |   +5 You should C++ from now on.I had a similar situation recently, but outside a contest. I had a simple integral and binsearching on it, written in Python. But it wasn't accurate enough (I needed to take differences of close values), so I needed to improve the precision by increasing the number of steps. But Python's slow and it would've ran for hours — so I didn't complain that the time limits are slow and instead rewrote the solution in C++, resulting in massive increase in precision (from "powerful random numbers' generator" to "sufficiently accurate") and decent time.Programming is about improving runtime, not increasing time limits to fit your code.
•  » » » » » » » » 5 years ago, # ^ |   0 Thanks for the advice!Is Java also too slow for programming contests on Codeforces and other platforms? I already use Java well so learning C++ will require some additional effort. If it doesn't matter that much then I would rather use Java.
•  » » » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 edit: yet again, doublepost
•  » » » » » » » » » 5 years ago, # ^ | ← Rev. 4 →   0 It probably is, I don't really know since I don't use it, I just heard what people said here. If you can use it well, then it's okay, but it still seems to have more speed-related fails compared to C++.
•  » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 edit: quadruplepost due to CF not responding
•  » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 edit: quadruplepost due to CF not responding
•  » » » » » » » 5 years ago, # ^ | ← Rev. 3 →   0 edit: quadruplepost due to CF not responding
 » 5 years ago, # |   0 :-) Hello
 » 5 years ago, # |   +6 Some stats about hacks can be found here.
•  » » 5 years ago, # ^ |   +3 and here for Div. 1.
 » 5 years ago, # |   0 why my summission is skipped? Your text to link here...