Здравствуй, Codeforces!
Меня зовут Данил Сагунов, и когда-то я был красным... Впрочем, поздравляю всех со Второй Революцией!
Рад сообщить, что в эту субботу, 3 октября в 19:30 MSK состоится Codeforces Round #323 для обоих дивизионов. Задачи для вас придумывали и готовили я и Виталий gridnevvvit Гриднев. Это не первый раунд, в котором мы являемся авторами, и я уверен, что не последний.
В подготовке задач нам помогали мои друзья Максим Neon Мещеряков, Владимир vovuh Петров и Роман Roms Глазов, за что отдельное им спасибо. Благодарю Макса Zlobober Ахмедова за координаторскую деятельность, Михаила MikeMirzayanov Мирзаянова за создание и поддержку систем Codeforces и Polygon, благодаря которым проведение раунда стало возможным, и Марию Delinur Белову за перевод условий задач на английский язык.
Спасибо Владиславу winger Исенбаеву и Александру AlexFetisov Фетисову за прорешивание задач раунда!
Участникам обоих дивизионов будет предложено по 5 задач и 2 часа на их решение. Надеюсь, задачи покажутся вам интересными, а многие из вас сумеют вернуть свой цвет.
UPD В e-mail рассылке была указана неправильная продолжительность раунда. Соревнование будет длиться 2 часа.
UPD2 Раунд успешно завершен! Благодарим всех за участие.
Поздравляем победителей первого дивизиона:
И второго дивизиона:
Мои поздравления fotiIe96, единственному решившему задачу D!
UPD3 Разбор можно найти здесь
Автокомментарий: текст был обновлен пользователем danilka.pro (предыдущая версия, новая версия, сравнить).
Наконец-то Div1... Хотя для меня это уже значения не имеет :)
Предвидится новый рекорд по числу зарегистрированных пользователей)
used to be red :(
I_love_Tanya_Romanova changed his bio on Quora to "Red on Codeforces" from "Winner of SEERC, ACM ICPC finalist" :D
He participates at SEERC, not NEERC
Oh, my bad! I'll change it.
You are wrong — I didn't make any changes in last several days :) These bios are topic-wise, and I had red at CF/TC for CF and TC topics for a long time (while SEERC-related stuff was used for topics like "competitive programming" and "ACM ICPC").
I still think that winning SEERC is not as easy as getting red, even after recent changes — at least you need some good team for SEERC, while for red CF color only your skill matters. Plus you have to solve harder problems :) Maybe our region is not as strong as NEERC, but still you have to compete against other reds...
And I really like these changes — we'll see how it will work out... But right now it added value to red color. Now I have decent chances to lose it soon, while it sounded much harder several days ago :)
Sorry again.... my bad :)
Warm Up ACM ICPC finalist :D
He is so humble, that most people don't appreciate him. I know he mostly says that he is not a genius, that he is not like those other guys who can reinvent an algorithm on the spot in a competition, but it hurts to see people interpret his humility as otherwise. He is damn talented. He is damn hardworking. And he is a very nice person. So please don't say things that seem like you're making fun of him. He under-speaks his achievements. But you shouldn't.
Not Acm Icpc finallist,warm up for regional acm icpc.
In which revolution?!
Good Bye 2015 revolution.
To be honest i don't like previous gridnevvvit's round . Mostly problem statements are not clear at all , non russian speaker like me had a real tough time on those rounds . But i must admit there is tremendous change in recent some Rounds . Problems statement are clear now with explanation . Hopefully it will continue . Recent change on Codeforces make both Div 1 & 2 more interesting . Eagerly waiting to see how rating will change after this round .
When half of the people who prepared the round are Div 2...
Anyway, I am an optimist about the new system. The distribution will get better in time.
my first palindroom contest!
good feeling :D!
This is every contestant's first contest in some way or the other(First contest with Updated rules).
But my first **_palindrome _** contest
Someone dare to ask "Which one is harder, becoming red on Topcoder or Codeforces " .
A lot of reds have been saying its much easier to become red on CF, than being red on topcoder. MikeMirzayanov had a fitting reply to that, and most reds lost the color. So sad.
Will this round follow the new rating formula developed by Mike and his team?
Michael MikeMirzayanov Mirzayanov :D
Tomorrow first day at university & contest round #323 ^^ Hope good rates :)
Auto comment: topic has been updated by danilka.pro (previous revision, new revision, compare).
Я испытываю смешанные чувства при виде div1-раунда, который готовили один едва-едва оранжевый участник и четверо сине-фиолетовых. Чёртова революция...
Good luck to everyone!
First contest with new colors.. Hope this will brings us luck:)
Blue to Cyan....:-( But it looks really inspiring :-)
Back to the original color? I don't think it's a good news for tourist,Petr,vepifanov and rng_58.
Last Challenge was not that tough...Hoping for best for this challenge
More people in Div 2. Nice.
Хахахаха а я хотел на этом раунде стать фиолетовым(оставалось 25пт). Не судьба видимо!
Wow, only about 600 participants in div.1, the pressure is real :D
My new handle : I_lost_my_color
div 1: 600 div 2: 6000
6000 / 600 = 10 :) I love this numbers :)
Welcome back guys :D
Now there's no need for some of div1 users to make fake accounts to participate in div2 contest :D
I think this is the first time where div2 contest will be much challenging than div1. :P
Good luck everyone and may the best return to div1. :D
Could luckX-DLol that's not a good sign :D
sadly , yes :'(
fight for being in div-1 got more interesting .
CRASH!? Or was that only with my computer/internet?
Seems like the round is delayed for 15 minutes
Отчего весь этот шум,
Отчего весь этот гам?
Одно идет мне на ум:
Похоже, сервер упал...
песенка, которую до сих пор подпеваю. Ах как давно это было, ЛКШ:).
P.S. вот ссылочка для тех кто не в теме — тыц
Те, кто не в теме, уже ниже набежали :D
да Вы прям поэт, я так посмотрю.
на этот раз стишок не очень.
delayed ??? server is busy ??? what the **** ???
:( Again delayed 15 min!!!
I should never expect Codeforces round starts on time. T^T.
You should never expect anything on time.
looks like Xellos is yellow.. No troll Xellos?
Yes, I can change my colour at will. For example, I'll be red after this contest.
UPD: Or not. Probably because new rating formula.
Sever is too slow -_- hopefully it will be okay during contest time :)
I hate delay :|
Похоже сегодня будет горячо на контесте. Набежит over 100500 народу жаждущих веруть себе цвет/дивизион/уважение.
Is anyone else unable to access CodeForces at times right before a contest? I don't pretend to know the reason for this, but if the servers do not handle such large amounts of participants well, then we can start a Kickstarter or Patreon to fund for server upgrades. I'm sure many of us wouldn't mind giving a [insert monetary unit] or two for this project.
Scoring?
WOW!!!RECORD registered to Codeforces Round #323 (Div. 2) 7313:)
Am I the only one waiting for score distribution ??
It will be announced shortly before the contest...
8000 participants, nice. Was even 7000 reached before?
No, there was only 6950 on Bayan Thanks-Round (#320).
In fact, in 15 minutes before round we felt like:
too many people are eager to get back their colors!!
Увидел задачи
Задачи скучная математическая фигня. В следующий раз сделайте вместо задачи главу из учебника физики Ландау и Лифшица
Передаю флаг вам в руки.
How to solve Div-2 D
I think we must find all flat parts in region [1,2*n]. Then do LIS in n^2 for each point and see if LIS upto this point+(t-2)*flatpart of this point is the highest
I did that but got a wa at 3 pretest case.
Well, if you append the LIS in the last segment, then maybe it'll pass
My idea(which didn't pass pretest 2) was to split the problem into 2 cases:
If T<=250, then just run LIS algorithm and get the answer.
Otherwise, run the LIS algo on the first n * 250 numbers and get the sequence. Then pick some number close to the end(but not quite at the end): this is your "capped" value. You then treat the other T-250 periods as if the only numbers we selected in them were occurrences of this "capped" value. Then on the last period you can select higher numbers or whatever. This is probably wrong though :P
This isn't wrong, I solved it like this.
If T<=200 just solve with LIS. Else:
For each different value v in the initial sequence, do a LIS in the first n*100 values which only considers values <= v. Then, just repeat v for the middle n*(t-200) numbers. Finally, run LIS for the last n*100 numbers considering only those >= v.
It's pretty fast.
Let us define a graph with 300 nodes with weight of edge (i, j) denoting the length of lis starting with beginning value (not the index) being i and ending value being j.
Now, we want to find a maximum weight walk in the graph of length T. This can be done by matrix exponentiation.
will this work in 1sec ?? . Complexcity of your approach will be (300*300*300)*log10^7 .
Yes, I did make it work in time. You can check my submission.
Notice that you may compress coordinates, it doesn't modifies complexity but will improve your speed by a big factor 3^3 = 27, so your code will be 27 times faster. BTW, My solution was O(n^3)
If T <= 5000, then find the LIS for the A x T array by nlog(n).
Else, find the answer for s1 = A x 5000 and for s2 = A x 5001, then X = s2 — s1.
Result is s1 + (T — 5000) * X;
13386622
Задачу 3 было легко взломать. Лично я набрал 6 успешных взломов. Просто многие пытались сделать невозможное: решить задачу про НОД без НОДа. :) Контр-тест:
У меня третья задача решена без нода, и тест проходит верно. Но асимптотика у меня — n^4. Я ожидаю, что будет TL на финальных тестах.
OMG, оно зашло! Как-то нагло даже.
I saw many people hacked C div2. what is the test?
i hacked using
4
2 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4
My first submission produced wrong answer for this case:
4
10 5 2 2 5 5 1 1 2 1 4 4 2 1 4 4
I think they used similar one for hacking.
Люди из div1, как решили задачу B?
я решал так: если
T<=n, то просто найдем самую длинную подпоследовательность. ПустьT > n. найдем самую длинную такую подпоследовательность еслиT1 = n и T2 = n + 1. пустьdiff = ans2 - ans1, где ans1 — ответ при T1, а ans2 при T2. тогда ответом будет(T - T1) * diff + ans1.what on god sake is the 3rd pretest from div1B?
Maybe something like this:
4 10
1 1 1 2
answer 31
my answer is 31 and I got WA in 3rd pretest :D
ok thanks that was it
Seems like you know nothing :P (this is just a troll, you are way better than me)
What was everyone's solution to Div2C/Div1A? Mine was a really questionable greedy which sorted all of the values descending, took the top 2 as the first 2 numbers, and then removed pairwise gcds, took the next descending number available, remove its pairwise gcds with all other chosen numbers, rinse and repeat.
I feel like there's some counterexample to this algorithm, but it passed pretests.
I did the same.. and I think it is correct
Did the same, but got TLE on 7 pretest.
Could you tell some more on your implementation?
It's hard to describe since it was pretty long. Here is the link: http://mirror.codeforces.com/contest/583/submission/13380072
I did the same with a map<int,int> storing the number off occurrences for each number.
what if the top number repeats ,like 6 6 4 2. Hope you handled that.
Yep :D
:D
I thought of this case after submitting my solution for C. But used this case to hack someone else's solution :-). And my solution was hacked too :-(.
That's what I did too, and I'm pretty sure it's correct. A not-very-well-explained proof: Consider the situation: You have a partial solution that is certain, and you need to sort the remaining numbers. If you don't put the biggest one on the diagonal in the table (i.e. as one of the numbers we're looking for), and pick some smaller one for all the cells there. Then you have to put the big number somewhere else. But the number on the diagonal in the same row/col as the biggest number has to be a multiple of that -> contradiction.
It's correct. Notice that if you make the GCD table from the sorted array A, then the maximum element of (full table minus a square touching the bottom right corner) is the last diagonal element.
I'ts definitely correct. I have most of an inductive proof on my scrap paper.
I did precisely this with C++ multisets as my underlying data structure. Got TLE. I constructed the worst case on my computer and it runs in ~0.1 seconds. No clue what the problem is.
How to solve Div2 D/ Div1 B
The first time in my life that I failed all the problems. Look like I will have to go back to DIV2 soon...
Also, "Mathforces Round #323"?
Through, all the problems seem very interesting today. I wonder how to solve A and B.
In first one we can make two arrays : one for horizontal and one for vertical and initialize them to zero. Then while taking input we can check if both are zero then we store the position at which input comes. After taking all input we print the stored values.
I think he meant div1 problems :|
Oh! :-P
Div1-A
Sort the array. It's obvious that the biggest number in array is actually from answer (
gcd(A, A) = A,gcd(A, B) <= min(A, B)). So you take the biggest number and store in some Ans array. Next biggest number in array (let's call it B) is actually the second number from answer becausegcd(A, B) <= Bandgcd(B, B) = B. So now you know that it's number from answer, you erase it from array and add to the answer. Now last move, you need to erasegcd(A, B)andgcd(B, A)from the array. Finally, at every step you take the biggest number, add it to the answer, erase it from the array and erase each gcd with other numbers in answer two times. That's all.My solution 13368755
Div1-B
It's kinda obvious that there will be some "plato" in answer subsequence. There will be one number (maybe on several positions) that will be taken in all copies of initial array in the "middle" of answer. So I checked if n * T is bigger than 10000 and if it is than I take Tnew copies of array such that n * Tnew < = 10000. Now you can compute the length of the longest subsequence with the dummy quadratic algorithm and than you take two neighbor copies of array in the middle of answer. You take the biggest length of subsequence to them and say that difference between these lengths will be constant between each neighbor pair of arrays in the middle of the answer. So now you just add that difference multiplied to T - Tnew to the computed answer on Tnew copies.
If n * T is less than 10000 you can use dummy algorithm to compute answer.
My solution 13373614
What IS pretest 3 on Div2 D :/ ( my code passes 4 10 1 1 1 2 => ans 31 )
try 1 2 3 4 4 4 4 4 5 6 7
Question.C (Div-II) was very ambiguous question.....Is ans not just diagonal as GCD(x, x) = x OR am I missing something ?...Can somebody please explain ?
The input can be in any order.
I thought this, but then I read that ELEMENTS CAN BE INPUTTED IN ANY ORDER.
You're right, answer is diagonal elements but the thing is elements in the input were in an arbitrary order
Graph is not given as it.. It is given in arbitrary order
and gcd(x,y)<=min(x,y)
What is pretest 3 on Div2D? My code passes (4 10 1 1 1 2 => 31)
I always thought that all the stl functions are pass by reference rather than pass by value. Wasted a lot of time in figuring out what was making my code slow.
slow code
int fun(multiset st) { multiset :: iterator it = st.end(); it--; return it; }fast code
int fun(multiset &st) { multiset :: iterator it = st.end(); it--; return it; }Only difference is in passing the arguments, in one I pass by value and in other by reference.
Can anybody please tell me whether this is the only stl container which has pass by value behavior or are there some more?
You are still thinking in Java, everything in C++ is pass by value unless you explicitly pass a pointer/reference.
Well technically, Java is always call by value only. It is just that a new reference of the memory is passed to a function. http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value
Your st is the instance of
multiset<...>template class, so when you pass it without a reference (&), you pass the whole structure. It applies to all STL containers, not only multiset so don't forget to pass the reference!Because when you declare parameter without a refrence you are saying "Please copy the whole stuff", which can be VERY slow.
When you are passing by reference you just passing an pointer to the object, so nothing should be copied.
Is intended complexity for problem div1-D O(logp(A)^2*2*2) ?
If so, how is it possible to make it accepted in java?
Yes, we have a solution in Java that works in 2.2 sec.
So, is memory also O(logP(A)^2*2*2)?
Oh, I see, you don't need to keep all rows in dp. Next time I will write using for's instead of memorisation. Thanks you very much. So sad :(.
Here is the code of winger: http://pastebin.com/VRvrqSg9
Yes, using linear on
memory here is much more convenient.
Editorials??
When will the editorials be released ?
Assuming I didn't mess anything up, I think div1 D shouldn't be hard to solve with a simple DP, it's just annoying to implement. You need the following fact: the greatest power of p dividing
is the number of carries when adding a + b in base p. So if A has n digits when written as an - 1... a1a0 in base p, we can recursively compute dp[i][j][k], the number of ways up to sum two a, b < pi, with j carries, with k = 0 if a + b < pi, and k = 1 otherwise (so 0 ≤ i < n, 0 ≤ j ≤ n, and 0 ≤ k ≤ 1). I believe the edge cases with a ≥ pn - 1 or b ≥ pn - 1 can be done with similar, more careful analysis.
Why you do this CF ?
If you see something like this, write us a message and we'll ignore one of those two submissions. We have a system that detects double-submissions with zero diff, but sometimes it doesn't work properly :(
I ignored the second of those two submissions.
Thnx :)
Hi, the div 1 status changed from Finished --> System testing, with 1 only pending submission 13368130 from ashish1610. And now we can't use practice mode. Did you make any mistake? :)
Yes, you are right. I guess you should be able to upsolve now, sorry for that :)
Now, I have -1 with pretests passed.
Don't worry, we'll fix that. Looks like I accidentally broke something.
Fixed! I had to run a micro-system-testing in order to fix your submit :)
Thanks :)
Is there any chance this could stall the rating changes as well, since the changes already took effect for Div 2 (a much larger contest)?
Also now that we're on the topic, why do the rating changes generally take some time to take effect? They don't seem that hard to calculate, do you guys manually check some flagged submissions for cheating or something?
The rating has been recalculated for both divisions, isn't it?
There is a lot of manual work every time after the contest (including looking through some suspicious submissions, catching cheaters etc). This delays rating change as well as system testing sometimes.
Oh, 5 minutes ago they weren't, or maybe my cache was messing with me.
I must say, the overall changes in rating were pretty underwhelming (Largest rating changes in a previous Div 1 vs largest rating changes in this Div 1). Is that because this contest had only half the participants? Or was one of the ideas behind the new formula (there's a new formula right?) that ranks would be more stable?
When will be available the new ranking formula?? Was it used to rate this contest (#323)??
Ёлки-палки! В 1 дивизионе теперь в 10 раз меньше народу, чем во 2.
div2 D, in O(n^3*log T) right?
I solve in O(300 * n2)
I solved it in O(min(108, (nt)2)) 13373614
I solved it in O(n^2*logn)
I had the same complexity. I observed that for a LIS,I need maximum n periodic arrays where an element changes(from x to y ,y>x) ,the others contain only an element. But I fixed the number of periodic arrays needed,So I have (n +n^2+..+n*n)*log.
I didn't see that the case with n*n(or t if n>t) includes all of the others,so if there is an answer when I need just x<n arrays,it will include also that :P
I feel like 2 hours is too little for this Div 1 problemset. 2.5 hours would be better.
How I feel about number of div2 participants:
(╯°□°)╯︵ ʇsǝʇsʎs
I'm joking, of course, thanks for the round and work which went into the new rating system!
Why is the system testing taking this long? Oh, because too many people in div2.
Nice contest
can someone tell me why my div1 c submission got tle13381594
It looks almost the same as mine... Maybe the timelimit is too tight. (Or the problem setter has a better solution.)
Edit: dreamoon_love_AA is right. I used n/len gcd instead.
I think you use too many time of function __gcd() in line 34. So the time complexity of your program is O(nlog2n).
okay...thx ( i didn't take this into consideration (
What's the point that the system doesn't show test-cases during the system test?
Damn ! Man div 1 C had a tight timelimit !
my solution was of O(d(n) * n) damn ;D
Okhhh!! Finally got «C» after years :~
Probably missing the witching Cyan! :|
Thank you for this round — it felt great solving the problems. Especially problem D, with having to go on a hunch of doing LIS from two sides for some number of copies of the array, even though I wasn't able to prove on-the-fly that this will work.
Hopefully I'll be back to div1 now. :)
Ranks are about to be updated!
My rating is most probably going to decrease. But still
Wonder why the problemset page still 'temporarily blocked' ?
maybe, because rating updating
From Another Blog Post I guess they were updating features.D
Eagerly waiting for Editorial...Its 1:16am in India :)
Editorial is already out:
http://mirror.codeforces.com/blog/entry/20692
eagerly waiting for the rating change!
Where is editorial???
I lol'ed after seeing vitux Solution
Could someone explain please why this solution is ac? http://mirror.codeforces.com/contest/583/submission/13385298
Vectors have not enough length. Weak tests? I noticed this at the end of contest and lost 250 score to fix this. It was senselessly ;(
He has written:
If you are talking about +-1 error in your solution than it is actually rare to crash because of this. It's like chances that A[n] will cause an Runtime error are very small (but they exist) and it's often better to leave the solution as it is.
I think it is better to lost some score than to lost everything) And i thought that vertical[n] == horizontal[0] ;( And in test where first numbers are n it can cause error.
You can't say anything because vector is not an array, so you don't really know how much space is allocated, is there something after your data in vector class by design etc (only if you haven't profound knowledge in C++). And about correcting mistake, I'm saying that it's unnecessary because I haven't ever seen program failing because of that error while using vectors.
Vector [] operator doesn't check if the index is out of bounds. Using it with index outside the bounds is undefined behavior. Vectors may also allocate more memory than necessary so that new elements may be added without reallocation.
You aren't going very far our of the bounds anyway.
Suddenly everything in codeforces turned into russian language for me :D
what is the feel seeing russian as foreign language?
It seems like there is an "anti-cheating" pass, or something similar, after systest?
I noticed my rank increase from 83 to 81 already :D
Yeah may be. Some submissions got skipped!
.
Why it work? 13382543
the new formula seems to be so painful(
my contest rating is 1608 and still i'm Specialist
Why codeforces use 32-bit system?
Main problem is multiplication: http://goo.gl/VVVWsN
Formula feels a bit weird (don't know if it's new one or not). I though I did ok, Top 60 out of 4.7k (top 1.3%), but I'll need to do this at least another 2 times like this to get div 1 :(.
Also only -91 (so cyan) for last place (with -600 points) seems weird. My natural instinct would've said gray, maybe low green.
Edit: I guess that happened before too, looking at http://mirror.codeforces.com/profile/worse my bad :P (though worse was 2k, and this was 4.7, so maybe it's not actually the same)
I think the new formula makes it harder that only one contest affects your rating like what was happening before in goodbye contests for example.
I'm the 5th today and hardly made it out of div2.
Admins, please rejudge with old formula.
We haven't said goodbye to it, it's not polite. ;(
My rating before this contest was very low(1954), I took 53 place, and earned only +118.
It seems like it would be hard to escape from violet(
It seems like formula changed.
Upd.: Didn't read comments before, sorry.
Разбор?
Oh wow, congrats to div 2 winner wrong_order I just realized he solved all of the problems in reverse and still managed to win, talk about relevant username.
Ouch, just debugged my 2C to find the problem on Test 23. A one-word typo for a corner case can ruin the whole solution! >:[.
I got WA on 23 as well. I guess its missing an integer in the end(int32 expected). What's your typo?
Будет ли разбор задач?
UPD: уже выложили здесь
http://mirror.codeforces.com/contest/583/standings/participant/5798484#p5798484 This guy decided to copy all solutions and submit them during virtual participation... what a bummer.