### scipianus's blog

By scipianus, 5 years ago, ,

Hello, Codeforces! On 6th October at 19:30 MSK the Codeforces Round #271 (Div. 2) will take place. Div1 participants can take part out of competition, as usual.

I am Ciprian Olariu (scipianus) from Romania and this is my first round on Codeforces. It is more special as it is held right after I became red on Codeforces. I would like to thank Maxim Akhmedov (Zlobober) and Gerald Agapov (Gerald) for helping me to prepare this round, Delinur for translating the statements and also MikeMirzayanov for Codeforces and Polygon platform.

In this round the main characters will be Mole and Marmot, two good friends, and you will help them in their activites.

Please note that this round will have an experimental duration of 2.5 hours and 6 problems. The scoring will be 500-1000-1500-2000-3000-3000.

I hope you will enjoy the round. Good luck and have fun :)

UPD : To avoid overlapping Topcoder SRM #635 and Bayan 2015 Contest Warm Up, we decided to move round to Monday 19:30 MSK

UPD 2 : The editorial was published here

UPD 3 : Round has finished. Thanks for participating. Congratulations to the winners:

stonebuddha

TakanashiRikka

vanhanh.pham

LOVESY**

•
• +240
•

 » 5 years ago, # |   +42 6 problems? why not add one problem to take place the DIV1? :(
•  » » 5 years ago, # ^ |   0 This is an experimental round format for Div.2, the 6th problem added is an easy one.
•  » » » 5 years ago, # ^ | ← Rev. 4 →   +60 So 6 problems of the contest will be @,A,B,C,D,E instead of A,B,C,D,E,F??? ('@' is the previous character of 'A' in ASCII)
•  » » » 5 years ago, # ^ |   0 the 6th problem added is an easy one So you mean that between problems E and F one of them is easy ???
•  » » » » 5 years ago, # ^ |   +5 I mean that there are 6 problems, sorted by difficulty :P
•  » » » » » 5 years ago, # ^ |   +16 That means the 6th problem added is the 1st one! :p
•  » » 5 years ago, # ^ |   +3 Its sad because most of us will not solve D,E (div1) anyways. We could just do rated "div 1" seperately with last four problems :P
•  » » 5 years ago, # ^ |   +6 even if not adding one more problem, how about using the 6 existing problems like this Div-2 A Div-2 B Div-2 C + Div-1 A Div-2 D + Div-2 B Div-1 C Div-1 D then both divisions will have 4 problems (maybe contest time can be reduced).
•  » » 5 years ago, # ^ |   +8 its experimental round format
 » 5 years ago, # |   +15 Crosses with SRM 635: TopCoder schedule
•  » » 5 years ago, # ^ | ← Rev. 2 →   +14 Wow, so impressive rating graph.
•  » » 5 years ago, # ^ |   0 Fixed now
•  » » » 5 years ago, # ^ |   +19 It now overlaps with Bayan Contest.
 » 5 years ago, # | ← Rev. 3 →   +12 OMG, doesn't Bayan Contest Warm Up round overlap with this?..
 » 5 years ago, # | ← Rev. 3 →   +9 I think the time should be changed because at the same day there would be a Bayan contest and it would be held 2.5 before your contest while it's duration is 3 hours. Edit:oh adamant was faster than me.
 » 5 years ago, # |   +11 And now, the age of 2.5 hours contests...
•  » » 5 years ago, # ^ |   +19 The age of > 5 problem contests; first 270, then bayan, then this.I guess codeforces is showing evolution !
 » 5 years ago, # |   0 Now the date and time should be fine. Sorry for inconvenience.
 » 5 years ago, # |   +10 The contest ID is lucky "474" :DThe contest will be great, hope that!
 » 5 years ago, # |   -12 why without div1
•  » » 5 years ago, # ^ |   +9 What will you do with a div-1 contest ?? :P
•  » » » 5 years ago, # ^ |   -9 it shouldn't touch you
 » 5 years ago, # |   +39 I always attended contests like "Happy New Year Contest" , "April Fool Contest" etc etc . But never attended an "Eid Contest" ;) (Luckily today is Eid Festival here in Bangladesh :) )So , Eid Mubarak to all Programmers :) :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +12 Eid Mubarak to you too _rejectedcoder , hope you will prepare the Eid contest when you become red soon :)
 » 5 years ago, # |   +7 Oct. 4 — SRM 635 Oct. 5 — Bayan Warmup Oct. 6 — CF Round 271.. div2Nice three days :)
•  » » 5 years ago, # ^ |   +42 Dont you mean nic 11 days? :P
•  » » » 5 years ago, # ^ |   +14 Oct. 100 — SRM 1001111011 Oct. 101 — Bayan Warmup Oct. 110 — CF Round 100001111.. div10 Nice three days :)
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   -9 11 is 3 in binary :)
•  » » » » 5 years ago, # ^ |   +8 BTW, Oct 100 might mean 64 to most programmers.
 » 5 years ago, # |   0 Good luck!! I think everyone will enjoy this contest.
 » 5 years ago, # |   +13 It's Eid contest for some contestants :D.Today is Eid(Eid-ul-Azha is the 2nd largest festival of Muslim community) here in Bangladesh including some other parts in the world. And some other countries were observing Eid in last 2/3 days. Happy Eid Mubarak to you all :).
•  » » 5 years ago, # ^ |   +14 Eid Mubarak to you also :)
 » 5 years ago, # |   0 Did anybody receive any emails? 4 Hours to contest and no email for me yet... . Or maybe because I'm div 1? (sry, first unofficial round :D) Luckily I found out through one of my friends.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I think you registered before the e-mails were sent. I guess they send only if you didn't register. Edit: Register for the contest I mean.
•  » » 5 years ago, # ^ |   +3 They don't send div2 contest's notification to Division 1 contestants.
 » 5 years ago, # |   +4 2.5 hours seems a challenge, hope my battery is enough
 » 5 years ago, # | ← Rev. 2 →   +2 All eyes again on worse ...
•  » » 5 years ago, # ^ |   +13 I think he/she is in the friend list of most of us.
 » 5 years ago, # |   0 Denial of judgement??
•  » » 5 years ago, # ^ |   0 Yeah me too :(
•  » » » 5 years ago, # ^ |   0 Denial of judgement too
•  » » » » 5 years ago, # ^ |   0 Me too(((
 » 5 years ago, # |   0 My problem A is now like this I don't know is it hacked.00:03:08 Pretests passed [pretests] → 8107570 However,The hack says 117673 2014-10-06 20:26:22 SINUS waltz7l9 A — Keyboard N/A Ignored What does this means?
 » 5 years ago, # |   0 Why isn't possible to hack using generator file?
 » 5 years ago, # |   0 00:03:08 A Denial of judgement [hacks] Hey ! my points!
 » 5 years ago, # |   0 In C problem, can any 4 moles make a regiment or 4 consecutive moles make a regiment? Please clarify ASAP..
•  » » 5 years ago, # ^ |   +8 There is another place to ask such questions, in the contest itself.
•  » » » 5 years ago, # ^ |   0 Thanks!!! I didn't know such place previously..
 » 5 years ago, # |   +1 Problem E is very interesting, I like it. hope to learn easier solution
 » 5 years ago, # |   0 Can binary search pass the time limits for problem B?
•  » » 5 years ago, # ^ |   0 YES
•  » » » 5 years ago, # ^ |   0 I was thinking of hacking binary search solutions by giving huge test cases but didn't do it.
•  » » 5 years ago, # ^ |   0 I think no.
•  » » » 5 years ago, # ^ |   0 why not?
 » 5 years ago, # |   +1 How do you do D?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +1 Let's f[n] be the number of good sequences with length n. Formula is f[n] = f[n-1] + f[n-k]. Then if g[n] = f[1]+f[2]+...f[n]. Answer to a, b is g[b]-g[a-1].
•  » » » 5 years ago, # ^ |   0 Damn. I was trying to get a closed formula for a given good sequence of length n and then find a closed formula for . I thought a DP might be too slow so didn't entertain the idea.
•  » » 5 years ago, # ^ |   0 It is a dp solution..The recurrence relation is f(i)=f(i-1)+f(i-k)
•  » » 5 years ago, # ^ |   0 If I am correct than we have a recurrence relation:for n and k, where n is the maximum of all (a[i], b[i]) (to be safe n can be set to 100000, the maximum length of sequence) and k is the number of 'W's consecutively.T(n)=T(n-1)+T(n-k)base case T(0)=1, T(1)=1 and for all (n-k<0) T(n-k)=0
•  » » » 5 years ago, # ^ |   0 Would you clarify/prove why the relation is actually correct?It is clear that the first summand in the recurrence corresponds to combinations when 'R' letter is added to combinations derived from T(n-1) step. By it seems that there are more than one way to do it, no?The question is the same for the second summand.
•  » » » » 5 years ago, # ^ |   +1 Think of this problem as the coin change problem. You've got 1 coin of value 1 and 1 coin of value K. What is the number of ways of putting this coins in a row such that their sum is equal to N?I hate dynamic programming. However much I try to understand the concept, I always fail at it.
 » 5 years ago, # | ← Rev. 4 →   +3 What is the 4th pretest in problem E?
 » 5 years ago, # |   +2 What is pretest 3 on D?
•  » » 5 years ago, # ^ |   0 Pretest 3 on D , I guess, is the case when difference of values stored at b[i] and a[i] goes negative. I passed it by adding MOD (1000000007) to the difference.
 » 5 years ago, # |   +2 Can anyone tell me the correct process to hack by generated input. I tried it in two contests. It shows invalid input with this message — "FAIL Expected EOLN (stdin) [validator A_valid.exe returns exit code 3]"
•  » » 5 years ago, # ^ |   0 Same here! Though I've hacked before successfully using a generator.
•  » » 5 years ago, # ^ |   0 Probably you just forget to print the last new line symbol. Hack tests are strict in all whitespace symbols, you just follow the format exactly.
•  » » » 5 years ago, # ^ | ← Rev. 4 →   -21
•  » » » » 5 years ago, # ^ |   +1 You output a space after each number, you should not output the last space.
•  » » » » » 5 years ago, # ^ |   0 Is there any way i can practice hacking ?
•  » » » » » » 5 years ago, # ^ |   +1 No way to practice it outside of contest, if you mean that. Did you try TopCoder approach (separate challenge phase)? Anyway, there is not that much to practice here, just keep in mind that when you are trying to challenge somebody's solution your test will go through a validator which checks its correctness. And validators are very strict in terms of input, every space and new line should be exactly as they are described in the statements.
•  » » » » » » » 5 years ago, # ^ |   0 Thanks a lot :) . I understand now . Though there was no restriction about trailing spaces.
•  » » » » » » 5 years ago, # ^ |   0 Try to get into div-1 , then participate in any div-2 only contest,do first 2 easy problems and have fun of hacking without fear of loss in ratings.
•  » » » » » » » 5 years ago, # ^ |   +7 There is only one problem with this approach — you will get into a room with div. 1 participants only and it becomes more complicated than hacking in div. 2 :-)
•  » » » » » » » » 5 years ago, # ^ |   0 yeah , but he can practice hacking at least.
•  » » 5 years ago, # ^ |   0 Yea i got 4 "Invalid input" errors due to that error, but it worked out this way .. http://ideone.com/apqkIr
 » 5 years ago, # |   0 Tried hacking at the last minute, but I got an 'Invalid Input' error, even though I'm pretty sure that the input format was correct. Do trailing spaces at the end of a line cause that?
•  » » 5 years ago, # ^ |   0 I guess it does :/
 » 5 years ago, # | ← Rev. 3 →   0 Any other solution of E aside the segtree?UPD : sorry i mean E but i wrote D
•  » » 5 years ago, # ^ |   0 DP
•  » » 5 years ago, # ^ |   0 DP.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 How to solve it using segtree? About problem D
•  » » 5 years ago, # ^ |   +1 I used Treap. So, we can add pair (key, prior), where key is the high of smth column, prior — max length of sequence, which have ended in it's column.
 » 5 years ago, # |   0 what is the solution of E?
•  » » 5 years ago, # ^ |   +1
 » 5 years ago, # |   +5 Problem E was in Andrew Stankevich Contest 29 Task B : Financial Softwarethe two problems are almost the same :D
•  » » 5 years ago, # ^ |   +2 why didn't you solve any of them :3
 » 5 years ago, # | ← Rev. 3 →   +9 I implemented everything except for E (even though I have an idea with Normalizing coordinates + DP + 2 Fenwick trees), and I'm very curious about a not so messy solution for E (maybe some greedy may work, not sure though). Anyway thumbs up for the round, scipianus.
•  » » 5 years ago, # ^ |   +13 not so messy — no normalizing and one segment tree instead of 2 Fenwicks.
•  » » 5 years ago, # ^ |   +4 2 Fenwick trees isn't messy at all. You just do all the stuff with LIS twice with small modifications.
 » 5 years ago, # |   0 How I can solve problem C?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +2 Try all the 256 ways to rotate the points inside a regiment and see which one is the best. Backtracking and strong nerves are your friends here. Also knowing how to deal with rotations is very useful.
•  » » » 5 years ago, # ^ |   +4 I can't rotate the points, so ignore this problem :|how rotate the points?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 For rotating I did the following: x,y=x-a,y-b if angle==0: return x+a,y+b if angle==90: return -y+a,x+b if angle==180: return -x+a,-y+b return y+a,-x+b
•  » » » » 5 years ago, # ^ |   +4 cheers (link)
•  » » » » 5 years ago, # ^ |   +3 cheers link
•  » » » 5 years ago, # ^ |   0 I created a solution brute forcing the 256 possibilities, but it kept failing on Pretest2.The only thing to consider while rotating was making sure center was shifted to origin right?Debugging it such problems is hard. :(
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 I didn't solve it but i think it is purely math. For each mole there can be 4 orientations. So for a regiment there can be 256 orientations. Just check all these orientations and output the optimal answer.
•  » » » 5 years ago, # ^ |   0 but problem C is hard than problem D!!!
•  » » » » 5 years ago, # ^ |   +19 Not harder. Just painful to implement and quite prone to errors!
•  » » » » » 5 years ago, # ^ |   +5 mb difficulty(problem) = difficulty(algorithm) + difficulty(implementation) + ... ?
•  » » » » 5 years ago, # ^ |   0 Definitely not, D requires some programming skills and a bit complex things like precomputation, C is straightforward, never mind it took much more of my time.
 » 5 years ago, # |   0 [submission:8118906][submission:8118827] My two submissions for D. I used the recurrence dp[i], if (i-1>=0) dp[i]+= dp[i-1] dp[i]%=MOD if (i-k>=0) dp[i]+= dp[i-k] dp[i]%MODand then summed from a to b using another array. Why is my solution failing ?. Pretest 3 precisely.
•  » » 5 years ago, # ^ |   0 when u printf the last array : arr[b]-arr[a-1], because it is under the modulus it will result wrong answer if arr[a-1]>arr[b] so to avoid this you should say : ((arr[b]+mod)-arr[a-1])%mod
•  » » 5 years ago, # ^ |   0 Because the difference of values at b[i] and a[i] goes negative also!! So add MOD to it.
•  » » 5 years ago, # ^ |   0 :( I spent almost an entire contest trying to make this work but couldn't :(
•  » » » 5 years ago, # ^ |   0 If x is negative after MOD operation, just add the MOD value to it. You could also general formula which should look like this: ((arr[b]-arr[a-1])%mod+mod)%mod
 » 5 years ago, # |   0 Its My first time i Cleared D & E pretest.. Even though its Midsems here i couldnt resist this contest.. Hats of to the problem setter for making this contest so much fun..
 » 5 years ago, # |   +11 I thought that I ignore a content when I read a statement, but... Today's blindness and worms eating were not nice. Really :) What about making more positive problems next time? (Rethorical question)
•  » » 5 years ago, # ^ |   +2 I almost threw up whilst reading the worm eating part :|
 » 5 years ago, # |   0 One of the best Codeforces contests I have ever competed in! The problems were awesome! Kudos to the setters :D
 » 5 years ago, # | ← Rev. 2 →   0 main(){ int i,d=10000-3; cout<
•  » » 5 years ago, # ^ |   0 Of course this is invalid. if(i!=d) in both for loops are printing 1 value less than d. Try changing d=5 and then run it, you should see the problem.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   -6 Thanks...
•  » » » » 5 years ago, # ^ |   +1 Like mosiomohsen said, you shouldn't print the extra spaces.
•  » » » » » 5 years ago, # ^ |   0 Thanks, next time....
•  » » 5 years ago, # ^ |   +1 extra space at the end of the sequence is wrong.
 » 5 years ago, # |   0 Weak pretests for B = Happy happy me :)
•  » » 5 years ago, # ^ |   0 It makes me happy too (9 successful hacks)
 » 5 years ago, # |   0 problem D is easy problem!!!
 » 5 years ago, # |   +7 Mb such contests will reduce rating dispersion (more problems => rating estimation is better). But it will be harder to prepare good round.
 » 5 years ago, # | ← Rev. 3 →   +3 Great round, I enjoyed the problems a lot.(maybe I say this because I solved a lot :P)Edit: reached div1 :D
 » 5 years ago, # |   +21
 » 5 years ago, # |   +2 Tourist scored more than 10k points in this contest. Is this the first time this has happened?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 Well having 6 problems for a div-2 contest isn't that common either.
 » 5 years ago, # |   +90
•  » » 5 years ago, # ^ |   -16 No we don't, Petr and Egor code in Java.
•  » » » 5 years ago, # ^ |   +9 Petr's program that generate code by statement support 3-4 languages.
•  » » » » 5 years ago, # ^ |   +3 Really want to have a look them how to write code.
 » 5 years ago, # |   +55 How does tourist solve all problems in 30mins of which he does the first one in a minute?How can he manage that much reading, typing speed.Does he do screencasts like Petr? I'd love to see a screencast of him competing.
 » 5 years ago, # |   0 http://codeforces.com/contest/474/submission/8116443 why wa on tc 34??
•  » » 5 years ago, # ^ |   0 Really silly mistake, dp[1][1]=(k==1)?1:0; should be done after taking input. But actually this isn't necessary at all. Just initialize the base case for position 0 and loop from 1 instead of 2. The DP value for position 1 should be calculated automatically.
•  » » » 5 years ago, # ^ |   0 Yeah!!Mother of silly mistakes :(
 » 5 years ago, # |   +12 I think this solution should not pass. Maybe the test cases were weak.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +10 fail on test 100000 11 2(99998 times) 3
•  » » » 5 years ago, # ^ |   +6 Yeah, I know that. I just wanted to check if it would pass or not. To my surprise it did. The test cases were too weak I guess!
•  » » 5 years ago, # ^ |   0 it's a funny magic, but the minimum constana is 128 xD, with 127 WA 39, with 128+ AC!
 » 5 years ago, # | ← Rev. 2 →   0 I think 2.5 hours long contest with 6 problems is more enjoyable than 2 hours long contest with 5 problems. Looking forward to participating in more rounds in this format.
 » 5 years ago, # |   0 I hadn't had integer overflow bug for like a year, but now it just came back from E! (I assumed h <= 1E9). Thanks for warning me to be always careful.
 » 5 years ago, # |   0 Problem B: 8122368Time Comlexity: O(mlog(n)).Why TLE?
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 I also used the same idea. Probably the TLE is happening due to using pair in vector. You don't need to push both the starting and ending values, only starting value should suffice. Then BS on that vector. You could look at my solution: 8113015.UPD: Your BS implementation is wrong. It is doing linear instead of binary. Replace u-- with u=mid-1 and l++ with l=mid+1.
•  » » » 5 years ago, # ^ |   0 Using vector doesn't lead to TLE. My binary search is indeed correct and it divides the search interval into half each time, that's an O(log(n)). We have m queries, that's O(mlog(n)) which is sufficient indeed to pass the system test.
•  » » » » 5 years ago, # ^ |   0 I didn't say using vector, I said using pair in vector. But that is not the case here, your BS implementation is wrong and is running in O(n) instead of O(log(n))
•  » » » » » 5 years ago, # ^ |   +40 It's funny that "BS" is often used as an abbreviation for "bullshit". How accurate it is here :D
•  » » » » » » 5 years ago, # ^ |   +3 Right, like not sure if the BS function is actually BS or BS! :D
•  » » » » » » 5 years ago, # ^ |   0 Never encountered that xd. Though I encountered it as short form of Bachelor of Science ; d.
•  » » » » » » 5 years ago, # ^ |   0 This is the funniest thing I have ever seen on codeforces lmao
•  » » » » » » » 5 years ago, # ^ |   0 ayy lmao
•  » » 5 years ago, # ^ |   +8 I think that function "bs" works at O(n). And asymptotics your program O(nm).
•  » » » 5 years ago, # ^ |   0 How does "bs" work at O(n)? Give me a test case to prove your assumption.
•  » » » 5 years ago, # ^ |   +3 It should be u = mid — 1, l = mid + 1. You are indeed correct. Sorry and have a good night.
•  » » 5 years ago, # ^ |   0 I don't think you write a correct binary search. "u--, v++" looks abnormal for me. Should it be something like "u = mid — 1, v = mid + 1"?
•  » » » 5 years ago, # ^ |   +1 What a silly mistake! Thanks bro. Have a good night!
 » 5 years ago, # |   0 Can anyone look into my solution it is giving TLE but i am not able to understand why ??http://codeforces.com/contest/474/submission/8123046
•  » » 5 years ago, # ^ |   0 You are passing vector by value and not by reference in the functions.
•  » » » 5 years ago, # ^ |   0 Got it !! :)
 » 5 years ago, # |   0 I saw successful hacks with test containing char 'q'. Is it valid? I think no.
•  » » 5 years ago, # ^ |   +3 Should be valid as soon as you move to the right of it.
 » 5 years ago, # |   0 EID MUBARAK All the problem solver :)