Hello Codeforces community !
I am glad to announce Codeforces Round 307 (Div. 2) on 12th of June at 19:30 MSK. Authors of this contest are Nikola Mandic (nikola12345) and Aleksa Plavsic (allllekssssa). This is our first round and we really tried to make interesting and solvable problems. Traditionally Div.1 participants can take part out of the competition ( personally I believe that the problems are worth to Div 1 participants, and nobody can solve everything in 20 minutes ). This is the first Serbian round and we want to invite our friends from Serbia to take part in this round and maybe prepare some of next rounds.
The main character of this round is gonna be GukiZ ( our proffesor of computer science ). He really helps us to become better people and developers !
We want to thank Zlobober for help in preparing contest and great advices, Delinur for translating problems statements into Russian and MikeMirzayanov for fantastic Codeforces and Polygon platform !
We wish you great fun, a lot of Successful hacks, Accepted solutions and high rating !
UPD: Scoring distribution: 500 — 1250 — 1750 — 2000 — 2500.
UPD2: Due to technical reasons round was delayed by 10 minutes. Stay tuned!
UPD3: +5 minutes. Thanks for your patience!
UPD4: System testing is complete, but the rating update won't be that fast since we are working on improving our cheater catching system. Thanks for your understanding!
Congratulations to winners!
DIV 1:
1.MrDindows
DIV 2:
1.hrzhrz_hrzhrz
2.slo
3.wangjing
Thanks to all participants. We hope you have a good time and learn something new.
UPD5: Link of editorial !
Okay, let's be finally realistic here: This time I will either jump into Div.1, or I will not.
You are in the "danger zone", good luck!
[user:Ghassan.Khazaal,2015-06-12] is the closest one to Div 1 :)nope, i am closer because i will win the round
nice joke :)
next joke please <3
U lied, mister.
Was that a joke as well?
He said that he's going to win the round. As mentioned above — he did not.
1699.999999999 -> 1700 :) nice mention.
actually 1699.999999999 -> 1699.999999999
and 1699.(9) = 1700 -> 1700
and 1699 + sum(9*10^(-k)) for k = 1..n -> 1700 (n -> inf)
Next Bet Please
I wish good luck to all participants.;)
and all of them same points :)) such a welcome comment
It clashes with Codechef Snackdown is it possible to shift it ?.
http://snackdown.codechef.com/schedule
if you prefer a codechef round to a codeforces round I think...
I wonder whether I_love_Codechef prefer codechef or codeforces round...
dont worry codechef will be loading while this contest happens :)
my homour > INF
That's why I have decided to participate in both :p
Too bad you can't do both.
I will still try to participate in both
Not a good idea according to me, but then maybe YOU can :)
I am such a fool that I waited for codechef snackdown elimination mirror to start till 11 pm, but didn't noticed that official elimination round had already started at 9:30 pm. I noticed it only when I was not able to submit any solution in mirrored contest. This big mistake has costed me 3+ hours of penalty time due to which my rank went beyond 700. If I hadn't made this mistake, my rank would be under 300 and our team would have got T-shirt and would have qualified for finals.
Life can seriously betray you sometimes like this.
i might not be red but i can host a contest and i will do it .... best of luck
It looks like we will have harder division 2 contest than usual. Hopefully it will be not too hard ;)
Congratulations on your first round! Zelim sve najbolje
( personally I believe that the problems are worth to Div 1 participants, and nobody can solve everything in 20 minutes )May I shout out tourist and run away?Really look forward for this contest! allllekssssa helped me a lot to understand problem's editorial with his solution (back when I used to only know Pascal).
First Serbian round! Congratulations setters. :)
One day, we'll have an Indian round too. And I'm looking forward to that day with excitement. Hope it comes soon.
There have been at least two Indian rounds as far as i know :P
http://codeforces.me/blog/entry/12518 http://codeforces.me/blog/entry/13111
Yes I know, but unfortunately I did not start coding when the rounds were held. I want to personally take part in an Indian round as a participant, it'll be a whole new feeling.
Thanks guys ! I hope that we will justify expectations !
We have solutions in Pascal and after contest we will put it in Editorial.
I hope you also have solutions in C++ and Java, to prevent the TL (java) or naive solution due to your time constraints
P.S. Today in Russian Federation celebrates the Day of Russia :)
Challenge for tourist: Solve all problems in 20 mins
I talked with him ! He can't do competition, but he can do virtual contest anytime. Also same chellange can be for Petr, vepifanov and other top participants...
If the problems are so hard, how do you expect div 2 participants to enjoy the round?
If a Div 1 participants can't solve all problems in 20 minutes, it doesn't mean that it is hard
I wonder if there exist a past div2 contest where a div1 contestant managed to solve all the problems in 20 minutes.
for me total time needed to read and understand all five problems is more than 20 minutes
Ignore this comment :)
I found one here. tourist solved all problems within 16 minutes.
There is nothing that tourist can't do.
This round number is 16. tourist Solved this problems in 16 mins.
Its funny tourist even bothers with div 2 sometimes. Give others a chance to win tourist :)
I hope that the problems will be on different topics ...
Next Bet please
"a lot of Successful hacks" :/ I guess this line is not pleasant for me. every-time I saw it on the round announcement, one of my sol got hacked just before the contest end. and when I try to hack someone else's sol I fail.
Then you should be more careful :)
Auto comment: topic has been updated by allllekssssa (previous revision, new revision, compare).
"( personally I believe that the problems are worth to Div 1 participants, and nobody can solve everything in 20 minutes )"
it appears that problem statements will be lengthy and (especially) problems A and B will be implementation problems with lot of cases and variables to handle, that may make these problems, easy but time taking problems.
the earliest scoring distribution ever .
Hi, this is the first time I will participate out of competition. I want to know if my rating will be affected.
no, your rating will not be affected
thanks, mate
I'm surprised by the scoring! It seems that we're gonna have a harder B than usual... :)
Good Luck
I want to get out of the green zone towards blue and purple .
will, I wish to get accepted as possible because I got enough of digging in the newbie area ..
Once I was also deep in newbie, but through regular practice I have managed to participate 5-6 times in Div — 1 (candidate master). One day you will also enter Div — 1 by learning DS and algo, regular practice and by making, "up-solving", your habit.
Seen 5000+ (and still counting) registrants for the first time in Div 2 only contest.
There is 4532 Participants actually, all others are participating unofficial
And its delayed....
And I hate delay
And again. -_-
Lets see how many problems I can solve in first 50 minutes (also participating in codechef snackdown)
How many did u solve? I already got the 2 easy ones...
Don't lie, you only solved 1
I meant in snackdown... lol :)
The best option : Switch back to Snackdown... :)
Damn I hate Delays
Come on! 5 more minutes?! I have a chemistry exam tomorrow.
~800 unrated participants :3
At least they're fair enough to participate with their real account (^_^)
5578 — 800 = 4778
~4778 rated participants Oh My God I'm very Clever
this is more correct
5500 — 800 = 4700
why is this more correct? :p
Great. People, we have yet another delay (+5min this time) :(
And I love delay ):
yes me too,especially when you are writing snackdown contest parallel with it
In Russian, please.
Good luck have fun.
What The Fuck happened?? why these delays??
no need to swear
for fun
Soon contest announcements will have "due to technical reasons, round will actually start on time. Thank you for your understanding!"
Really this last delay?
heeyy , you are not codechef
10 + 5 + 2.5 + ... it's gonna be 20 mins...
It's 1:41 a.m. here in Korea.. Delay means less sleep to me T_T
00100011 00100110 00010000 00010011 00010011 00010000 00100100 00100011
4859 rated contest registration !!! I this its a new record For Div — 2 :D
Are you sure it's for DIV 2 ???
Remove problem A, and it becomes Div1 Only
B was probably too easy for Div1 too, but others are ok.
Spent last 70 minutes on D, almost come to the solution, but lacks of knowledge in combinatorics. Also can't get how to do fast 2^(bignumber) mod 10^9+7.
I've came up to formula: 2^(n * total_bits — 2 * (bits1pos1 + bits1posn) — 3 * (bits1pos2 + ... bits1posn-1)) for each combination of bits1pos1 ... bits1posn-1 where thier sum = amount of bits with value 1 in K.
2^N mod 10^9+7 is actually quite simple, and can be done in O(logN). All you have to do is exploit these two properties,
Ah thanks! So its just usual fast power but with mod addition... So easy :)
yup
This contest was too easy
u know that there are total 5 problems in the contest ri8 and not one !! :p
don't argue with me it was pretty easy (Face with sunglasses)
maybe no body understands sarcasm that's why i decided to leave a post here for u guys to know that i'm obviously being sarcastic ...
Was this serously a div 2 contest? 130 accepts on C 50 Accepts on D and 25 Accepts on E
Possibly you have seen "unofficial" standings. In official Div 2 standings stats are like this:
A->2622 B->416 C->43 D->4 E->6
so I think it was slightly harder Div 2 contest
Thank you for this great round! (no sarcasm here) I've never thought that Div2 rounds may be that tough ;)
Both announcements were so obvious and useless.
How can we solve problem C??
was it a DP?
It can be solved using binary search. If we fix time, we can use greedy to put students from left to right and then compare it to M to check, whether it's possible to make it with this time
That is a great idea but could you explain the greedy part in more detail?
What could be pretest 12 for B?
I could provide a tricky case that let me pass pretest 12
input:
output:
here the maximum is 3 which is ab, ab, ab 3 times not bcd..
this implies when you the possibility of adding string b as well as string c, choose the one with minimum len.
My solution passes this test case, but failed #12 on pretests. I don't think they are related.
Try: aaaaaabbbbbb aba bab
I am getting "bcdababa". Why is it wrong?
when u get bcdababab u are first including string with larger length that is string c, and adding the rest afterwards, while you need to first focus on adding the strings with smaller length if you have the opportunity to add any of them( either b or c).
this works as a tie breaker.
UPD: and as a result will increase answer by a significant amount.
I've got fault on test 12 too and I used that idea about minimum length. And input strings for this test is too long and all I can see is that an optimal solution maximum is 133 and my 129...
This is wrong, actually.
Consider a = "aefaefaef" (3 times aef), b = "aa", c = "aef". If you make the shorter string while you can you'll get 1 "aa" and then you'll have just one "a" to make one "aef". So you'll have one "aa" and one "aef" in total. It can be easily seen that one can make "aef" 3 times, though.
I made the same mistake at first but then figured out it's not always true :). Unfortunately couldn't debug on time the other solution I came up with.
hey u are absolutely correct..
actually breaking tie on length is the 2nd tie breaker.
first you need to add the string one time which can be repeated max number of times.
if in this both the strings can be repeated same number of times then you need to break tie on length of strings.
See my submission 11550880
My solution also passes this case(same output as you)!! But it can't pass case 12!!
I don't know, but try these testcases:
Answers?
I am getting: 1 — babac 2 — abacba 3 — cacaabaabab
Do I have anything wrong?
Thanks in advance!!!
UPD: No idea why my solution is failing!
Your output looks correct to me.
Your answers seems correct.
My own solution passes the #12 pretest (have no problems with it), but failed with runtime error on #23. Yet haven't find the error, but probably it caused by bad i/o, haven't read such a long strings before, not sure about that.
Huh, found error. Its when neither of b and c is substring of a. In my code it was uninitialized result, so it failed on print.
For your second test i get: babaac and it have 'ba'+'ba'+ac = 2. And the answer for deinier was abacba and it is 'abac'+'ba' = 2. what is the criteria in tie case? My solution can't pass test case 12.
Solved with Brute Force :D
Here is my solution: 11559149
Input: aaaaaabbbbbb aba bab
Output: abaabababbab
Looks allllekssssa is fan of PrinceOfPersia
I have solved 2 problems A and B :))))
These cases with L=0&M=1 for D which are not included in pretests... Pure cruelty :)
Have to agree with you. I feel lucky that at least there was a pretest in which K >= 2^L. It was then that I realized that there were special cases (including those you mentioned above) :P.
I am not as fortunate as you. That was the only corner case I handled :'( I though I had it in the bag but missed 2-3 corner cases :'(
I've got one more personal rule: never use constants without MOD inside modular arithmetics code.
What's behing B's pretest 12 ?
Maybe something similar to this..
Input:
aaaaaabbbbbb
aba
bab
Output:
abaabababbab
yes!!! that great!! Thanks!
Thanks. I am failing on that!
How to solve D?
you just need to calculate how many binary numbers with length l,where no 2 1bits together.this all is fib(n+1)*x+(2^l-fib(n+1))*y,where x=number of 1 bits in binary representation of k and y=number of 0.
Not sum, but product, I think, no?
Fn + 1x(2N - Fn + 1)l - x
hey how did you come up with this formula involving Fibonacci numbers.
Is it some less common standard formula or something else?
Thanks in advance. :)
To create digit 0 from N numbers we will start with the first one it can be either 0 or 1 in this digit. The next one can also be 1 if and only if the first is 0, and can be 0 in any case. Now we have three case:
0 -> 1 : the third must be 0;
0 -> 0 : the third can be 0 or 1;
1 -> 0 : the third can be 0 or 1;
The number of the allowed zeros equals the number of all cases in the previous number.
The number of allowed 1 equals the number of allowed zeros in the previous number so it equals the number of all cases in the number before the previous number.
So the number of ways to construct zero is a Fibonacci sequence: 2, 3, 5, 8, 13, etc;
There is log(N) code for precise Fibonacci numbers. It is discussed here in Russian. See my submission 11558240
yes right,you should write dp solution and you will find formula yourself
okay the recurrence is the key.. which I believe would resemble the Fibonacci recurrence.
thanks for replying :)
.
It is a usual problem of last 5 minutes. Live with it.
Very disapointed because of lags on the site at the end of the contest. Was not able to submit my D problem in time because of too long response of site.
the contest ended before time i couldn't submit in last 5 mins constantly got cf is unavailable :(
On this contest I've intentionally solved A in C++ and D in Java to get the achievement "Polyglot" on this site (there was a blog post about it). Now my only hope to get it is to have A && D passed systests :)
UPD NOOOOOO, my D solution has failed system tests :(
Nice Round :)
Worst contest in CF history.
Be positive.
Tasks was interesting, tests was ok. Maybe a bit hard for Div2, but definitely not bad contest.
When there are 761 out of contest (div1) competitors and only 160 correct solutions for C there is something badly wrong... Definitely crosses from good to bad.
Writer with lower rating (like purple) tends to underestimate the difficulties of the problems, having fear to be regarded as too easy by contestants, and the problems actually become harder than usual.
Maybe so, but we have Zlobober for such problems :)
Test cases of Problem B are fun to read. For eg.
Lol good eyes.
I have totally misunderstood B, I was searching for maximum length of concatenated substrings instead of maximum number of substrings and besides that I have passed 12 pretests :D
Сдал Ешку (претесты) sqrt-декомпозицей, потом кое-что поменял и переотправил. Переотправленное решение получило TL. После контеста отправил предпоследнее решение и получил ACCEPTED. :(
I hate this contest because this contest Ever not Normal and very hard ):
P.S. Три раза пытался сделать нормальный размер изображения — не вышло.
which data structure needs to E?
sqrt decomposition
Why O(|a| * 26) solutions on problem B gets TL54?
UPD.Answer here
What a shit contest , fucking aweful :) allllekssssa dont creat contests anymore
It was quiet contest for Div.2 participants.
Задача D сводится к задаче "Сколько существует различных строк длины N, состоящих из символов «0» и/или «1», в которых две единицы не идут подряд?". Эту задачу я хорошо знаю и даже разбирал её на хабре (задача 8).
Ответ на задачу про строки, не содержащие "11" — это число Фибоначчи от n+2. А общее число таких строк — 2 в степени n. Вычитанием получаем число строк, содержащих "11". Если в очередном бите k стоит 1, то в массиве в соответствующих битах должны идти две единицы подряд — то есть умножаем на первое число. Иначе умножаем на второе число.
Число Фибоначчи можно сделать за log(N). http://habrahabr.ru/post/148336/ Разумеется, все операции по модулю n. Быстрое возведение в степень тоже можно делать по модулю n. Дальше всё понятно.
Решение: 11558240. Код чисел Фибоначчи взят с хабры, все операции по модулю m. К сожалению, на контесте забыл проверить, что если m == 1, то ответ 0.
Я долго думал насчет нормальной формулы, но ничего в голову не пришло, зато родилась другая идея. Будем пересчитывать ответ для n через ответ для n / 2. Пусть наша функция возвращает массив ans, ans[i][j] — количество таких комбинаций из нулей и единиц, при которых не встречаются две подряд идущих единицы, начинающихся на i и заканчивающихся на j (0 <= i, j <= 1). Тогда можно пересчитывать ответ за О(1), отдельно разобрав случаи четного и нечетного n (при четном мы просто совмещаем две одинаковых блока, при нечетном вставляем между ними еще цифру). Ответ — сумма всех значений ans[i][j]. Мое решение.
Prob C : Is this a valid test case 4 1 2 3 0 0 Ans : 8 If so should be a good hack !
Rating should be given too much late. Follow topcoder's Rating system.
Thanks to authors for good problemset!
It's good only for div1 not div2.Bcoz it was rated only for div2 and most of the contestant don't solve problem more than 1. problem A and problem B are huge difference.
So, do you want to stay in Div2 forever? You should be able to solve problems like this to get higher in ranks, imo. And this contest was the one, where speed was really important, for example if you managed to solve A only. The problems were quite nice, looking forward for such challenging round further on.
Thanks for the nice problems. Best Div-2 only contest in a while.
Can somebody help me out here? My submission 11555558 for B gives MLE.I have no idea why.I use O(|a|) memory according to me.
And now problemset wouldn't open to check.
I think problem statement's are shit!!
What is the approach for B ??
I tried to find as many of string b as possible and then as many string c, and i tried c then b and printed the one with max non-overlaping substr and didn't work.
this is my code
I did the same and it passed. Ok I am joking,it didnt :). I am really curious to explain us a better programmer the reason.
Brute force solution: try all possible counts of b and calculate count for c. Find the case with max sum of counts for b and c.
11550107
I had troubles solving B, but even had an idea like this, but thought that it is going to TL. Your solution seems clear to me, thanks alot for explaining!
Did exactly the same. I believe there might be a case that fails it, but I couldn't come up with it during the contest, so submitted, and got wa on #12.
It's a very long pre-test, so it's hard to see where your solution goes wrong, I hope the author can explain why this approach fails. ( or someone else).
Maybe something similar to this.. Input: aaaaaabbbbbb aba bab Output: abaabababbab
Here I found it from a user above in the comments. Here we fail :P
Binary search:
Let N be a number of non-overlapping substrings in string a, that are equal to b or c. We want to maximize this number.
Here is the main idea
Ya I did the same But it will not contain all the case example aaaaaabbbbbb aab abb If you go by your approach then the answer would be B: 3 & C: 0 then C: 3 & B:0 which will both give you 3 as final answer whereas the final answer would be 4 B:2 C:2 So you have to take cases like this in consideration
Auto comment: topic has been updated by allllekssssa (previous revision, new revision, compare).
most rating will be decided by how fast we solve problem A
If you have TL54 in B, check int values.You should use long long. Maybe you have such lines with mistake:
You have i <= 1e5 and usedB[j] <=1e5. i * usedB[j] <= 1e10.
Thanks a lot ! Finally i understood where i went wrong !
very nice problems . tanks lot!
Can anyone tell me why my code was too slow for problem B? http://codeforces.me/contest/551/submission/11556052
wow its so complex...
First time reading C, D, E...
What is the expected complexity for problem E? Tell me it's better that
...!
Can be solved in O(Q*√N) using a hash map.
For the problem B i used this idea:
(sorry if it was incorrect. I am not good in maths) and we want the maximum value of: (i+j) How solve this math problem? thanks in advance
This is my first time using C++ in a contest, and I'm having the following issue.
The code for problem D runs correctly on my machine, but when I do the custom invocation, the answer always returns 0.
Any ideas why? Thanks.
Auto comment: topic has been updated by allllekssssa (previous revision, new revision, compare).
Yes,those who are complaining dont want to learn anything and just want good ratings and easy problems
Obviously this contest was harder than usual. Specially B seemed to suit for C and C for D. Whatever, still great contest due to the beauty of the problems.
This contest was great! Many thanks to the authors.
Congratulations to the real winners!
Real Div.2 winners:
slo
sheep
AICoderMike
unkoman
please_delete_account
Indeed. I believe it's better to ignore unrated Div-1 participants while announcing the round winners. It just gives them more motivation.
Just noticed the dreamoon_love_AA test case in B. hahaha
There are more funny tests. Like this:
I wrote all the funny testcases. My friend has nothing to do with it :)
Also I have a lot of funny comments on Serbian ( some comments are about my friend, teachers, or my 'good' english ). I hope nobody feels hurt. I relly hadn't bad intention with testcases !
Is that typo on test #45? I don't know the correct one between grandpa or she. Btw, I'm looking forward for your Pascal solution as you mentioned :)
Zlobober sumbited my Pascal solutions ! Do you see it ?
I like testcase with Egor and tourist :)
Admins ,
I just wanted to say one thing that all these people who participate in their first contests and get into top 5 or top 10 must be banned ! These discourages others who are working to get in top 5 because of these genius div1 players who make fake profiles to just see where they stand in div 2 . For instance in this contest 4 out of top 5 players are those who are playing in their first match and now voila these geniuses are in top 5 :/
Should Petr or ACMonster or vepifanov or rowdark or dreamoon_love_AA be banned? Codeforces isn't the only Online Judge in the world.People can practice in other Online Judges and then particpate in CF.
UPD:In case of misunderstanding,I didn't say multi accounts shouldn't be banned(and I think unrated Div.2 winners in this round is from Div.1).All I say is banning all unrated Div.2 winners is not a good way to prevent multi accounts,I think.
It was a good contest.but I don't know why my B was not accepted. :\ :D good luck!
As per previous comments above, your code won't pass the following test case:
Input: aaaaaabbbbbb aba bab Output: abaabababbab
It assumes that the maximum answer will occur when string b is taken out fully before string c, but the maximum can occur for 'interior' solutions where b and c are not fully removed.
Fix: Find max number of times b can be removed, then iterate through removing 1 to max b's (and any remaining c's per case) and find the instance with largest sum of b and c removed.
I have no idea why this submission gets runtime error on codeforces but runs fine on my local ide and codechef. http://codeforces.me/contest/551/submission/12304739. Please check.