Hello, Codeforces!
I have the pleasure to invite you to the round #343 which is going to take place on Saturday! This round is consisted of 5 problems and you have 2 hours (as usual) to solve them.
The problemsetters are Mohammad Amin Vahedinia (Me) (MrNull), Daneshvar Amrollahi (dkjsfkhg) and Alireza Tofighi (ATofighi). We would also like to thank Alireza Tofighi (ATofighi) and Ali Asadi (aliasadiiii) for testing this round and Ali Bahjati (LiTi) for helping us preparing this round.
We thank Gleb Evstropov (GlebsHP) for his help in preparing the contest, Maria Belova (Delinur) for translating the statements into Russian, and, of course, MikeMirzayanov for unique Codeforces and Polygon platforms.
This contest's Hero is Famile Door and his friends who are preparing his birthday party!
UPDATE 1: Scoring Distribution is 500 — 1000 — 1750 — 2000 — 2500
UPDATE 2: Editorial is ready HERE
UPDATE 3: System Testing is finished you can see the standings here: standings
Congrats to the div2 Winners:
2. DarthMaul
4. ykaya
5. abcdef6199
Also congrats to the div1 Winners:
1. Um_nik
2. anta
3. Nerevar
4. kmjp
Best of luck to everyone!
A contest by my friends !
Will be interesting ...
cool!!!
happy birthday Mr. FamileDoor in advance...
famile door :D :))))
contest in the third consecutive day, it is mid-night at my time zone, however, I will try my best like all of you here and get advanced to div.1, wish all having good result!
let's hope something realistic and not for exemple N invited (N<=1000000000000) or K candles on the bithday cake where (k<=1e50) !!
Indeed, nothing is realistic in Famile Door’s world :D
I just hope Famile Door can explain his birthday party wishes in a short and direct way :D
For who doesn't know about Famile door, I have to say Famile door is a character in Kolah qermezi TV series (iranian TV for sure).
https://en.wikipedia.org/wiki/Famil-e_Door
The last codeforces before the end of my holiday. better !!
Its recently that I have become purple, so I still like giving DIV 2 :D :P
//
LOL
Cool !
An Iranian contest after months.
Come on PrinceOfPersia !
Can anyone explain how the ratings go up and down for each coder?
http://codeforces.com/blog/entry/102
OMG! The hero of the contest is my favorite character! And also the authors are Iranians :) best contest ever!
The flag of Iran and Famile dooor(I Love him) is up :) Famile dooor always say:"agar darbande dar manand,dar manand...":D ty all guys who prepare this contest <3
It's actually dar manand, by which he means: like a door.
UPD: Although dar manand literally means they will not succeed.
oh yeah,you are right ;) but i should say :" sir dagh.. :P"
How is this relevant to the discussion at hand? Sorry I don't read/speak Persian, so I can't really understand what's written over here :(
The last phrase of the poem is Famil Door's signature. I can't remember a single episode without him saying it.
You are not alone.
Most of the Iranians also don't understand it (like me).
It is a poet of Hafez (a great poetry).
Only the last line is important which is Famil Door's signature.
UPD: And means if you have a problem and God don't help you, you won't be able to solve it...
UPD 2: But I'm not sure about it!
Thanks to authors! Famile Door :)^D
I have to mention that Famil is a door-keeper and he is from a city called Door. I am sure we will see problems about opening and closing some doors :D
I remember preparing a practice contest for my friends, in which I used Famil (and also his wife, Dooreh) for the contest character too! I was about to prepare a CF round, also about Famil. I wish I knew the authors of this round before they announce the contest! Maybe I can help them next time preparing some of easy problems :)
I used to think he is a relative of "aghaye mojri"(a far one :|)
Iranian Contest style and statements are always funny.
I Love he 's son :))
Oh
Another awful Iranian contest
1- you don't have to practice on this contest.
2- when codeforces is going to run this contest , it means codeforces has considered that this contest has the least quality to be the contest of codeforces !
This guy looks creepy af :D
Looks can be deceiving my friend ! He's one of the loveliest puppet characters I can think of.
An attractive hero. So, let's hope an attractive contest :)
I forgot to register LOL
Very good contest!!! Thanks for the round...
I liked problem C.
A<=B<D<C<E
Problem D LIS?
I used segment tree.
D can be solved using seg tree + coordinate compression . Didn't get the time to implement it :(
No need for coordinate compression. D is easy this time.
For such problems, using fenwick tree is better since it takes much less time to implement. It is also easier to learn than segment tree, though not as universally applicable.
I find BIT harder to understand, things are more intuitive when working with segment tree :)
Do you need to know how an aeroplane is made just to take a flight? Sometimes we must use the concept of blackboxing in life.
I thought we are aeroplane makers.
What you say is a really bad way of learning.
LOL. So, you won't fly in an aeroplane unless you know how to make one in your backyard? Does Google maps show you every district, every house on every country on earth, or does does it blackbox most of it untill and unless you zoom in?
I don't say bro, learning algorithms is bs, just mug them up but I say bro, BIT is really cool to use because the code is short, even if you find it confusing, you can still use it
Yes. LIS but on the volumes. Solution 1. Use Binary Search Solution 2. Use Segment Tree.
what is the LIS?
Largest Increasing Subsequence
Longest increasing subsequence
And how this helped to solve problem? The longet do not mean the subsequence with the biggest sum...
No, but try to maximize the volume with the concept of LIS.
Wasted alot of time in problem C trying to find out Catalan Numbers and bunch of nCr's. It ought to be DP. (Why the hell is DP so hard ?)
I feel very happy because yesterday I was learned how to find LIS on good time with indexing tree and now I was solved problem D for my first time :)
I tried hacking on D, with the fact that if PI has < than 17 digits after the decimal point the error will change. Example:
1 10000 10000
real answer = 3141592653589.793238401 (with PI's digits equal to 50)
advitiyabrijesh 's output = 3141592653590.0000000 (with PI's digits = 12)
System verdict:
And the hack was Unsuccessful. . .
"Your answer will be considered correct if its absolute or relative error does not exceed 1e-6."
here the relative error is less than 1e-6.
But the authors solution gives wrong answer. The error is actually 0.206761599 which is larger than 1e-6.
Absolute yes, but relative error is less than 1e-12
Ok, I understood. Thanks :)
Lesson learned — Never hack about precision errors.
The error 10^-6 is relative, not absolute. Therefore, in this case is aproximately 3141593.0 difference allowed.
I was too slow :D
Codeforces servers were pretty good today :)
Problem D : https://e2718281828459045.wordpress.com/2013/09/06/maximum-sum-increasing-subsequence/
Basically just calculate r2h for each cylinder, use this, and multiply the answer by Pi.
I googled that and I didn't find anything...
It didn't feel like a Div.2 contest.
lol what did it feel like?
I problem B , due to my bad internet connection , my code was submitted twice , so I got -50 coz of resubmission How did the judge accept the 2 submissions however they're similar (i.e. why there was no warning for the second submission )? submissions links : 16236771 16236745
your first submission gets skipped
Sure but when I submit the same code twice ,the system should send me a warning (as usual) , this didn't happen in the contest :)
same thing happened with me! mine was worse because i got three consecutive wrong answers! :(
Really nice contest! :)
I liked problem C very much, although I couldn't get all the pretests pass on time... next time, maybe!
there might be a hack on c which s is like ")))))(((((" but i am not sure and i didn't solve the problem anyway.
У кого был WA6 в D? В чём может быть проблема?
Моё решение такое (похоже на поиск наибольшей возрастающей подпоследовательности за nlogn):
Пробегаемся по всем объёмам (не умноженным на PI), храня при этом c++'ный set из пар (V, SUM), которые являются лучшими "ответами" (сам ответ = SUM) для "префикса" тортов до торта с объёмом V, в которых последним взятым тортом является торт с объёмом V. Когда рассматриваю очередной торт, то lower_bound'ом ищу пару (Vcurr, Vcurr), где Vcurr — объём текущего торта, "уменьшаю" итератор на 1. получаю пару (Vlast, SUMLast). В сет пихаю пару (V, SUMLast + V).
во время каждой итерации отслеживаю максимальный ответ, который в конце и вывожу (умноженный на PI). В начале в сете хранится пара (0, 0).
Когда пихаешь пару (V, SUMLast + V) нужно пройтись вперёд и поудалять пары, которые стали бесполезными (у которых sum <= SUMLast + V). Так сохранится возрастающая последовательность.
PS: я юзал map, с set нужно ещё смотреть чтобы не было пар с одинаковым первым элементом (lastV)
Если есть пары с одинаковым первым элементом, то при lower_bound'е будет пара доставаться с наибольшей суммой (т.к. set), поэтому это не помешает.
А про удаление лишних пар ты прав. Я думал, что суммы тоже будут упорядочены. Простой контрпример: 1, 10, 2, 9
сет после 4-х итераций будет выглядеть так:
(0, 0), (1, 1), (2, 3), (9, 12), (10, 11)
Можно было просто найти максимальную возрастающую подпоследовательность из r(i)^2*h(i) деревом Фенвика за O(N*log(большого числа~10^12)*logN), что я и сделал
Нет, спасибо, такое я пока не знаю. "Дерево" Фенвика пишется быстрее/проще, чем то, что я описал выше?
Дерево Фенвика — самая простая для написания( не путать с пониманием ) структура данных для поиска "чего-то" на префиксе. Тем более, твое решение не рабочее и представляет из себя жадный алгоритм, который не применим к этой задаче...
Моё старое решение действительно не рабочее, но если удалять лишние пары, то решение полное: 16263744
I always wonder why the System Test doesn't start immediately after the contests ends.
maybe someone need process the hack data.
I have no clue why my code to D does not work on pretest 6, can someone drop a hint? :D http://www.codeforces.com/contest/629/submission/16246045
Problem C has nice hacking testcase (exceeded of memory) :)
I used fixed memory. should I worry about MLE? :)
You got RTE, I saw my mistake 20 seconds before end and I couldn't change it :(
Just needed to make a simple check
diff>=MXto discard the access of the memory outside its limits. I fell from top 200 to top 500. a huge gap. :(AC : 16247743
Why? 2.4*10^8 bytes in bss are allowed. Could you please explain what you mean by memory limit exceed? If you mean negative indexing, then a simple shift by N is enough
No, he defined matrix d[2000][2000] and it should be at least d[2000][10^5+2000].
No, it shouldn't. I got it AC with d[2000][2000]. just used a simple shift trick.
Why on earth do problem setters make C harder than D!!!!
I think it's about opinions because I was learned LIS yesterday and it looks hardly to me but C is dp. There is easy problem that asks how many sequences of given length are correct and it is the same dp but we need extra flag so it's no so hardly :)
I spent 1 hr 30 minutes on C and din't find the recurrence relation. What was the recurrence relation for p? I used
dp[len][reqirement]=dp[len-1][requirement-1]{for an open parenthesis (.....}+ dp[len-2][requirement]{for ().....}
Look, my English is not very good but I will be trying to explain it in best way. The usual dp is dp[position][sum] and we try to move to next position with sum+1 and sum-1. Here we do the same dp[position][sum] but we need to know if we are being on left or right of S (I want to say if we are in P or Q) so flag F will show 0 if we are on left and 1 if we are on right. Each time we have some state(Pos,Sum,F) we try move to state(Pos+1,Sum+1,F) and state(Pos+1,Sum-1,F). And additional, if F is false, means we are on the left we try to move to the right but on same position with state(Pos,Sum+SumOfS,true). Only if we do it we need to know that Sum+MinSumOfS is not negative. Try to check my code, sorry for English :)
Could you give me a pastebin or ideone link to your code?
Yes, I give you — http://pastebin.com/aBHAG8k9
Thanks! And your English isn't as bad as you think(although I should first check whether your explanation matches your code :) )
No problem, I am hoping you understand it!
great explaination .... now it looks very easy for me :) thank you
The difficulty of a problem varies from person to another person. Because we don't train on some topic with the same intensity. So it differs ! e.g. for me C was easier than D.
So you demand the impossible from the problem setter when you say sort them by the difficulty equally for everyone.
Direct implementation of LIS is not even at D's level. Its a B or C.
Для тех, у кого было WA4 в С:
Возможно, это вызвано тем, что сами по себе префиксы
pиp+sудовлетворяет условиюкол-во '(' >= кол-во ')', но для какого-то префиксаp+c, гдеc— префиксs, это условие не выполняется.По крайней мере у меня была ошибка именно в этом и как жаль, что я обнаружил её за минуту до конца, а смог исправить лишь через пять минут после контеста.
Для тех, у кого WA37 по D:
Скорее всего это вызвано тем, что объём верхнего пирога должен быть строго больше объёма нижнего пирога.
Моё решение, например, это вообще никак не учитывает...
UPD: Второй причиной могла стать погрешность. Для решение этой проблемы стоило всё считать в целых числах и лишь при выводе ответа умножать его на Pi.
Как я понимаю, WA37 это погрешность при вычислении числа Пи. 15 знаков мало.
Да вполне достаточно. У меня ровно 15, например.
Как это может повлиять, если нас просят только 6?
Ответ же порядка 1017 * π. Если не делать print(ans * pi), а прибавлять числа, то погрешность может накопиться.
Эм, нет. Дело не в погрешности. Два пирога просто могут иметь одинаковый объём и тогда нельзя один на другой ставить. Да и логичнее было бы посчитать сначала всё в целых и только при выводе ответа один раз умножить на Pi.
У меня в комнате 2 решения упали. Оба по погрешности.
Возможно, вы неправильно смотрите на вещи.
Вот моё решение упало при
52224523173403512.0000000000и52192519806537609.261718750. Вряд ли 3e14 — это погрешность из-за вычисления числа Pi.P.S. Хотя число 3e14 имеет некоторую схожесть с числом Pi... Судьба, наверное.
Что мешает этому тесту ломать и то, и другое решение?
Можно пример решения, которое падает "по погрешности"?
Насколько я понимаю, это: 16245661 Во время контеста я глянул на решение, вроде как, ДО написано без правой границы, т.е. этот случай проверялся.
Таки да, это решение падает именно из-за погрешности.
Хотя ответ сходится с ответом Lo_R_D, так что, видимо, там та же ошибка.
А разве причина не в том, что у нас вычислениям не хватает точности в принципе, и две равные величины отличаются на eps (и могут быть неправильно сравнены)? Проблема ведь в другом) А не в знаках числа PI. Зацени фокус: 16249271
А, так вот где погрешности... Окей, спасибо, теперь понял.
Ты просто переставил местами PI и h?
Как это повлияло на точность?
16242198 = 16242896 cheaters?
Look my blog entry, I one time was reported two cheaters but nobody care unfortunately.
I've seen problem D before : problem.
The same solution will work for it just add a few lines of code .
Why this behaving in odd manner on [codeforces] ?(http://codeforces.com/contest/629/submission/16247940)
so many WAs on test case 37 for problem D! i wish some1 had hacked my solution
I wonder what is this test.
"strictly greater"
Oooooooh. Man I never learn :(
I think it is round off error. Instead of using double for calculation, one should use long ie r^2*h. Then just before printing answer multiple by acos(-1).
That way precision is maintained. I can't believe I made the mistake. Was supposed to be expert today :(
This one might be too.
But I know some who used long long everywhere, but failed because of missing the word "strictly greater".
How do you check for "strictly greater"?
See my solution. I compress all areas (so they are less than N) and just take maximum in prefix (1...new_value[i] — 1). Here, -1 is for counting only strictly less numbers.
You can index every r^2 * h from the given test in increasing order (sorted first), then check the elements with lower index, this way you will never use a cake with the same volume
My accepted solution for problem C (practice) should give RE:
100000 98000 (98000 open brackets)
I corrected this problem in contest (incorrectly) and I got WA :'( while the original code received Accepted
Kill me please
When can I see the changed rating?
I hope soon!!
Can you congratulate top 10, not top 5, please :(
Top 10 is too much. Top 9? XD
So it turns out this code could pass all pretest in last task:
Why? It is because in all tests, if we choose 1 as the root then in each query(a,b) one of them is true:
If we root the tree at 2 or 3 or a random one then pretest will catch this bug.
So is this intended?
Worst feeling in the world: being 2 rating points lower than purple.
1 point here :'(
I know that feel bro :'(
Can someone help me find bug in my solution to C? I cant find it.
http://codeforces.com/contest/629/submission/16248986
i was comparing it to the um_nik's code and i cant see any difference
http://codeforces.com/contest/629/submission/16235943
Could someone tell me what's wrong with my code? Please! I can't understand the bugs with only one for loop. :( 16249539
thank for contest problems is good :D
Edit
Why does both submission give AC?
Correct
Wrong
Test case 100
Every element of this matrix is C.
The other one gives verdict as Skipped not AC
Edited
Iranian contests are unlucky for me :(
But now no claims to the authors
can any body explain problem C elaborately. I was not able to understand tutorials
we count dp[length][balance] = number_of_correct_bracket_sequences_with_balance=balance like dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]. dp[0][0] = 1
then consider length_of_prefix = i (i=0..n-m), it means length_of_suffix = n-m-i. then iterate over balance of prefix (it must be not lower than (minimum prefix balance of string) * -1), so ans += dp[i][current_balance] * dp[n-m-i][current_balance + balance_of_string] (need to process RE).
Can someone explain the solution B? looks to be greedy, sort by start or end, and doing a linear traversal on both male and female intervals does not work? looks to be a standard problem, can someone help please?
First Notice that number of females and males have to be same.So answer is always a' multiple of two. I did it as follow- Make an array of 366 days for male and female separately. take start and end . Increment the array b/w start and end for each gender separately. Then traverse both the array and take max of min of both arrays and multiply by two. Since days are only 366 This method works easily
Good problemset! (specially C)
Hello codeforces, I am having struggle with problem B and i want to solve it alone before looking at editorial but i am really having difficulties with it.Can someone help me out or atleast give me a hint what is wrong with my code?Cheers CODE
Consider this test case:
Your code will answer 4, while the correct answer is 2. You don't consider the fact that the friends who have available time in common with a specific person, might not be available together at all. Try to think of it from a different angle.