### Um_nik's blog

By Um_nik, history, 6 years ago, translation,

Hello everyone!

Codeforces Round #315 will take place soon. The authors of this round are students of Ural FU Umqra and Um_nik. This is our second round. First one was in the black days of Codeforces and we hope that this will not happen again after our round :)

We want to thank Codeforces team for great Codeforces and Polygon platforms and Zlobober for helping us prepare this round.

Good luck!

UPD1:
Score distribution.
div2 : 500-1000-1500-2250-2750
div1 : 500-1000-1500-2250-2500
We strongly recommend you to read all the problems. We try our best to prepare different problems and some problems that hard for us can be easy for you.

UPD2:
Editorial

UPD3:
Congratulations to the winners!

div1:
1. KAN
2. Petr
3. enot110
4. tonyjjw
5. conflict

div2:
1. Lost
2. loser21
3. Aliquando
4. hqpwca
5. LazyWolfLin

Thank you for participating.

• +289

 » 6 years ago, # |   -53 no, Sex_predator is not my account.. I have one account, dont asking me
•  » » 6 years ago, # ^ |   -69 Joking guys, it's me :D
 » 6 years ago, # |   0 Hope we see interesting and hackable problems in this round :)
 » 6 years ago, # |   +51 One suggestion to Codeforces team, Please do not allow someone to name their handle which has slang or obscene word or may be their handles are part of it. Thanks.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +78 I don't really want to educate anybody here, but "sex" is the main thing why you exist.
 » 6 years ago, # |   +11 where's your previous round? "I don't know what black days are."
•  » » 6 years ago, # ^ |   +2
•  » » » 6 years ago, # ^ |   0 why were those black days? o.O
•  » » » » 6 years ago, # ^ |   +42
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   -20 NICE :)
 » 6 years ago, # |   -8 Good luck to everyone!Wish you high rating! And thanks Umqra and Um_nik for this round! It's good to have another chance to practice more!
 » 6 years ago, # |   0 Here's a suggestion: Please hold more contests at 17:00 ~ 19:00 Moscow time. That time is more available for Taiwanese and Chinese coders. There are many of them!
•  » » 6 years ago, # ^ |   -27 My a suggestion: create platform like codeforces(codeforces asia). And hold contests at 17:00 ~ 19:00 Moscow time. It will be good for participants from Asia.
•  » » 6 years ago, # ^ | ← Rev. 4 →   -94 Jeffrey I dont think that you should say anything trying to separate China. Plz mind your words.
•  » » » 6 years ago, # ^ |   +27 Wow.Didn't expect politics to be brought up on Codeforces.Seriously?
•  » » » » 6 years ago, # ^ |   -63 Don't expect you say strange things on Codeforces.
•  » » » 6 years ago, # ^ |   +1 I agree with you.
•  » » 6 years ago, # ^ |   -80 I agree with I_Love_Bofei. Taiwan is an inalienable part of the territory of China, always. Please be careful what you say.
•  » » 6 years ago, # ^ | ← Rev. 2 →   -77 Jeffrey Taiwan is an inalienable part of the Chinese territory.
•  » » 6 years ago, # ^ |   -13 There will be 2 sites. What wrong with site like codeforces?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +30 You know what's wrong ? there is no 2 Zlobober, so how can we start a round without thanking him in one of the two sites !! mind your words man!
•  » » » » 6 years ago, # ^ |   -12 Of course another site has own cordinators
•  » » » » » 6 years ago, # ^ |   +12 dear -emli-,i think this will help you to fully understand IslamSalah's comment.you're welcome.
•  » » » » » » 6 years ago, # ^ |   -14 Today I will beat both of you on contest
•  » » » » » » » 6 years ago, # ^ | ← Rev. 4 →   +2
•  » » » » » » » 6 years ago, # ^ |   +3 but anyway, i accept your challenge :D
•  » » » » » » » » 6 years ago, # ^ |   -13 and don't use fake accounts
•  » » » » » » » » » 6 years ago, # ^ |   -8 what do you mean?
•  » » » » » » » 6 years ago, # ^ |   0 CHALLENGE COMPLETED :p
•  » » 6 years ago, # ^ |   -49 Taiwan is a part of China... Of course ,don't talk too much about politics
•  » » » 6 years ago, # ^ | ← Rev. 3 →   -35 Speaking from a country clouded by all sorts of censorship, your comment is so trustworthy!Okay I'm kidding, I kind of feel sorry for you,since you've been brainwashed by a corrupted government since your birth :)Of course, I still respect your freedom of neglecting the fact that Taiwan is an independent country and spitting out ignorant comments :)
•  » » » » 6 years ago, # ^ |   -42 I do not think you really don't expect politics to be brought up on Codeforces as you said before. How dare you say Taiwan isn't corrupted? I'm so sorry but what you said is a joke. I won't argue about it anymore because history will give us the satisfied answer like HK and Macao.
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   -50 I have to say something again.Even though we all know Codeforces is not a site for politics.lnishanWe don't need you to feel sorry for anyone.Just feel sorry for yourself.As I was saying,please mind your words. Codeforces is not a place for you to fill with nonsense delusion.So should I guess that you have your own mind and you are not yet another machine used by a stupid government to spread fake things?Time is the judger for what's right and what's wrong.We have our own beliefs and don't you dare say anything about it as we respected you as a man.It's really a waste of time to write so much.DTaiwan is part of China.It has been before.And it will be in the future.AS ALWAYS
•  » » » » » 6 years ago, # ^ | ← Rev. 4 →   0 You're the one being delusional.Feel like googling "Taiwan" and look it up on wikipedia?Oh wait, you can't :) (without using VPN, proxy)This is just pathetic. Oh and, this will be the last comment I made on this topic.Not interested in arguing with some politics zealots.Keep living in your own world where every country is yours essentially.
•  » » » » » » 6 years ago, # ^ |   +4 hahahah, young man, so jump.
•  » » » » » » » 6 years ago, # ^ | ← Rev. 4 →   +10 i mean Inishan is so jump. his words are so impolite, but some people still vote up for him. i dont know why,it is just sarcasm, taunt and discrimination. then pretend to be aloof from politics after saying the words, and use":)" to show his "accomplishment". In a word, Inishan's words are so arrogant, and do his grandparents and ancestor know?I never talk about politics in public places, even this time. but plz mind ur words and be polite to every one. I dont mind my contribution, if u insist on supporting him, a ungratefulness and mean person.
•  » » » » » » » » 6 years ago, # ^ |   0 Does the word "jump" have the same meaning in English?
•  » » » » » » 6 years ago, # ^ |   0 I think you greenese should care about your own problems.. Chinese goverment has done a lot more efficently in past three years than Taiwan in past thirty years. I think you should solve the problems between blue and green first.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +35 I don't know much about Taiwan and China, I just want to say that starting time is a sensitive issue for us all.In Korea, we take 'regular(19:30 MSK)' Codeforces round at 01:30(Of course North Korea would have it 01:00 :p). When the round was at 17:00 MSK, we took it at 23:00, which was really great(you can see me excited here). Even a tiny shift was very convenient for me. However, at the 17:00 MSK contest, many people were embarrassed, as their schedule(job, school, etc.) hadn't ended. Many other shiftings were preferable for some people, and uncomfortable for others. I am lucky too, because it doesn't really overlap with my schedule — it's just too late, and I will probably fall asleep in morning class. Some people might have regular rounds in the middle of their day — for example, New York has it at 12:30.We are competitors from all over the world, yet users of Codeforces. Administrators of Codeforces don't realy have to make equality on opportunity. I personally would really like an early contest, but if it's not preferable, we can't request... I just 'hope'.
•  » » 6 years ago, # ^ |   -38 Taiwan is just a part of China. Why so serious?
•  » » 6 years ago, # ^ |   +9 The point is that earlier contest time is more friendly to coders in East Asia. I wanted to vote 'up' but misclicked it. Sorry bro. :)
•  » » 6 years ago, # ^ |   0 I agree with JeffreyHo. I'm from Vietnam and it is difficult for me to participate in a contest. It is usually held from 23:30pm to 1:30am. So, can you hold the contest earlier?
•  » » 6 years ago, # ^ |   0 I agree with JeffreyHo. I'm from Vietnam and it is very difficult for me to participate in a contest. It is usually held from 23:30pm to 1:30am. So, can you hold it earlier?
 » 6 years ago, # |   0 :))
 » 6 years ago, # | ← Rev. 2 →   0 Hi, simple android app codeforces contest reminder.Maybe will work not correctly with power optimization systems (e.g. sony stamina)P.S. This is my first educational android app, so constructive comments are welcome.
 » 6 years ago, # |   -16 I missed those black days of codeforces,but happy to witness black days of topcoder :) Hope they will overcome too.
•  » » 6 years ago, # ^ |   0 when did that happened ??
•  » » » 6 years ago, # ^ |   0 if you are asking about codeforces black days you can find it here, but if you are asking about topcoder I would say almost every SRMs of topcoder had some issues these days. So, I told it as black days for topcoder.
•  » » » » 6 years ago, # ^ |   +8 You are right.It seems that the little issues that pops out almost every TC round is as critical as the black day's of CF, "which I'v witnessed on my third Round by the way".However I started to get a more fan of TC than CF, hope they work out these issues :D
 » 6 years ago, # | ← Rev. 3 →   0 World Consumer Rights Day Round!
•  » » 6 years ago, # ^ |   0 Happy Skyscraper Appreciation Day :D
•  » » 6 years ago, # ^ |   +9 Today:1) Independence Day in Ecuador2) Day of signing Panama Canal Zone accord3) Day of returning Hong Kong in China4) Day of St. Lawrence5) Day of city in Naberezhnye Chelny, russian city.Are you sure that this round must be named World Consumer Rights Day?
•  » » » 6 years ago, # ^ |   +2 Surely you can give it more funnny name :-P Looking forwart to the round!
•  » » » 6 years ago, # ^ |   +14 Sorry sir. But I have to remind you. The day of Hong Kong's returning isn't today. It was July 1st,1997.
•  » » » » 6 years ago, # ^ |   -15 Yes, but:1994 The last British troops leave Hong Kong. After 153 years of British rule, the island is returned to China.http://www.historynet.com/today-in-history
•  » » » » » 6 years ago, # ^ |   +17 Oh,I was saying that the ceremony was on July 1st,1997. And here in China we remember the date as July 1st,not today.
•  » » » » » » 6 years ago, # ^ |   0 Ok, thank you
•  » » » » » » » 6 years ago, # ^ |   0 but thx for ur remembrance:)
 » 6 years ago, # | ← Rev. 2 →   +19 Your problems in the previous round were very interesting I hope this round will be the same :)
•  » » 6 years ago, # ^ |   +5 We all hope so.
 » 6 years ago, # |   0 This round shuld be called #NotPI :)
•  » » 6 years ago, # ^ |   +1 ceil(PI*100)
•  » » 6 years ago, # ^ |   0 It is better to say round #PI++ :)) *******************************************************
•  » » » 6 years ago, # ^ |   +2 Excuse me, is your key stuck?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   -22 No, in this way people will read my comment. :)
•  » » » » » 6 years ago, # ^ |   +3 And downvote your comment! If you do such stupid things!
•  » » 6 years ago, # ^ |   +5 More like #ICan'tIntoRoundingPi.
 » 6 years ago, # |   -8 This time they told Score distribution SOON ;) THANK YOU |: ################################################################################
•  » » 6 years ago, # ^ |   0 Is it depends on your result in contest?
 » 6 years ago, # | ← Rev. 4 →   0 You know, Div 2 contestants should not compete in Div 2-only rounds....the irony! Edit:I know this is a div1+div2 round, just saying...
•  » » 6 years ago, # ^ |   -6 I know this is a combined round, just saying... No it's not combined round
•  » » » 6 years ago, # ^ |   0 I meant, div1+div2 . Sorry about that.
•  » » » 6 years ago, # ^ |   0 Any particular reason why you copied Dreamoon's photo?
•  » » » » 6 years ago, # ^ |   0 I didn't copy.
 » 6 years ago, # |   +2 "U contest" sounds good to me. Because Organised by "U"mqra and "U"m_nik of "U"ral "U"niversity .
•  » » 6 years ago, # ^ |   -28 fuck "U" sounds nice too.. don't take personally
•  » » » 6 years ago, # ^ |   +9 Were you born to be downvoted?
•  » » » » 6 years ago, # ^ |   -25 no I was born go give pleasure to hot girls. happy ?
•  » » » » » 6 years ago, # ^ |   +1 Why would I be happy? I am not a hot girl :p
•  » » » » » » 6 years ago, # ^ |   0 so hot girl be happy on reading this ? thanks, you are my true friend
•  » » » » » » » 6 years ago, # ^ |   0 Since you were going to give pleasure to hot girl, I assume hot girl will be happy
 » 6 years ago, # |   0 Problem E costs 2750, it going to be interesting!
 » 6 years ago, # |   0 hope to not see Succesful Hacks on Div 1.A :D
 » 6 years ago, # |   +23 I was away from CF for few weeks and what's this? They are no longer declaring the score distribution at last moment! When did people started playing safe?
 » 6 years ago, # |   +16 WTH with A?
 » 6 years ago, # |   +48 ​
•  » » 6 years ago, # ^ |   -70
•  » » » 6 years ago, # ^ |   +10 Very disturbing one!
•  » » » 6 years ago, # ^ |   +5 Xellos I usually like your memes very much but this picture is very distasteful please can you remove it ?
•  » » » » 6 years ago, # ^ |   +4 I don't find it distasteful, I don't care about getting downvotes and since it's getting plenty, it's going to be invisible by default soon, so I don't even need to do anything.And I can't delete the comment at this point anyway.But if you can't bear it existing even hidden, there's always the option of walking away from the screen.
•  » » » » » 6 years ago, # ^ |   -8 Actually, its so "distasteful" that its actually funny :p
•  » » » » » » 6 years ago, # ^ |   0 true :p
•  » » » » » 6 years ago, # ^ |   +3 "I can't delete the comment at this point anyway"Couldn't you edit your comment? Learn from him how to hide your comment. And, "I don't care about downvotes" — means you don't care this community! Mind your words...
•  » » » » » » 6 years ago, # ^ |   -23 Couldn't you edit your comment? "it's going to be invisible by default soon, so I don't even need to do anything" — logic is there if you don't take things out of context "I don't care about downvotes" — means you don't care this community! No.
•  » » » » » » » 6 years ago, # ^ |   0 I was wrong about people always agreeing with Red coders....You were right! :p
•  » » 6 years ago, # ^ |   +7 ?
 » 6 years ago, # |   0 Codeforces is hanging. Can't read codes of roommates.
 » 6 years ago, # |   +2 When B has more solves than A...
 » 6 years ago, # |   +3 Is the answer for DIV1B this sequence?
•  » » 6 years ago, # ^ |   +3 Yes sir, first difference of the bell numbers.
•  » » 6 years ago, # ^ |   +3 yes,it was also 2nd number sequance of bell -_-
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +17 Awesome! Is there anybody here, who discovered this sequence by calculating the answer for 1..5 using bruteforce?
•  » » » » 6 years ago, # ^ |   0 I did :D but no time to impement :D
•  » » » » 6 years ago, # ^ |   +1 I've bruteforced for all n < 7, then OEIS it. Got 2 sequences, first one's formula is a little hard, so I thought second one is what I need. Accepted :D1.
•  » » » » » 6 years ago, # ^ |   0 How did you bruteforced n = 6? It has 2^36 variants to analyze..
•  » » » » » » 6 years ago, # ^ |   0 2^(6*7/2) = 2^21 values.
•  » » » » 6 years ago, # ^ |   0 I tried all sequences, then found thr right one, but I could not implement that.
•  » » 6 years ago, # ^ |   +13 This is why I hate a single-input problem. People that has no idea at all can just do bruteforce, find the several first number of the sequence, google the sequence and get the answer.
•  » » » 6 years ago, # ^ |   +8 There were two sequences corresponding to 1..5 answers. It was difficult to choose between them :)
•  » » » » 6 years ago, # ^ |   +8 no it was not :D you can just make 5 more if and 5 more submission and you will find which one was :D
•  » » » » 6 years ago, # ^ |   +42 After realizing that both sequences are equal it becomes much easier :)
•  » » » » » 6 years ago, # ^ |   0 :D :D :D :D yes much more easier :D
•  » » » » » 6 years ago, # ^ |   0 Exactly! missed it... I need to be more attentive :)
•  » » » 6 years ago, # ^ |   +83 Why do you think this is an approach that should not be available? It looks quite creative and risky to me.
•  » » » 6 years ago, # ^ |   0 It can be even worse than that! The sequence in question is number 4 increasing sequence from the search based just on the 3 given problem examples: https://oeis.org/search?q=1%2C+3%2C+10And the other (wrong) sequences could be rejected by simply copy pasting and running them against pretests. Shame on me, but that's what I did after I failed to "invent" this sequence on my own. Still, bruteforcing via pretests cost me quite a few points.
 » 6 years ago, # |   0 Why 10^9 in div1A is AC? I am about the solution without Sieve of Eratosthenes.
•  » » 6 years ago, # ^ |   0 It's kinda not 1e9, because not all the prime numbers are 1,2*1e6 and if it's like divisible by 2, that is finished in 2 iterations(assuming isprime breaks at right time).
•  » » 6 years ago, # ^ |   0 Actually, it's not 10^9 because of rare up to square root computations.
 » 6 years ago, # |   +21 a bit hard contest , Just a Bit
 » 6 years ago, # |   0 Funnily enough, I solved A but not B. Can someone help me find the bug in my code (I keep getting a runtime error on test 7)? http://pastebin.com/tYXaAaEx
•  » » 6 years ago, # ^ |   +1 try this case maybe you r not checking for numbers out of range 5 5 4 37 4 4
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Thanks! That was the issue. All I had to do was change "<= n" to "<= 100005" in line 25!
 » 6 years ago, # |   0 Guys, why SolveB was easier then A? More people solve B!
•  » » 6 years ago, # ^ |   +7 For me, the description of the problem A was very confusing.
•  » » » 6 years ago, # ^ |   +5 Me too...
•  » » » 6 years ago, # ^ |   +5 Agreed, didn't get the solve because the description was poor.
•  » » 6 years ago, # ^ |   +7 I think that many people didn't think enough on A.
•  » » 6 years ago, # ^ |   0 The authors forgot to mention in problem A that the song continues to download as it's playing. Their mistake is understandable -- what they meant is reflective of real life -- but I can definitely see how it confused people.
•  » » 6 years ago, # ^ |   +1 A becomes more easier when you realize a statement, and much more easier when you realize a solution.
 » 6 years ago, # |   0 How to solve B(div1)?
•  » » 6 years ago, # ^ |   0
•  » » 6 years ago, # ^ |   +5 Let's say that equivalent numbers have same color. And all numbers such that they are not equivalent to themself have color 0. Let Fi be the number of ways you can color n points in exactly i colors. Then it is easy to see that . Now the answer is because order of colors except 0 doesn't matter here.
 » 6 years ago, # |   +11 Problem A has the worst statement i have ever seen in my life, i don't want to ofend you guys, but it was really bad, poorly explained, i don't like to do try/error on contests, even the clarification did not help much either.Overall felt the contest was rushed and not tested enough (statements where not good) that is my opinion , of course people that guess the tasks only by input and output are going to give me negatives, but i don't care, had to speak up.
•  » » 6 years ago, # ^ |   0 I agree with you lol
•  » » 6 years ago, # ^ |   +1 I agree with you about Div2 A, but the rest of the contest seemed ok to me, just a bit harder than usual.
•  » » 6 years ago, # ^ |   0 Definitely agree. The examples didn't make much sense, and the clarification was pretty much exactly the explanation for the example(which was also confusing). Maybe a picture would have helped.
•  » » 6 years ago, # ^ |   0 You are right, problem B was solved by more people than A! I wonder, how hard it was! (I don't know how hard because I am still unable to understand the problem.)
•  » » » 6 years ago, # ^ |   0 I guess A must have a bunch of tricky test cases, so even though I got the statement in one go, I preferred not to submit.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Maybe you are an exception, because tricky cases doesn't affect much in submitting on most of the cases. Take a look at here for an example.
 » 6 years ago, # |   +16 Does anyone have something better than randomization for div1 D?
•  » » 6 years ago, # ^ |   +8 I remember a similar problem being in NWERC 2014, and I solved that one with divide and conquer + heuristic, but it doesn't seem to be possible in this one. The randomisation idea is almost identical, though.
•  » » 6 years ago, # ^ |   +3 Address this comment: http://codeforces.com/blog/entry/19705?#comment-245177
 » 6 years ago, # |   +5 What is solution to Div1C? Is 2-sat involved?
•  » » 6 years ago, # ^ |   +5 Exactly. You can use 2-SAT to check if there is any correct word with given prefix.
 » 6 years ago, # |   +45 That moment,when there are two cheaters in your room and u hack both of them :)
 » 6 years ago, # |   +1 problem statement for problem A.(MUSIC) was very poor had to find meaning from test cases
 » 6 years ago, # |   +16 Why were the TLs in C-Div1 so strict? I lost much time optimizing my 2-SAT in order to pass the pretests. Also, D is very similar to this task on Polish SPOJ: http://pl.spoj.com/problems/AL_09_04/. Translation: There are n points on the plane. Can you cover them using k lines? By the way, has anyone tried solving the problem using meet-in-the-middle technique?
•  » » 6 years ago, # ^ |   +12 tfw you optimise againt TLE and get RE insteadalso tfw I know I'm going to get WA
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 There is no need to iterate through all characters from 'a' to 'z' while finding next symbol. One can observe that we can change any vowel to other vowel, and any consonant to other consonant, and the status of the transfromed string will be the same, e.g. whether it's in language ot not. So, finding next symbol requires exactly two 2-SAT checkings and therefore, you can solve this problem in O(NM),
•  » » » 6 years ago, # ^ |   0 I had this optimization from the very beginning.What I did later was: (a) change the adjacency list in 2-SAT into adjacency matrix, (b) return -1 if M > 3N(N - 1). It worked something like two times faster and it passed pretests. (Of course consonant-only alphabets killed me...)
•  » » » 6 years ago, # ^ |   +1 I wasn't iterating through all characters and still barely managed to fit within TL, spending 35 minutes and 10 attempts to make it :)Rough bound which I got: 200*200*4=160000 rules; 160000*2=320000 edges in my graph. 320000 on DFS + 320000 on RDFS=640000 operations on getting strongly connected components. 200*2=400 calls of 2SAT while looking for LCP of answer and word from input; 200*2=400 more calls of 2SAT while restoring answer.640k*800=5.12*10^8. Quite a lot, now I am not surprised with TL16 :)I am pretty sure that it can be implemented much better (and I'll look at other implementations to learn how to make it faster, thanks to authors), but looking at list of attempts with TL16 during contest — I am not the only one who struggled with it :)At some moment, looking at guys with time <0.1 on pretests, I thought "OK, I screwed up with wasting a lot of time on implementing obvious solution while I had to come up with something smart".:)
•  » » » » 6 years ago, # ^ |   +8 mnbvmar, I_love_Tanya_Romanova, I see you. Indeed, I didn't think straightforward approach could lead to TLE. Sometimes it's better to spend more time to think and use not the very 2-SAT algorithm, but only ideas from it) We can find transitive closure of 2-SAT graph in O(NM) before processing string, and the only information we use from it is reachability from a to !a and vice versa. Now, when we have some prefix, we can fix vertices that must be visited in any case (respective to positions in prefix), and after that, while processing two vertices correspoding to other positions in string, we can use information about reachability to decide whether vertex to use.
 » 6 years ago, # |   +1 Looks like about half of the solutions for div2 A are failing...wow...
•  » » 6 years ago, # ^ |   0 Is this the first time the A problem has had less than half the solves of the B problem?
 » 6 years ago, # | ← Rev. 2 →   -136 O(n^2) space complexity solutions are getting accepted for Div. 1 B ? Like seriously ? EDIT : so wow , much butthurt. I should write these kind of opinions on the complexity of solutions more often just to see the "butthurt impact" it has on people.
•  » » 6 years ago, # ^ |   +17 Why not? n = 4000, n^2 = 16e6?
•  » » 6 years ago, # ^ |   +37 "I can't calculate or try custom test, but it's totally not my fault."your post in a nutshell
•  » » » 6 years ago, # ^ |   -21 Do me/you a favor and multiply that number by 2 and "calculate" the difference between 256 and that number. Then use the acquired info to understand that two arrays of that size + bunch of other stuff won't fit in 256mbs of space.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 You only need binomial coefficients in a 2D array. Why multiply by two?
•  » » » » 6 years ago, # ^ |   0 why "two arrays" ? there is only one 2-d array, another one is linear.
•  » » » » » 6 years ago, # ^ |   -23 I was not going to code "your" solution was I ?
 » 6 years ago, # |   +97 Thanks for the awesome contest (especially D and E)!To get D accepted, I need to add "if (k == 0) return;" to my solution. First I lost Yandex because of a bug in the prime number generation, then this :(
•  » » 6 years ago, # ^ |   +2 What you did wrong in prime number generation?
•  » » » 6 years ago, # ^ |   +24 int n = (int) 1e6; int[] pr = new int[n + 1]; Arrays.fill(pr, 0); for (int i = 2; i * i <= n; ++i) if (pr[i] == 0) { pr[i] = i; for (int j = i * i; j <= n; j += i) pr[j] = i; } 
•  » » » » 6 years ago, # ^ |   -7 and where is bug ? It looks like the algorithm described on wikipedia https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
•  » » » » » 6 years ago, # ^ |   0 for (int i = 2; i * i <= n; ++i)
•  » » » » » » 6 years ago, # ^ |   0 ? On the wikipedia is the same for i = 2, 3, 4, ..., not exceeding √n: , but Petr used trick i*i <= n
•  » » » » » » » 6 years ago, # ^ |   0 For p prime greater than n1 / 2, pr[p] = 0.
•  » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   -16 ~
•  » » » » » » » 6 years ago, # ^ |   0 so all the prime numbers greater than square root won't be processed.
•  » » » » 6 years ago, # ^ |   +8 Ohh, I did the same mistake in Hacker Cup initial round, but first of all experience programmed like you did and specially in final which result in giving you 2nd spot. As I_love_Tanya_Romanova said, you are really unlucky in problem C for last couple of years.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +35 I was actually curious what problems people would see with this code. I see the following: Hardcoding n=1e6 is a bad idea. Had I not done that, I would've noticed the bug on the sample input. Using two different types of special values (pr[i] == 0 and pr[i] == i) to denote the same thing is a bad idea. I should've just filled with pr[i] == i initially. Issue 2 has appeared because I've initially had the code written with boolean array "pr", then converted it to integer array since I needed any divisor in the solution below. Had I thought the solution through before starting coding, this wouldn't have happened. I forget to convert actual pr[i] == 0 special values above sqrt(n) into pr[i] == i — this is the "final bug", but I think it's important to notice the three above issues that have led to it appearing and going unnoticed.
•  » » » » » 6 years ago, # ^ | ← Rev. 3 →   +1 Actually I was also quite surprise by the fact the you initialize the value of array with 0 as default value which is not needed indeed. Then these two things comes into my mind. You started with initializing all the array values with -1 then changed it to 0. You had the boolean array(which is least likely) and changed it to int array as you use IDE so it suggest where you need to change. And btw I think p[i] == i, and initially filling the array value as its index would have been a better idea, it would have reduced your chances of making mistakes but you know better than me and sometimes minor details decide the result.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   -8 If you remove just this line — pr[i] = i; and replace it with if (pr[i] == 0) the resulting array will be filled with 0 for primes and lowest divisors for non-primes.
 » 6 years ago, # |   0 Can someone explain what did DIV 2 A want us to do? I spent around 60+ minutes, and found it very unclear/contradicting. Not complaining about problem statements, but can someone explain it? Not the editorial, but phrase it in a better way.
•  » » 6 years ago, # ^ |   +1 You have to sum the infinite geometric series with the initial value being the current amount downloaded and the rate being (q — 1) / q repeatedly until the current downloaded is greater than or equal to the total length of the song.
•  » » » 6 years ago, # ^ |   0 Thanks chaosagent :)It is a shame for me that I designed this algorithm but discarded it for the reason of precision errors may take place :/I should have tried :|
•  » » » » 6 years ago, # ^ |   0 I actually failed the system tests because of floating point precision... I just deleted a few zeroes and now it works and I am very very pissed off lol
 » 6 years ago, # |   +14 Bad luck!... Get AC after change EPS from 1e-9 to 1e-6 :( ...
•  » » 6 years ago, # ^ |   +8 Integers :)
 » 6 years ago, # |   +8 Waiting for Editorial. I want to see jury solution of Div1. D.
 » 6 years ago, # |   0 Auto comment: topic has been updated by Um_nik (previous revision, new revision, compare).
 » 6 years ago, # |   0 Hoped to stay in Div 1 this time, but because of a really stupid mistake in Div1A, will probably go back to Div 2. :(
 » 6 years ago, # |   0 I only submitted B, and got a rating rise :D
•  » » 6 years ago, # ^ |   0 Actually I believe problem A was Harder than problem B.
 » 6 years ago, # |   0 Auto comment: topic has been updated by Um_nik (previous revision, new revision, compare).
 » 6 years ago, # |   0 it was the worse A that have been prepared !!!!! i solved B in 7 min and C in 20 min But not A !but other problems were fantastic!!! WOW ;)thanks for reading!
 » 6 years ago, # |   +15 Not my best performance, plus part of code editing is hidden under Chrome, but still — screencast
 » 6 years ago, # | ← Rev. 5 →   +30 I had an unusual and impressive experience in this contest. My program for problem C outputs -1 after running about 1.9s. And I allocated a block of memory with the size of 1000000. In my computer, my program only used 1/3 of the memory I allocated. During the contest I tested my program and everything went well. However on the grader, it runs much more faster and used all the memory within only about 1.8s seconds so it got RE before it output -1.
 » 6 years ago, # |   +35 Amount of accepted solutions to A which had "Palindromic tree is better than splay tree" in code is damn too high!
•  » » 6 years ago, # ^ |   0 It's almost like a magical formula that gets solutions AC'd :D
•  » » 6 years ago, # ^ |   0 We've added this phrase just for fun (:
•  » » » 6 years ago, # ^ |   0 Yeah, surely I know, but my point was that having this in code in most cases tells that people don't have an idea what is going on in this task and still managed to produce a correct code :P.
•  » » » » 6 years ago, # ^ |   0 Why take chances, that's why! Suppose some guy solved it without adding that line, and then got pretests failed for some reason, panics and adds that line, just in case it was the reason for wrong answer. Submits again, gets pretests failed again, realizes that line doesn't matter, but still, leaves it there, just to be safe, or maybe cause he forgets to comment it in a hurry.
 » 6 years ago, # |   0 For 569C - Primes or Palindromes?, reading the problem statement, how can one determine — "Up to which number he should calculate the number of prime and number of palindrome number" ?
•  » » 6 years ago, # ^ |   0 Editorial of the contest gives the mathematical proof that n < 107 even for maximum A = 42. So you can run once in your computer for A = 42 precomputing primes upto 107 to get the exact limit .
 » 6 years ago, # |   +9 I forgot to use long long and get Wrong answer in problem 568A. TAT
•  » » 6 years ago, # ^ |   +9 It seems many other people took this mistake too. What a trick!
 » 6 years ago, # |   +1 I can't understand 3rd sample test case in B div1 "B. Symmetric and Transitive"
•  » » 6 years ago, # ^ |   +1 1)empty set 2){x, x} 3){y, y} 4){z, z} 5){x, x}, {y, y} 6){x, x}, {z, z} 7){y, y}, {z, z} 8){x, x}, {y, y}, {x, y}, {y, x} 9){x, x}, {z, z}, {x, z}, {z, x} 10){y, y}, {z, z}, {y, z}, {z, y}
 » 6 years ago, # |   0 What kind of mathematical knowledge should I have to solve such a problem like "A. Music"? I saw the tutorial after the contest and was amazed by the solution which I couldn't work out actually! Yeah I was near, I mean I couldn't reach the percentage formula.
•  » » 6 years ago, # ^ |   0 I just used brute force solution. It passed, of course after contest. :(
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Could finally slove it. Actually I think it's more about Physics than Mathematics.Assuming that there are two main concepts: Time spent on downloading since reaching moment S. (t1) Time spent on listening from the begining. (t2) Now let x be the moment when (t1=t2), we just need to calculate these two periods of time.q is the speed of listening, q-1 is the speed of downloaing.Time=Distance/Speed, which means that:t1=(x-s)/(q-1) t2=x/qt1=t2 -> (x-s)/(q-1) = x/qx=qs is the formula which would get us the moments of "intersecton" of t1 and t2.we just multiply S by q as long as S is less than or equal T, number of Operations would be the answer :)
 » 5 years ago, # | ← Rev. 4 →   0 i think problem "E" can be solved by "divide and conquer & DP". there is a problem with much similar idea ( http://codeforces.com/problemset/problem/101/E ) with my solution ( http://codeforces.com/contest/101/submission/13598464 ) .The basic idea for this problem is to maintain a DP for each index i which store the maximum of length of LCS from i to n. if array has gap at i, then store for every m numbers , otherwise store for only one number array[i]. TimeComplexity : (m*k) which looks fine. Space Complexity : O(m*k+n) ~ 10^8 > 128MB. to resolve this problem, we can divide the array into blocks of size SQRT. now, store all the DP states for 1st Block , then 2nd Block and so on. so Space Complexity : O(sqrt(n)*m) ~ 3*10^7 , which looks passable. decide the bucket size accordingly.Edit : Space Complexity does not passes. looks slightly greater than expected.