Hello Codeforces.
I'm honored to announce you, that Codeforces round #326 is gonna take place soon on Codeforces.
Writers are AmirMohammad Dehghan(PrinceOfPersia) and Ali Haghani(Haghani). There will be 6 problems in each division(4 problems are common) and you'll have 2 and a half hour to solve them. I hope you enjoy the problems.
I wanna thank Maxim Akhmedov(Zlobober) for his great helps in preparing this round, MikeMirzayanov for wonderful platforms of Codeforce and Polygon, Delinur for translating problem statements into Russian and MohammadReza Maleki(mruxim) and Ali Bahjati(LiTi) for their great advices (and LiTi again for some graphics).
This is my third round on Codeforces and not the last one, I hope.
This is the last round on Codeforces with Zlobober as coordinator. It was nice working with him. We had a lot of fun and interesting contests during his coordination. I just wanna say: Thank you Maxim for all your contribution to CodeForces community and good luck in the future. After I heard these news, my first guess for the next coordinator was I_love_Tanya_Romanova; But I don't know if CodeForces hires people from out of Russia or not.
The main character of this round is Duff, but you'll also have to help her friend, Malek!
I wish you all high ratings and lots of joy.
Scoring will be posted soon.
GL & HF!
Problems are sorted by the expected difficulty, but we strictly recommend you to read all the problems.
UPD: Scoring is: 750-1000-1500-2000-2500-3000 in Div.2 and 500-1000-1500-2000-2750-2750 in Div.1 .
UPD1: Editorial is published.
UPD2: System test is over. Congratulations to all winners.
Div.1 Winners are:
Div.2 Winners are:
Also congratulations to JoeyWheeler, the only one who solved problem Div.1 D.
Came from gym... tired... was really afraid to be late on this round...
Gym makes my body better and Codeforces makes my brain better!
Really hard week but I'm marchin on to become better & better...
Vote up if you agree that SPORT and PROGRAMMING are really good compatible!!
Now I believed it's Instagram not Codeforces... :/
I've just wanted to share the best part of my life with you guys, to inspire new achievements...
Is it bad desire or what?? :(((
If you DO NOT agree please DO NOT vote down, I'm loosing my contribution :((
Lol. Guess you don't like the "bad boy" image :p
thug life
this is not instagram
let's keep it that way
please :)
THIRD
what does it mean? Zlobober is still alive ;)
Sorry, wrong word.
Damn. I've been laughing at "R.I.P" for about an hour now, and I feel bad for it xD.
Anyways thank you Zlobober! :D
Mother of math contest is coming :v will miss you Zlobober :(
Your first guess seems to be wrong :)
Looking forward to an interesting contest) And I'm also curious about next coordinator)
I heard some people say it's Endagorion.
It sounds good to me too. However, take a look at this comment.
when the entire Codeforces loves you but you love Tanya Romanova :(
How can purple user prepare Div.1 round??
It seems a bit nonsense like grey user preparing Div.2 round...
even red users have difficulty of PrinceOfPersia problems, and u asking if he deserves to prepare round ?
because he is a great coder and Mr Haghani is a legend
it would be awesome contest, just enjoy the contest!
I want to thank Maxim on fantastic work and good contests. I was prepared one round with this great guy and I hope we will meet again :)
GOOD JOB, Zlobober!!!!
very good character ;) hope she dislike math :|
I guess she likes data structures
PrinceOfPersia hates algorithms !!!! how come :D
You dont see his awesome blogs Algorithm Gym and others discussing data structures and segment tree, do you?!
She likes the D. (data structures :))
You're asking for downvotes dude.
I know :D but getting downvotes is more fun than getting upvotes xD
Thats right baby :*
i think if she doesn't like math , she will ask u to help her in math problems :D
codeforces bug ??
Check it now once again ;)
no change !
In my page it shows 154 in Contribution :/
cookie ... :)
I'll be specialist this contest :(
And i had already got used to seeing Zlobber on each round publication. Oh Well!!!
Missed Gerald. Will also miss you Maxim. Even though some people(me included) might not comprehend the amount of work required to be coordinator, we can all agree that you did a great job.
Thank you once again
HackerRank HourRank1 and Codeforces round 326. Tomorrow is gonna be fun!
Look at my day :
school, test from Algebra
HourRank 1 — my third competition as problemsetter :)
Codeforces round 326
Learing logic and prolog for test in Friday
And yes, I missed today TCO SRM — sorry Errichto, my dear friend. School was sabotaging me :(
Сменку не забудь))))
It's the worst idea to write message in Russian, in English blog.
Tough day. I forgive you then.
Who is this "Duff"? :/
:|
Lucky "Malek" :)
why It must be a special person ?
It's Duff beer dude!!! ;)
Designated Ugly Fat Friend
FYI, in Iran we call hot chicks "Duff" ;)
Maybe Hilary Erhard Duff
With all these pictures, it feels more like Instagram than Codeforces :|
Next time better let all the characters be male
Just iranian's know the meaning of duff ;)
But now anyone knows...
We should punish PrinceOfPersia that told them our secret :D
.
Hi I really become glad when see that Iranian Coders prepare a round:) But i have a sugestion for you PrinceOfPersia, Please prepare persian version of problems for iranian coders. Ty hf with The Duff :) :P
I think one of the reasons Cozezilla was built by PrinceOfPersia is the purpose which you stated,
but unfortunately I have no info that why after the first contest the site went a little down till now..
No, my meant was we can see problems in persian language version in this site (http://codeforces.com)
I 'm waiting timer :)
6 задач? Что-то мне сегодня как-то нестандартно.
+ 1:30 system test
I suspect that there are many hacks in today's contest good luck everyone!!!
I agree with you, because it's PrinceOfPersia's contest
wish a duff contest too. :D
Thank you !
Congrats! :D
You're now first in top contributors list.
And also congrats for your gold medal of iranian national olympiad in informatics.
Dear dynamic score
I hate you
Duffy...plz don't sit on ur duff
Duffy..Duffy..Duff :-p
Have I opened CF or Instagram :/
You have opened PrinceOfPersia's blog. :)
Good_luck everyone!!!
Isn't it late enaugh to post scoring?
"Problems are sorted by the expected difficulty, but we strictly recommend you to read all the problems."
Famous statement. I smell a rat!!!
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
no delay until now!
thanks god! i wish it continues!
Did 6 problem rounds become standard ?
CF round 326 Good luck to everyone!!! 3*2=6 :)
Here comes the 10 minute delay :D
Not in my round buddy ;)
In problem C, if I have subsequences (1.2.3),should I connect 1 and 3 after erasing 2.
So satisfying!
awesome revenge :D
What is this gender-fluidity?
I'm going to make a round about amoebas and randomly change gender pronouns throughout the statements!
Seems like Div. 2 C is going to be one of the most hacked problems in Codeforces history...
It also happened to me :[ I am sorry but is it possible for others to hack my solution after I locked it immediately ? In the case the answer is no, how could this happen that after 20 mins of locking the problem, 2 people just hacked it?
Locking your solution doesn't protect it from hacking. It just gives you the ability to hack other people's codes.
So how can I prevent it from getting hacked ?
code the correct solution :p
You mean if it gets hacked, it's because the code couldn't pass all the test cases ?
Alright I got it !
If it gets hacked, it contains some bugs. But if it contains bugs, it may pass systests.
yup !!
Write correct solution
Submitting the right solution haha. If your solution has any failure people will always be able to hack it.
Div 2 Problem D requires PhD in mathematics.
Get PhD in mathematics.
I thought score was dynamic, but it was fixed!
However, its time to get the editorial right now as it is a contest of PrinceOfPersia !! :)
It seems to be a nice contest. Aparently I was to busy with problem F to try all problems but anyway :)
Btw, is there solution faster than
for F?
Good problems .. ))
It was a nice competition, Had fun solving the Problems :).
Does anybody know what was Div2 D pretest 4? Spent half an hour debugging with no success... =(
To pass 4th pretest, you have to use
long long. I wrote#define int long longand passed it.Bloody hell. I guess this will be the last time I tried to use long long only where I thought I needed it...
Got TL in the hardest problem last time because used long long instead of casting to long long only on multiplication. Didn't get place on the top.
So, think twice
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
Задача А div2. У чувака очевидный выход за пределы массива, но на взлом прога выдаёт правильный ответ. Остановите планету, я сойду.
UPD:
Приехали, выход за пределы теперь не бага. Зачем так жить?
Аналогичная проблема была у меня в Div2 B, участник использовал int при ограничениях в 10^12, но программа работала верно. Мистика...
Мое решение по div2 B, в котором я использовал int (13627664), упало не с WA, а с TL. Почему TL, я догадываюсь. Но как оно смогло отработать на некоторых тестах, где i * i точно должно было переполниться? Мистика...
Так и хочется сказать, мол, расслабься, это плюсы :)
Vector, наверняка, вылетел бы. А с обычными массивами, видимо, может иногда и повезти.
За исключением некоторых контейнеров, выход за пределы массива никогда не был и не будет багой. Решение падает, когда происходит выход за пределы памяти, т.е. когда вы попадаете в недоступную зону. Вы можете создать 2 статичных массива подряд и, обращаясь к первому, залететь во второй.
И у меня такое ощущение, что кодефорсес так устроен, что резервирует память с запасом. Хотя я не уверен.
2 times I battle with TLE resulting from scanf vs cin :(. Cin: not even once.
im so eager to know what the test11 is in D2 C, spent almost 2h solving this problem and FAILED!!
Oh my god.what a fast editorial and system testing.
This my AC submission for D2-C: 13635586, with 218 ms. This is my previous submission for the same problem: 13634487, that got TLE.
However, the only difference of the two submissions is the array length. The former has 1M, while the latter has 2M.
Can someone explain this phenomenon? My previous submission should have been AC with around 500-600 ms :(
Edit: nvm, I used cin/cout in the previous submission... :(
only difference is array length? You change cin to scanf buddy. Scanf is faster!
Its not actually because of cin/cout. If your array was 1M length, that means there is no cell of memory in 1M+19, as it has to be. It was a popular hack though!
He uses array 1000100 — length, plz don't comment if you even don't see the code. ><
I think somebody submitted a wrong code for C or D (div1) and now he/she is going to get accepted and the writer is adding some test now. :D Is it right?
How to do div 2C problem?
Div 2 C got TLE only becuase I used cin cout....logic is correct. This shouldn't happen..shouldn't it? The time should be given such that it will get AC irrespective of input method :(
The problem is that in that case, inefficient algorithms with scanf would also pass. Sorry, but you just have to use scanf for large input problems =/ (I had some submissions fail because of that today too...) OR use ios_base::sync_with_stdio(false);cin.tie(false);cout.tie(false);
so... Make the time limit so that Java's Scanner(System.in) would pass? This would allow for much less optimized algorithms in C to get passed.
very easy and noble the pretest, I hate this competition's system
Pretests are good. They permit the whole "hack" system to exist.
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
Good problems, but the jump in difficulty between div1 ABC and DEF was way too big.
My old laptop's battery run out of charge in the last twenty minutes and then I try to edit my code on my mobile phone but finally got a Compile Error...
Eh, my sqrt-decomposition on Div2-E gave TLE :( I was too lazy to code HLD and I didn't want to copy my previous implementation since I don't like copying old codes. Somebody who got AC with sqrt-decomposition?
There's no need for HLD, you only need the same structure as for LCA (except this time storing also the 10 smallest people on the path 2k vertices up from v, not just the 2k-th parent of v). Then, it's just LCA+mergesort.
Ah, I am such an overkiller :D Thanks for the explanation, it seems much easier now! :)
Generally, this tends to be a full replacement for HLD as long as there aren't any updates.
Thanks for sharing that, I will know it in future! And congrats for becoming red again! :)
Speaking of overkill, I used persistent segment trees to solve this problem.
What is HLD. Will not work Heavy Path Decomposition?
Heavy-Light Decomposition. The same thing, a slightly different name.
It will work, but as I mentioned above, it's a total overkill.
I think it's better to swap problem E,div1 and D,div1 and the score of D,div1 being 3000.I mean that the arrangement of the question be like this: A,div2 B,div2 A,div1 B,div1 C,div1 E,div1 F,Div1 and D,div1
this contest learns me this:
all prime divisors of N are not between 2 and sqrt(n) ! just its for testing is it prime or not!
thanks PrinceOfPersia XD !
*sorry it was t not w!
actually you are wrong, and this is one of the reasons so much people got hacked.
For example, consider number 33. It's square + ceil is 6. But the prime divisors are 3 and 11.
50th place! Rating +4, here I come!
UPD: Damn, I never get it right with this new formula.
No it's +25 and many congrats! :)
The contest can get unforgettable if the rating update very soon.
Why this submission gave TLE? (Problem C, Div 2) http://codeforces.net/contest/588/submission/13648330
cin >> a;
due to cin Code needs I/O optimization. Change cin to scanf
I hate when I see this type of comments. Scanf is not faster than cin, not even close on newer versions but cin is synced with scanf as a default since 4.6(?) which means it uses scanf behind the scene. You can use ios::sync_with_stdio(false; în your main function and see the difference.
Do that before any reading and don't use both scanf and can.
I hate such comments like yourth, because SCANF is faster and it is FACT! Example of codes which are simular but not pass with cin and ios::sync!
Code with cin and without cin As you see, it is faster MORE then TWO TIMES!
It's enough to write
ios_base::sync_with_stdio(false);cin.tie(false);cout.tie(false);
at the first of your code and now I think you can get AC with cin/cout.
cin >> a; was giving TLE. I got AC now :/.
Why TLE in test 38??? please, i need help http://codeforces.net/contest/588/submission/13643971
order is NlogN*logN = 10^6 * 20 * 20 Using array instead of set will get it pass
just use scanf instead of cin, here i send your solution
Does it take much time for the contest to be published on your profile? I mean, for the rating change and all that
It usually takes 1 — 2 hours. Bingo! It's there.
It's the first time I take park in a contest. I had to leave a 30 minuntes from the beginning, so I just solved 1 problem. My rating lowered in 62 points. It's kind of funny
Yes it's weird. I think rating on Codeforces depends on previous contests also. That's why even when my ranking was better than other people but still i have a lower rating than them!
Thanks!
This is my submission for Div2B : # 13646742 The logic is the same as given in editorial but for some reason it's giving different answers on my IDE (correct) and CF judge (wrong).
the link: http://codeforces.net/contest/588/submission/13646742
pow function is messing up with your answer Tip:Never use pow function
I solved A and B in Div-2 and passed system test ... Why skipped ??!!!!
Cheating.
You may have Multi ID or Your code may be matched with someone's . That's why thus happens what I am thinking . Same problem happens to me .
May be matched with someone's, but I never cheating :/
Really nice div1E, solved after the contest.
Could someone give me a tip about how I can remove the "Memory limit exceeded" from my code for div.2 E? http://codeforces.net/contest/588/submission/13652236 I tried to make a LCA of sets...
Its strange changing cin (alongwith ios::sync_with_stdio(false);) to scanf worked. Was getting TLE with cin
Have you tried gob ?
Screencast of me failing rounds.
Failing? But you got #4..
#just_grandmaster_thingsLooks like someone got a bit too angry :P
Говно контест!
1) Задачи нифига нерешаемые (за искл. первой и, может быть, второй). 2) Все на одну долбаную тематику, запросы L,R сделай что-нибудь. Не разнообразия, ничего. 3) Большие тайм лимиты, как следствие возможное долгое тестирование после контеста. 4) Сильные претесты — фиг зачеленджишь кого (это видимо, чтобы уменьшить время системного тестирования).
Как следствие из всего этого — решать первый див, только рейтинг сливать. Нет необходимости решать Див1, если ты не можешь решить D,E или F, так как по скорости на A,B,C тебя таргеты все равно обойдут, а потом ты ничо сделать уже не можешь. Только безбожный слив рейтинга.
Уже задолбали делать задачи типо — ну... автор думал месяц над тем как решать какую-нибудь фигню, давай ка мы теперь на контест выдадим (на 2.5 часа), пусть решат, задача ведь простая, решение в 20 строчек.. Где задачи на алгоритмы? На технику? Почему надо мозг вы***ть, чтобы придумать видите ли идею решения. Мы программированием занимаеся или идее-придумыванием?
Ну зачем же так, на одну тематику, есть же еще замечательные задачи "посчитать количество какой-нибудь фигни по модулю 1e9 + 7"!
Как можно одновременно говорить, что все задачи на l, r запросы и при этом там нет алгоритмов, если такие задачи почти всегда чисто структуры данных? :)
Вот в данном наборе. Задача С, имхо, совершенно безыдейное применение стандартного алгоритма. Задача F тоже больше алгоритмическая, чем идейная (всего лишь придумать, как скомбинировать Ахо-Корасик и корневую).
E и F на [L,R], и не надо, говорить, что это не так. И вообще, если их не решать в таких контестах — то делать нечего.
Не знаю про какой ты алгоритм в С, после LCA там непонятно что делать. Объяснишь? Нет такого алгоритма — "...минимумы на пути в дереве..." — фигушки.
В задаче F я полтора часа думал, что делать после Ахо-Корасика, но так и не придумал. И забил на контест. Вот ты говоришь "... Задача F тоже больше алгоритмическая, чем идейная (всего лишь придумать, как скомбинировать Ахо-Корасик и корневую) ..." — ну знаю я и Ахо и корневую, а вот придумать как скомбинировать — не смог, именно идейную составляющую и не поднял, а ты ещё говоришь не идейная, тоже мне ...
P.S. Это ты у нас качок на строки, а я лишь любитель.
Есть такой алгоритм "двоичные подъемы".
т.е. мы будем хранить по 10 минимумов на каждой степени двойки по пути от каждой вершины до корня, так?
Ага.
Я его уже не меньше года знаю и, я так думаю, он очень легко придумывается, если понимать принцип работы двоичных подъёмов. Ну или на худой конец можно использовать мощные структуры вроде Heavy-Light Decomposition или Centroid Decomposition. Первая описана на e-maxx, в том числе с описанием данной задачи.
Ну я не говорил, что это не так. Я хочу сказать, что задачи, в которых запросы на подотрезках — это 95% какие-то структуры, тобишь, алгоритмы.
Я этого не говорил, просто дальнейшая идея, если хорошо понимать и уметь применять эти два алгоритма не должна составить трудностей.
И ещё. Где контесты типо вот таких:
http://codeforces.net/contest/54
Где думать не надо.. Где можно просто занять 6 место в первом диве не напрягая мозг, как я тогда и сделал..
Can anyone offer a brief explanation about problem E please? I really don't know what is the basis of a vector and why the answer is 2 ^ (b.size()) ...