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:
LOVESY**
6 problems? why not add one problem to take place the DIV1? :(
This is an experimental round format for Div.2, the 6th problem added is an easy one.
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)
So you mean that between problems E and F one of them is easy ???
I mean that there are 6 problems, sorted by difficulty :P
That means the 6th problem added is the 1st one! :p
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
even if not adding one more problem, how about using the 6 existing problems like this
then both divisions will have 4 problems (maybe contest time can be reduced).
its experimental round format
Crosses with SRM 635: TopCoder schedule
Wow, so impressive rating graph.
Fixed now
It now overlaps with Bayan Contest.
OMG, doesn't Bayan Contest Warm Up round overlap with this?..
Те, кто уже зарегистрировались должны будут повторять регистрацию, или нет?
Что за баг? Минут 20 назад зарегался на раунд, а теперь я зареган на BAYAN
Хрень сморозил.
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.
And now, the age of 2.5 hours contests...
The age of > 5 problem contests; first 270, then bayan, then this.
I guess codeforces is showing evolution !
Now the date and time should be fine. Sorry for inconvenience.
The contest ID is lucky "474" :D
The contest will be great, hope that!
why without div1
What will you do with a div-1 contest ?? :P
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 :) :)
Eid Mubarak to you too _toothless_ , hope you will prepare the Eid contest when you become red soon :)
Oct. 4 — SRM 635
Oct. 5 — Bayan Warmup
Oct. 6 — CF Round 271.. div2
Nice three days :)
Dont you mean nic 11 days? :P
Oct. 100 — SRM 1001111011
Oct. 101 — Bayan Warmup
Oct. 110 — CF Round 100001111.. div10
Nice three days :)
11 is 3 in binary :)
BTW, Oct 100 might mean 64 to most programmers.
Good luck!! I think everyone will enjoy this contest.
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 :).
Eid Mubarak to you also :)
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.
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.
They don't send div2 contest's notification to Division 1 contestants.
2.5 hours seems a challenge, hope my battery is enough
All eyes again on worse ...
I think he/she is in the friend list of most of us.
Denial of judgement??
Yeah me too :(
Denial of judgement too
Me too(((
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?
Why isn't possible to hack using generator file?
00:03:08 A Denial of judgement [hacks] Hey ! my points!
In C problem, can any 4 moles make a regiment or 4 consecutive moles make a regiment? Please clarify ASAP..
There is another place to ask such questions, in the contest itself.
Thanks!!! I didn't know such place previously..
Problem E is very interesting, I like it. hope to learn easier solution
Can binary search pass the time limits for problem B?
YES
I was thinking of hacking binary search solutions by giving huge test cases but didn't do it.
I think no.
How do you do D?
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].
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
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.
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.
What is the 4th pretest in problem E?
What is pretest 3 on D?
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]"
Same here! Though I've hacked before successfully using a generator.
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.
http://pastebin.com/ASAUu3Ld
You output a space after each number, you should not output the last space.
Is there any way i can practice hacking ?
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.
Thanks a lot :) . I understand now . Though there was no restriction about trailing spaces.
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.
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 :-)
yeah , but he can practice hacking at least.
Yea i got 4 "Invalid input" errors due to that error, but it worked out this way .. http://ideone.com/apqkIr
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?
I guess it does :/
Any other solution of E aside the segtree?
UPD : sorry i mean E but i wrote D
DP
DP.
How to solve it using segtree?About problem DI 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.
Задача Е, претест 4, ВА. Как бороться, что я упустил? Много падений на нем было
what is the solution of E?
Read it!
Problem E was in Andrew Stankevich Contest 29 Task B : Financial Software
the two problems are almost the same :D
why didn't you solve any of them :3
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.
not so messy — no normalizing and one segment tree instead of 2 Fenwicks.
2 Fenwick trees isn't messy at all. You just do all the stuff with LIS twice with small modifications.
How I can solve problem C?
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.
I can't rotate the points, so ignore this problem :|
how rotate the points?
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+bcheers (link)
cheers link
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. :(
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.
but problem C is hard than problem D!!!
Not harder. Just painful to implement and quite prone to errors!
mb difficulty(problem) = difficulty(algorithm) + difficulty(implementation) + ... ?
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.
[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]%MOD
and then summed from a to b using another array. Why is my solution failing ?. Pretest 3 precisely.
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
:( I spent almost an entire contest trying to make this work but couldn't :(
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
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..
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)
I almost threw up whilst reading the worm eating part :|
One of the best Codeforces contests I have ever competed in! The problems were awesome! Kudos to the setters :D
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.
Thanks...
Like mosiomohsen said, you shouldn't print the extra spaces.
Thanks, next time....
extra space at the end of the sequence is wrong.
Weak pretests for B = Happy happy me :)
It makes me happy too (9 successful hacks)
При n<=100000. КАК ЖЕ У МЕНЯ БОМБИТ
Совет: делать как минимум +5 к размеру всех массивов. И числа больше 1000 записывать например так 1e5 или так 100*1000, тогда ошибиться будет трудно.
PS хотя может даже и так не упадет, обычно дело как бы.
Упало
Ха, а я установил 1699 :D
problem D is easy problem!!!
Как по мне, задача F легче C
Ну да, структуры данных vs Геометрия 9 класса.
Структуры нужно просто написать, а над геомом надо сидеть и париться
Над чем именно? Над скалярным произведением? Ну ладно, ладно, я зануда :)
:)
Я же сказал — как по мне.
Вот например — как я решал C во время контеста: http://pastebin.com/pDBdBJxa
И фиг пойми, почему у меня вронг
На поверхностный взгляд нет проверки против ромба. Там вообще наверняка 90% WA — ромбы и квадраты не параллельные осям.
Где в условии сказано, что квадрат обязательно должен быть параллелен осям?
Так и не сказано, а многие это писали и претесты оно проходит.
Я писал скалярное произведение на отсечение ромба
Mb such contests will reduce rating dispersion (more problems => rating estimation is better). But it will be harder to prepare good round.
Great round, I enjoyed the problems a lot.
(maybe I say this because I solved a lot :P)
Edit: reached div1 :D
Tourist scored more than 10k points in this contest. Is this the first time this has happened?
Well having 6 problems for a div-2 contest isn't that common either.
No we don't, Petr and Egor code in Java.
Petr's program that generate code by statement support 3-4 languages.
Really want to have a look them how to write code.
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.
http://codeforces.com/contest/474/submission/8116443 why wa on tc 34??
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.
Yeah!!Mother of silly mistakes :(
Задача E. Интересно, я один думал, что последовательность должна начинаться в 1?
Я всегда буду внимательно читать условие, особенно после WA.
Я всегда буду внимательно читать условие, особенно после WA.
Я всегда буду внимательно читать условие, особенно после WA.
Я всегда буду внимательно читать условие, особенно после WA.
Я всегда буду внимательно читать условие, особенно после WA.
Я всегда буду внимательно читать условие, особенно после WA.
Я всегда буду внимательно читать условие, особенно после WA.
I think this solution should not pass. Maybe the test cases were weak.
fail on test
100000 1
1 2(99998 times) 3
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!
it's a funny magic, but the minimum constana is 128 xD, with 127 WA 39, with 128+ AC!
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.
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.
Problem B: 8122368
Time Comlexity: O(mlog(n)).
Why TLE?
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.
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.
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))
It's funny that "BS" is often used as an abbreviation for "bullshit". How accurate it is here :D
Right, like not sure if the BS function is actually BS or BS! :D
Never encountered that xd. Though I encountered it as short form of Bachelor of Science ; d.
This is the funniest thing I have ever seen on codeforces lmao
ayy lmao
I think that function "bs" works at O(n). And asymptotics your program O(nm).
It should be u = mid — 1, l = mid + 1. You are indeed correct. Sorry and have a good night.
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"?
What a silly mistake! Thanks bro. Have a good night!
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
You are passing vector by value and not by reference in the functions.
Got it !! :)
I saw successful hacks with test containing char 'q'. Is it valid? I think no.
Should be valid as soon as you move to the right of it.
EID MUBARAK All the problem solver :)