### fcspartakm's blog

By fcspartakm, history, 4 years ago, translation, ,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #337 (Div. 2). It'll be held on Sunday, December 27 at 14:05 MSK (Moscow time) and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time!!!

Me and Edvard Davtyan (homo_sapiens) prepared the tasks for this Round.

Great thanks to Gleb Evstropov (GlebsHP) for helping us preparing the contest, to Maria Belova (Delinur) for translating the statements into English and to Mike Mirzayanov (MikeMirzayanov) for the great Polygon platform.

The scoring distribution will be announced later. Good luck everyone!

UPD The start time of the Round is moved on 10 minutes. Score distribution 500-1000-1500-2500-2500

UPD2 Competition completed! Thank you all! Editorial

• +223

 » 4 years ago, # |   -28 Yee this contests digits are prime :-D
•  » » 4 years ago, # ^ |   0 What a nerd ...
 » 4 years ago, # |   +55 Recently homo_sapiens prepared so many round, like a Problem_HULK ! Sorry to say , but description of problems prepared by fcspartakm are really hard to understand. Hope this time , it will be okay !
 » 4 years ago, # |   +83 Really appreciate the effort homo_sapiens is doing here.
 » 4 years ago, # |   -12 As usual, the round starts in the unusual time :)
 » 4 years ago, # |   -13 Worst unusual time ever :(
•  » » 4 years ago, # ^ |   -28 I agree... contest begins when I am at school
•  » » » 4 years ago, # ^ |   -23 So me.. like you.
•  » » » 4 years ago, # ^ |   -33 Really appreciate the effort "homo_sapiens" is doing here.
•  » » » 4 years ago, # ^ |   +50 But it is very suitable for us students in China. :)
•  » » » » 4 years ago, # ^ |   +1 Also suitable for students in India (4:50 pm) :D
•  » » » » 4 years ago, # ^ |   0 I think so too。
 » 4 years ago, # |   +5 GL & HF
 » 4 years ago, # |   +16 Hope to be an expert after #337 div2!Come on,Parco!
•  » » 4 years ago, # ^ |   +2 My brain after reading this comment: M-x replace-string "expert" "candidate master"; M-x replace-string "Parco" "KostikBigOne"
•  » » » 4 years ago, # ^ |   0 rank 300,i think i could be an expert :D
•  » » » » 4 years ago, # ^ |   0 btw,what's wrong with the rating now?
 » 4 years ago, # |   -44 the time for this contest is very bad;please check its url instagram.com/marvi_chocolate3
 » 4 years ago, # | ← Rev. 2 →   -27 It is unusal time. Thanks everyone who participate in this contest.
•  » » 4 years ago, # ^ |   -50 negative to positive.
 » 4 years ago, # |   -48 The scoring distribution will be announced after the contest.
 » 4 years ago, # |   -33 Total: 4206 Contestants: 3959 Out of competition: 247
 » 4 years ago, # |   +6 wtf!!!! the sitre went down!!! i didnt had time to register
 » 4 years ago, # |   +11 The site was down for the last 5 min, i couldn't reg :(
•  » » 4 years ago, # ^ |   +8 you can register now
•  » » 4 years ago, # ^ |   0 You can register now..the contest has been delayed..
 » 4 years ago, # |   -13 I love delay :(( :|
 » 4 years ago, # |   0 Scoring distribution will be announced after the contest?
 » 4 years ago, # |   +12 Been seeing a lot of this recently... ;_;
•  » » 4 years ago, # ^ |   -6 when CF so laggy, you accidentally send the same comment twice.
 » 4 years ago, # |   +34 " UPD The start time of the Round is moved on 10 minutes.". Should be: The start time of the Round is moved on 15 minutes, right?
 » 4 years ago, # |   +45 For most people at UTC+8, it will be the best time forever XDThey will enjoy a real "usual" time contest.Anyway, gl & hf, thanks to fcspartakm & homo_sapiens.
•  » » 4 years ago, # ^ |   +5 I think just like the football ,we should have some round at different time to make people over the world enjoy the happiness that cf brings to us.
 » 4 years ago, # |   +4 Wow, the server is so buggy today. Takes minutes to load pages... Really impacts contest performance and productivity negatively...
 » 4 years ago, # |   0 hacked after locking is this possible
•  » » 4 years ago, # ^ |   +5 Yes.Locking just gives you access to others code. If other person has locked his/her solution then he/she can hack others solution even when other participant hasn't locked his/her solution. So submit only when you are sure.I too realised this during a contest.
 » 4 years ago, # |   +9 WA on test 7 >_<
•  » » 4 years ago, # ^ |   +3 If you are about problem B, try this test on your solution: 5 1 1 1 2 1 Correct answer is 6. I also have a lot of problems with test #7, but i have already passed all system tests with completely different from first implementation.
•  » » » 4 years ago, # ^ |   +6 Hm, my only problem with test 7 was using int32 instead of int64. When changed — AC.
•  » » » » 4 years ago, # ^ |   0 В случае sarvagya3943 ошибка как раз таки в неправильной реализации, а не переполнении переменной.
•  » » 4 years ago, # ^ |   0 problem is with my logic i guess !
 » 4 years ago, # |   +32 A is mad ! O(n) solution would get ac really ? i tried to hack an O(n) solution with 2000000000 but i got UHA :(
•  » » 4 years ago, # ^ | ← Rev. 2 →   +2 I think not. May be he did some constant optimization like this one: 15044253. The complexity of this solution is As far I know, CF allows 4 * 108 operations in one second roughly.And always think twice before hacking any solution for TLE like me! This solution was in my room, but I am not that fool. :)
•  » » » 4 years ago, # ^ |   0 I've seen a lot of times when bad complexities pass, because of marginal optimizations.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +12 You are wrong. CF can make 10^9 operations per 0.6 seconds: 14032294
•  » » » » 4 years ago, # ^ |   +2 Mainly I told about C++.However, it varies on the computation you did in every iteration. But our consideration is only the worst cases.Or may be CF increasing their speed day by day! :)
•  » » 4 years ago, # ^ | ← Rev. 2 →   +7 http://codeforces.com/contest/610/submission/15052683Check this submission I tried to hack. It gave me UHA. It actually failed on systest when codeforces gave the test 2000000000. However when we hack it it gives UHA. Some bug.
 » 4 years ago, # |   0 Fluctuating pupil / specialist . ;(
•  » » 4 years ago, # ^ |   0 Fluctuating pupil :( :P
•  » » » 4 years ago, # ^ |   0 :(Look for garbage value in B. I was getting WA in pretest 3 then i realized that when there is only one minimum then some values will be garbage.
•  » » » » 4 years ago, # ^ |   0 I get WA 7 :(
•  » » » » » 4 years ago, # ^ |   +9 WA 7 is about int overflow, use long (64-bit) data type for calculating a sum.
 » 4 years ago, # |   +8 Don't you just love it when you get hacked in a solution, but your hacker is so nice, he gives you ample time to rectify your mistakes ^_^ .
•  » » 4 years ago, # ^ |   0 Yea that happened with my A. I was first thinking they should have written print -1 when not possible so that it will cover odd case. But i submitted my code without thinking over it. Pretest passed -> Hacked -> AC. :)
 » 4 years ago, # |   0 does pretests of C include all K s?
•  » » 4 years ago, # ^ |   +15 There are people with successful hacks on C.
•  » » 4 years ago, # ^ |   0 Lol,no. Why would they do that
•  » » 4 years ago, # ^ |   0 nope because the person that commented just before u had his C hacked :)
•  » » 4 years ago, # ^ |   0 Nope ... My friend got hacked in problem c for k=0
 » 4 years ago, # |   +3 Isn't the k=0 case in problem c a controversial one ?? Because some consider that there is no solution for it .. while others printed + for it .. U cannot have an orthogonal set over there r8 ??
•  » » 4 years ago, # ^ |   0 Let's just accept the fact that if you got hacked in C, it was because of k=0, and then rectify it.
•  » » 4 years ago, # ^ |   0 The condition was that any two vectors are orthogonal. Since there is only one vector, the condition remains true.
 » 4 years ago, # |   +39 Problem C is very unoriginal: https://en.wikipedia.org/wiki/Walsh_matrix#Formula
•  » » 4 years ago, # ^ |   0 but painful.
•  » » 4 years ago, # ^ |   +9 And D is the most original problem ever :P
•  » » 4 years ago, # ^ |   +8 Sorry for that. I didn't know about that. Actually the legend is true story about me.
 » 4 years ago, # |   0 How to solve pC ? is it gray code or something?
•  » » 4 years ago, # ^ |   +12 i solved it next:start from K = 0, then lets say the vector is + Now for all numbers from 1 to K do next: copy existing vectors for the first half of vectors, duplicate them (i.e. ++ -> ++++, +* -> +*+*) for the second half of vectors, add their reverse (i.e. ++ -> ++**, +* -> +**+)
•  » » » 4 years ago, # ^ |   0 and how to output 2^k answers?
•  » » » » 4 years ago, # ^ |   0 Each time you iterate the cycle I described your number of answers gets doubled. So for K = 0 you have 1 vector '+', for K = 1 you will have 2 vectors, for K = 2 you have 4 vectors and so on.Technically, I solved it using char arrays. And then just pring every char array on its own line
•  » » » 4 years ago, # ^ |   +1 What was the intuition behind this?
•  » » 4 years ago, # ^ |   +1 My solution was:answer for k = 0: (1) (or "+")answer for k:all vectors from (k-1) answer doubled and all vectors from (k — 1) answer doubled, but second half is inverted
•  » » » 4 years ago, # ^ |   0 thanks a lot.
 » 4 years ago, # | ← Rev. 3 →   +22 Hello,can anyone look into my hack #192799? I think there is a problem with the checker maybe? Solution verdict: OK Checker: ok OK. Be happy! Input: 1 Output: + * Answer: ++ +* How can this be correct?
•  » » 4 years ago, # ^ |   0 Print 2^k lines consisting of 2^k characters each.
•  » » » 4 years ago, # ^ |   0 Yes,he printed 2 lines of 1 character but he should have printed 2 lines of 2 character.
•  » » » 4 years ago, # ^ |   0 really this print + * on test 1
•  » » 4 years ago, # ^ |   +30 We are working on this issue.
•  » » 4 years ago, # ^ |   +23 Issue is now resolved, everyone should be happy I suppose)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Can you please open problemset now? It says temporarily blocked
•  » » » 4 years ago, # ^ |   0 It seems that his submission 15050289 was still accepted and he still got 1200 points for that problem?
•  » » » » 4 years ago, # ^ |   +1 Yes. He has a correct solution that works incorrect only in this case, so we decided to keep it accepted.
•  » » » » » 4 years ago, # ^ | ← Rev. 4 →   +10 I accept your decision but I think it is a bit unfair,since it goes against the spirit of competitive programming.It is wrong even if only on one case.What if there is no bug in the checker in the first place,will it still be accepted?Let alone I should get +100 points for a successful hacking.
•  » » » » » » 4 years ago, # ^ |   +6 If there was no bug in the checker in the first place, it would have given me "Wrong answer on pretest 2", then I'd read my code again, find the bug and resubmit. But since it passed pretests, I assumed it was correct and moved on to problem D.I think that what would actually be unfair is get -1200 points on a contest because the checker failed on pretest 2.
•  » » » 4 years ago, # ^ |   0 контест будет нерейтинговым? таблицы изменятся? у tenshi_kanade всё ещё Accepted за C
•  » » » 4 years ago, # ^ |   +8
 » 4 years ago, # | ← Rev. 2 →   +5 @fcspartakm ; There has been solutions to problem A with an O(n) solution, which is getting passed. I tried to hack one with input as 2*(10^9) and it still passed. How is this possible?
•  » » 4 years ago, # ^ |   0 Compiler Optimization most probably.
•  » » » 4 years ago, # ^ |   +3 I don't think that should be allowed. And it's a pretty straightforward O(n). Where the loop runs n/2 times.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 http://codeforces.com/contest/610/submission/15052683This is the link to the submission. It got a WA in systests, and it is giving WA on my system as well for the input for which I hacked. In sys-tests this guy has TLE's on the same code. How come the hack passed?Can you please check this fcspartakm, homo_sapiens, [user:GlebsHP)]?
 » 4 years ago, # |   +21 Em I really do wanna know what is point of retarded hacks like in this contest, a good hack should be one that needs your effort to find test case that is not working, not having no pretests and then first guy, that gets the idea of: Oh, maybe they have no pretests, get like 1500 points?
 » 4 years ago, # |   0 So how do you check intersecting points in D without checking all lines which are in the range?Like you have a horizontal line from -1000 to 1000 and there are 100000 vertical lines in this range — how do you avoid checking every one of them?And if you can't, then the solution complexity is n^2 right? Because if there are 10 horizontal lines who all start from -1000 to 1000 on different Y positions then you still have to check 100000 vertical lines for each of these horizontal lines, right?Tried to optimize my solution for 30 minutes without any luck :(
 » 4 years ago, # | ← Rev. 2 →   0 In problem B, 3 WA on pretest 7 with int, even in JAVA! :( Finally passed it
•  » » 4 years ago, # ^ |   0 Hahaha, the same to me! But TLE instead, and something like 4 times :p. Finally AC
•  » » 4 years ago, # ^ |   0 I got 2 WA with long long :(
 » 4 years ago, # |   +5 During contest my friendlist was behaving weirdly. Did this happen with others?
 » 4 years ago, # |   0 when will the system tests start
 » 4 years ago, # |   +6 Way too much China :P
•  » » 4 years ago, # ^ |   -19 I worked so hard to get over my addiction to chineese food, and now you remind me of it ;_;
 » 4 years ago, # |   0 in problem b the wa was due to the constraints 10^9 not anything else
 » 4 years ago, # | ← Rev. 4 →   0 If I am not wrong, problem C was a variation version of problem TERVEC asked in September Codechef challenge. It is basically printing a Walsh Hadamard Matrix
 » 4 years ago, # |   +11 To the person who answers questions, if I am taking time to ask a question very specific to the problem, I have carefully read the statement and understood as much as I can. After that, if I am still not able to understand, the fault is not always mine.After solving C, I had to wait for 10 minutes on clarification of case k = 0. This penalised my time for D which I could not code in time. I am still not able to understand problem A at all. The contest had good problems. Please be a little more helpful and kind with the statements.
 » 4 years ago, # |   +1 I was able to register only coz of the delay, and luckily, I'm getting a notable jump in ratings this time!
 » 4 years ago, # |   +14 Wake me up, when the ratings change
 » 4 years ago, # |   +1 I should have solved B faster :( one hour for an easy problem is not good...
 » 4 years ago, # |   0 So after 3-4 WA on problem B: Wrong answer on test 53 :\ :(
•  » » 4 years ago, # ^ |   0 You also have to consider the distance between first minimum value and last minimum value.
•  » » » 4 years ago, # ^ |   0 Yeah added that now and got ac now :)
 » 4 years ago, # |   0 Nice fast editorial! Thanks fcspartakm!
 » 4 years ago, # |   0 Good Contest and give me good luck.
 » 4 years ago, # | ← Rev. 2 →   +21 am I the only one who think that D is repeated and very dull problem?maybe the right place for this problem is educational rounds not rated rounds
•  » » 4 years ago, # ^ |   0 Maybe, but it is Div2 and only 123 ppl solved it. So seems very fine :)
•  » » » 4 years ago, # ^ |   0 It was standard task, but I decided to do the third task, new and interesting for me. After nearly two hours of thinking I realized that I am very stupid guy :)
•  » » » » 4 years ago, # ^ |   0 After thinking of C for nearly an hour, I found D an easy task but finally failed to code it out before the contest ended...
•  » » 4 years ago, # ^ |   0 The same with you...And C is just weird someway... I don't think the solution can be called 'algorithm' anyway.
•  » » » 4 years ago, # ^ |   +2 yes, it's "guess the pattern" problem
•  » » » » 4 years ago, # ^ |   0 Can you share your ideas on how you found the pattern?I kept thinking about it but nothing found until I read the Hadamard_matrix
•  » » » » » 4 years ago, # ^ |   +3 I thought I should use the answer for K-1 to compute the answer for K, since the answer for K-1 is 2^(K-1) * 2^(K-1) square and for K it's 2^K * 2^K square then I knew I have to complete the other 3 parts of the square using the first one
•  » » » » » » 4 years ago, # ^ |   +5 Thanks.
•  » » » » 4 years ago, # ^ |   0 Haha, yes. Guessed the pattern, then copied and pasted k times :)
•  » » » 4 years ago, # ^ |   0 It was very well algo based as I did it using DP. Here, have a look at my code: C
 » 4 years ago, # |   +39 ho-jo-bo-ro-lo, the perfect complexity analyzer: 15049767 :)
•  » » 4 years ago, # ^ |   +42 how about this one 2563497 not even a single millisecond margin
 » 4 years ago, # |   0 Its been an hour, still no rating change. They probably caught one cheater at least, because my standings improved by 1.
•  » » 4 years ago, # ^ |   0 My standings improved by like 15 positions since system testing finished :)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Nothing to see here.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Well, my position improved by 2 so that must be the case :)
•  » » » » » 4 years ago, # ^ |   0 If yours improved by 2, then mine should too, you stood better than me.
 » 4 years ago, # |   0 New Year's wish for all year to get rid of problems
 » 4 years ago, # |   +7 where is the rating changes ? :(
•  » » 4 years ago, # ^ |   0 Its coming, just like winters . FYI winters hasn't reached my country yet.
 » 4 years ago, # |   +21 why unoffical Participants still rated ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +9 I think any participant who hack in contest will be rated
 » 4 years ago, # |   +3 Div 1 users got rating changes. For example, Alex_2oo8 went from 2590 down to 2315. Please, you have to correct that...
 » 4 years ago, # |   +3 kingofnumbers got -176 rating change although he's unofficial participant.
•  » » 4 years ago, # ^ |   0 I got -169 and I'am unofficial participant too
•  » » » 4 years ago, # ^ |   +1 all participan hacked still rated
•  » » 4 years ago, # ^ |   0 mb cheats?
 » 4 years ago, # |   +3 Seems ratings are difficult to calculate →_→.
 » 4 years ago, # |   +3 Will this round be unrated ？
 » 4 years ago, # |   +1 Why do I have less rating increase than I had an hour ago?
•  » » 4 years ago, # ^ |   0 Because the ratings calculated earlier included Div 1 unofficial participants who hacked during the contest, and that's not supposed to happen.
•  » » » 4 years ago, # ^ |   +3 Ok, thanks! :) And congrats for getting back to div1 :)
•  » » » » 4 years ago, # ^ |   +3 Thanks!
 » 4 years ago, # |   0 I solved problem A without any wrong ans. But my rating decrease 8. Why?
•  » » 4 years ago, # ^ |   0 Rating is calculated considering time of solving and first successful attempt. And also with some special expected and real positions. To more information click in this link.
 » 4 years ago, # |   +7 WTF is happening to the rating ?It has been saying "System testing 100%" for quite a while now.It seems that the last educational round was also rejudged ???And why did rating changes disappeared ?
•  » » 4 years ago, # ^ |   +15 This round has given me more anxiety than I know what to do with.
•  » » 4 years ago, # ^ |   +5 OK, back to final standings :-)They may take our lives, but they will never take our rating changes :D
•  » » 4 years ago, # ^ |   0 Seems indicative of a zombie apocalypse...
•  » » 4 years ago, # ^ |   +26 It reminds me what happened at the Miss Universe ceremony.Like "You are Miss Universe", and then Here, it's the same but for a "+162" in rating...
•  » » » 4 years ago, # ^ |   +6 Is there any chance the contest is unrated? coz its should not be! What is it with these judges just give the rating and get over it!
•  » » » » 4 years ago, # ^ |   +3 Mike just found a submission that was judged as "cheating", but in the end it was not. Give it some time to recalculate again.
 » 4 years ago, # |   +4 Where have the rating changes gone? They were calculated, then reset because they were wrong, then recalculated, now I come back and they are gone again. What the... ?!?!?!
•  » » 4 years ago, # ^ |   +8 I know it is a strategy to kill us with anxiety :-|English is not my native language
•  » » » 4 years ago, # ^ |   +1 Your English is pretty good. I think that adding that note at the end (or "sorry for poor English") is what makes it look bad.
 » 4 years ago, # | ← Rev. 2 →   +3 Has anybody any information about our ratings? I'm very excited)
•  » » 4 years ago, # ^ |   +4 You shouldnt worry that much , sir. Rating is not the most important thing in your life.
•  » » » 4 years ago, # ^ |   +5 Actually, it is))0)
 » 4 years ago, # | ← Rev. 2 →   +28 Rating change seems to be John Cena. I can't see it.
•  » » 4 years ago, # ^ |   0 ^ We have a winner over here
 » 4 years ago, # |   0 I just can't sleep. I want to be candidate master today ^_^. Give me my rating :D
•  » » 4 years ago, # ^ |   0 Its really not the greatest thing that can happen for you :) Back in the days before colors revolution it was like "I'm in div1 now, yay! Why is there only div2 contests? Finally, a div1 contest! Damn, I'm back in the div2 again." :)
•  » » » 4 years ago, # ^ |   +32 After being rejected from MITACS, EPFL, Google, Jane Street, Microsoft and many more, this is surely the best thing happening in long time. These are not the days before color revolution.Let me celebrate my happiness. I am in love with it :D
•  » » » » 4 years ago, # ^ |   0 Huh, then congrats!
•  » » » » 4 years ago, # ^ |   +8 First they reject you, then you build something so awesome, they buy it for billions of dollars(remember whatsap). Chin up, buttercup! :D And congrats. I am inspired by you :)
 » 4 years ago, # |   0 I love this! :D I check my status it says pupil then i come back after two hours it says i am specialist! Codeforces changing colours of people like colour change on a Christmas tree! :D
•  » » 4 years ago, # ^ |   +3 You are a pupil again.
•  » » » 4 years ago, # ^ |   0 Yea it is switching itself after sometime. When contest goes rated i am pupil when it is unrated i am specialist! :D
 » 4 years ago, # |   +6 Did you re-rate the contest? My rating change seems to be different than it was several hours ago...Also some features on the website don't seem to be present (search). Is it just on my phone or is there some problem on the server?