Всем привет!
Приглашаю вас принять участие в Codeforces Round #260(div. 1 and div. 2), который начнётся 8 августа в 19:30 по московскому времени.
Задачи были подготовлены мной, netman и randrew. Это наш первый раунд и мы очень надеемся, что он вам понравится).
Большое спасибо Gerald, CherryTree, vlad107 и dimad за помощь в подготовке раунда и MikeMirzayanov за создание Codeforces и Polygon.
Удачи всем!
UPD. Распределение баллов для первого и второго дивизиона будет таким 500-1000-1500-2000-2500
UPD. Приносим извинения за большую очередь в конце соревнования.
UPD. Поздравляем победителей.
Div. 1
Div. 2
Здорово! Раунд новых авторов, тем более от земляков) Думаю, будут хорошие задачи.
А если бы они не были земляками Вашими, то раунд не удался бы?
Да, железная логика, не поспоришь.
Хороших начинаний Вам!
It's good to see new problem setters coming up with DIV1 rounds at their first appearance :)
Thanks to Mediocrity,netman & randrew. We expect more DIV1 rounds from you :) :)
The first time so early I am.
Hope Strong Pretests :D
Hope Strong Pretests :D
Hahaha so much hate for you
Why there is so difference two people with exactly same comments but one has 65 upvotes while other -16 downvotes !
Sorry for personal question, but I was always curious are you really Chinese girl or you're a boy who just puts girl face (as well as pictures from anime, cartoons, whatever) instead of their real profile picture? I think, that's pretty big disadvantage of English that you cannot understand the sex of the person when he tells something.
MinakoKojima is really a Chinese girl.
How do you know that? Are you real Juan Mata too?
I don't think so. He posted comments and participated Codeforces Rounds while FIFA World Cup 2014 was running.
no, i am not.
but how is that related to my earlier answer?
How you can claim that she's girl if you don't know him/her in person? I just proved that one cannot judge people by their nickname/profile picture because you neither Juan Mata nor Chelsea player (but you have Chelsea FC on your profile picture).
One does not simply ask gender on the Internet!
There is no need — see rule 16.
But they're trying to break it...
netman,(one of the authors of today's contest) you profile is very inspiring. starting from CF 105 div2, minimum rating 1105 at 143 div2 and then a story to tell everyone the secret of reaching 2192 at round 259 div1 ! its really amazing to see rising someone from the very beginning with his passion and practice that reminds me my lack of effort to attain that level. Wish you more and more success:)
he is just 8 rating away from becoming Grandmaster. let's hope that he can achieve this in the next round. :)
seriously, downvotes for wishing a participant good luck? seriously??!
Rating graph of randrew is also inspiring... :)
minimum rating is
1306and maximum is1889... just 11 rating away from being Master...Welcome to Belarus & two years later you will be a Grandmaster!
or sometimes (like when you are tourist), just eight months later! ;)
Chinese Div1 rounds chain is finally broken :D
I hope that means we get a holiday from maths problems
Says the kingofnumbers? o.O
LOL, Numbers doesn't means maths , there's a lot of algorithmic and data structure problems which have numeric input :)
king means for everything involves number :P
Hope for math problems :)
i do too! [for geometry especially :D]
this is CF, not IMO
Codeforces Round 232 (Div. 1) was a terrible memory... All extreme math problem P This is not Mathforces :(
You don't do Codeforces Round #232 (Div. 1). Why "was a terrible memory" ?
Round 232 was one of the rounds lost in the 22-day Codeforces blackout so if you look at standings no one is there. He may well have participated.
.
What did you say?
Thanks for taking the time to prepare the problems. Feeling excited! Good luck contestants. (◕ܫ◕)
My first time in a Div 1 round, I hope I can make a submission.
Good luck! :))
Weak pretests please ;D
The first ever non-Chinese Div.1 round in 40+ days(excluding tournaments)!!!
Hoping to get back to yellow :D
Wish you good luck :D I'm just hoping to get a positive rating this round.
Well I don't hope I can get back to yellow only by one contest, I mean, there are more chance of positive rating change in non-chinese rounds
UPD Wow. I become master again. And you too XD
WOW! That's wicked! I've never thought of being yellow in one regular round. Congratulations to you too!
Hope for good problem. Hope for more hack.hf & gl
the shortest contest post ever
Hope short problem statements too.
and short solution too !
But not short editorial :P
Still no editorial post... bad :(
maybe because nobody wished for "short time taken to publish editorial" ;)
actually there's a shorter announcement here it was only first 4 lines when the author first posted it.
Seems that the post you talked about is the only contest forecast post that doesn't mention MikeMirzayanov :p
Как принято в некоторых других странах, откомменчу: Удачи всем белорусам на контесте!
Земляки, не позволяйте меня заминусовать:)
брат за брата :D
За основу взято)
Брата храни, врагов хорони, родителей цени, задачу реши
Жалко, что без пони, но зато и без спойлеров.
Special translation for MinakoKojima: It's pity without pony. But it's good there are no spoilers this time.
Big thanks to vas.and.tor for help with the special translation for MinakoKojima.
Thank to sebinechita (not a user codeforces (and it is not a user)) for help with translation helpful to vas.and.tor.
I start now FOR first time .
Welcome
Good luck & it's my first time to be purple to take part in Div 1 !
a good news for me, a Chinese coder who don' t do well in math... most of last Chinese Rounds are also nightmares for me :p(anyway, learning is always a goos idea, through perhaps you can' t adapt it well
Is it the first Belarusian round or any other Belarusian rounds that have happened before ?
No. For example, aropan was the author of Codeforces Beta Round 92 (Div. 1 Only) and Codeforces Beta Round 92 (Div. 2 Only) before, and tourist was one of the authors of Codeforces Round 127 (Div. 1) and Codeforces Round 127 (Div. 2). So it's at least the third Belarusian contest :)
So a Belarusian contest is happening after a long time Thanks for the info greencis.
Coders like netman inspire us a lot for continuous practise.
The start time is confusing.
mine is correct. F5?
I think the registrations close 5 minutes before contest :)
It's simple: the time shown corresponds to what's written above it. If it's "Registration's running", then the time shown is how long the registration will be running. If it's "Before start", then the time shown is how long until the contest starts.
Look carefully! Bottom right one says
Registration is runningGood luck :)
А куда делась ВКшная кнопка "мне нравится" возле отстчета до начала контеста?
Видимо туда же, куда кусок логотипа.
magic
Она исчезла. (с) Mike
http://mirror.codeforces.com/blog/entry/12980#comment-176995
worse прекратил "бурить"(
печалька
А вдруг на цфе рейтинг unsigned, и поэтому если уйти в минус можно выйти в топ?
мне вот просто интересно, на сколько он поднимется если хотя бы решит 3-4 задачи за контест?
GooD LucK...:)
Div 2 задача С — просто показалось.
I'm ready
I'm readyO RLY???
In queue
Such CE, Much slow!!!
Haha :)
What a pity , I submitted a code in last 5 seconds and I got " Codeforces is temporary unavailable "
Problem C reminds me of the first day of IOI 2013, doesn't it? It is also clear now why you didn't thank Delinur for translations.
I like problem D a lot. Seems to be a good example, where rope sucks and sqrt-heuristics rule :) I didn't solve it during the contest, so I may be completely wrong.
Thanks for the contest, I've enjoyed it!
Good problems, but contest was ruined by slow testing.
I saw 20 pretests in some problems. Which means no hacks and maybe 500 tests in final tests. This could take some time to finish.
I am not sure that pretests for A are really strong. I hacked a guy with overflow and using N instead of MAXVALUE.
Fun fact: you can check if there are at least x pretests in the Status tab with settings "any verdict" and "tests = x" — based on AC solutions shown.
This way, we get: 12 for A, 10 for B, 15 for C, 9 for D, 21 for E.
At least A-C have nice time limits and D,E didn't have too many attempts.
My solution for C has a terrible misprint, but it gets AC on the pretests. It makes me think, that they are not so strong.
Thanks. We don't thank Delinur because when I write the announce we didn't know who was the translator.
Seems rope doesn't suck 7400437, but how does it work?
How to solve Div2 Prob C? I summed effective values obtained by all odd entries first and then checked even entries that outweighed the neighbouring odd entries, and then vice-versa. WA on pretest 11.
I guess it was linear DP. dp[i] = max(dp[i-2]+(freq[i]*i),dp[i-1])
My solution:
I used this dp after 4 WA. I hope it could be the correct answer.
dp[i] = max(dp[i-2] + m[i] * i, dp[i-1])
How did you come up with this recurrence? Can you explain it please. Thanks in advance.
dp[i] = the maximum score you can get using numbers with values 1~i. It is obvious that if you take one number i, then it is optimal to take all numbers i. Therefore we have two choices — take all numbers i or take none. If we take all we have dp[i-2]+freq[i]*i, we use dp[i-2] since we can't use values i-1 and we get score freq[i]*i from taking all numbers i. If we don't take i then the answer is the same as dp[i-1]. So we get the formula dp[i]=max(dp[i-2]+freq[i]*i,dp[i-1])
Hope I helped! :)
lets say you have stored number of frequency in array f. (Note ai<=100000). Now for each of the number i, if you take i you can't take the next number i+1.so you have to recurse over the next's next number i+2. and if you don't take it , you can take the next number. And see if you don't take the number i , you have two possibility , either you took i-1 , or you will take i+1 , both case is considered in the previous steps. and if you take(which you only can if you didn't take i-1) you can't take i+1.
I too faced the same problem. :(
It should be dynamic programming, you should consider two circumstances of the number. Reserve it or throw it away. Suppose that c is the count of a precise number, we have: fi, 0 = fi - 1, 1 + c[i] * i, fi, 1 = max(fi, 0, fi, 1). Note that you should use long long in c++ or int64 in pascal.
Ok, but what is the mistake with my approach? http://ideone.com/MVT6SI
1 2 2 3 4 4 5 6 7 7 8 9 9 10. Best answer is taking all the doubled numbers; your approach, starting with taking the odd numbers, will not replace1 3 5with2 2 4 4because2 2is not strictly better than1 3and4 4is not strictly better than3 5, but combined2 2 4 4is better than1 3 5(because3only appears once).Thanks a lot!!
Как решить C Div2?
Простая динамика
cnt[i] — кол чисел i
Круто, спасибо.
Я ее пытался решить, задавая в отдельном массиве "веса" действия, т.е. (mass[i] — mass[i — 1] — mass[i + 1]) Примеры:
1 2 = -1 1
5 4 3 4 5 = 1 -4 -5 -4 1
4 5 7 6 2 1 8 = -1 -6 -4 -3 -5 -9 7
И потом брать наибольший вес, удалять числа, и переопределять таблицу весов Контрпримера нет ни у кого, кто так решал? Я на 5 тесте обвалился, со своими велосипедами
Мой друг тоже писал что-то похожее и дожил до 9 теста.
А я пытался пропихнуть жадник, и прожил чуть дольше вас — 11 тест.
now not
invalid input after 10 minutes :(
Сделал попытку взлома за 2 с половиной минуты до конца контеста, а вердикта почему-то до сих пор (после конца контеста) нет. В чем может быть причина?
Спасибо за контест))
интересно было решать, только вот по С Div 2 не успел одного взломать на long long
Всю жизнь пишу массивы от i64, внезапно сегодня написал от инта, контесты утром для меня плохо складываются.
Problems are all interesting! Thanks! What a pity that can' t correct my buggy codes at last:(
It is unbelievable that there are many people still use long long in Div2/B although the N is 10^(10^5)..
It is unbelievable that there are many people still use long long in Div2/B although the N is 10^(10^5)..
Who ?
7381800 7387856
(many people >= 2). It is true !
What? And IT passed pretests??? 0_0
If you take a look at code of participants, you will probably be surprised how many people somehow have used overflow of "long long int" or even "int" in their submissions
__233333333
Nice round. A and B were the way div2 first 2 problems should be. C was a little nice DP. D was a real show-off of Trie + 2 x DP + Game Theory. Also heared that E was pretty hard for Div (1+2), because Div1 coders should implement C and also meybe D or E.
The chain in the problem C could be maintained just by using a set. After merging two vertexes (a, b), the answer will be
.
Only note each "division by 2" should be rounded up.
But firstly you have two compute the largest path for if each set representative right? DFS from any vertex then find the most deep vertex. Then dfs from that vertex. Isn't it the approach for finding longest path?
Yes, we should firstly initialize this, just simply DFS and merged them up in the set.
For the ones who have studied problem 1A — Dreaming in IOI 2013 the solution will be quite clear. Fortunately I have read that problem and solved it before :D
How to solve problem D? Maybe I'm stupid, but I tried to solve it for quite a while, and the only solution I came up with is the straight-forward square-root optimization (store one single Treap for permutation + individual Treaps for all numbers which occur often enough). This takes
per query and works literally forever (30 seconds on my machine for the worst case). But looking at the amount of people who solved it, probably there is a much simpler and much faster solution. I wonder what is it?..
We have
solution and it's much easier then yours.
One can divide an array into sqrt(n) blocks and maintain a deque for each block. Shift operation is rather simple: for fully covered blocks, it is just one push_front and one pop_back. Partially covered blocks can be handled naively.
To answer the second type of queries, one can maintain a count array for each block(count[i] — the number of occurrences of i within a block). For fully covered blocks the answer is just count[x]. Partially covered blocks can be handled naively again. Shift operation changes the count array in at most 2 positions per block, so it is possible to update it quickly.
The complexity is O((m + n) * sqrt(n)).
Beautiful, thanks for the explanation!
From what I could read in kutengine's solution: keep
linked lists containing 
elements each, and remember the count of each integer for each list. Then you can do the rotating query by removing from the end of one list and prepending to the start of the next.
That's quite beautiful, actually. I'm always surprised by sqrt-decomposition brilliance :P
Can someone explain this compilation error to me?
7393631
it worked after I've resubmited it (no changes were made)
You try not use #include <bits/stdc++.h>
Any particular reason for it?
1 — "it makes the code completely non-portable across compilers, and as I doubt the header is documented, being in the bits folder, the behaviour of the header is probably free to change in any future update." chris
ref: http://stackoverflow.com/questions/23644633/cannot-read-bitmapfileheader-of-a-bitmap-file-using-c
2 — "You should never be including this.
#include<bits/stdc++.h>Its an implementation file. Stick to the header files defined by the standard (they don't have .h on the end)." Loki Astari
ref: http://codereview.stackexchange.com/a/48813
It is obvious that this will only work on GCC. But if you only use GCC, then you are free to use any of its features.
Also this file is documented, and will not change without notice: https://gcc.gnu.org/onlinedocs/libstdc++/manual/using_headers.html#manual.intro.using.headers.pre
Try a different compiler (e.g. C++0x) -- it works fine on my computer.
the problem is that the compilation error that was issued was this one:
Can't compile file: collect2.exe: fatal error: CreateProcess: No such file or directory
compilation terminated.
thats very weird...
PS: it works fine on my computer as well, it's codeforce's judge that's issuing this error ):
How to solve div2-D ? I tried to use suffix automaton but couldn't get an idea. Hope a nice tutorial for this problem.
I guess, D is based on game theory..
waiting for the editorial :)
I think we can use bor and then for each vertex set: 1) can we Win from this position 2) can we loose from this position After it see on root vertex and print answer. http://mirror.codeforces.com/contest/455/submission/7387998
It's trie, not bor :)
trie + 2 tree traversals to check if it's always possible for first player to win and if it's always possible for first player to loose. then just check for each case:
first player can choose if he wins or looses a single game -> "First"
first player always wins a single game AND k%2 == 0 -> "Second"
first player always wins a single game AND k%2 == 1 -> "First"
first player always looses a single game-> "Second"
There's a case when first player can neither win nor lose for sure. Then second player wins and 71st testcase covers it.
I'll take a look, bit i think it's always possible to be sure (at least my code got AC)
There are 5 different cases(but we can reduce that to 3):
The first player can decide the result of the game. Then he will lose n-1 games and win the last one.
The result is deterministic (first player always win or lose), in such case, if first player always wins, result depends on parity of k; otherwise first player loses.
The first player can ensure a lose but cannot win, then opponent force him always lose.
The first player can ensure a win but not a lose(this is more complicated and I took some time to evaluate that): assume k=1, then first player choose to win; then assume k=2, we will see that the second player can let him win, and get a first play in next game and wins; evaluating similar cases as k grows we will see that first move will always win if optimally play. So the result depends on parity of k again.
The opponent can decide the result. Obviously the first player loses.
And finally the conclusion is: If first to play can decide the result then first play wins; Then if first to play can only ensure a win, result depends on k; Otherwise first player loses.
After waiting for a long queue, my submission have failed on pretest after 15 minutes after the contest. I should have tested more with handwritten cases.
again power of
#define int long long.....2 unsuccessful hacking attempts on my code because of this...:Pyes ,but one of them give me 100 pionts. others even passed,very angry...
How do you write int main?
GNU C++ still accepts "main()" which means "int main()" but with a warning.
signed main()
Nah, that's way too conspicuous ;)
You can write void main() in Visual Studio
But GCC gives
compilation errorif you writevoid main(), and that's not supported in standard.Codeforces supports MS compiler
16. Solution code obfuscation and creation of obstacles to reading and understanding the solution is prohibited. It is forbidden to use any special techniques designed to complicate the reading of the code, to understand its workflow.
/blog/entry/456
Yes, but this is actually useful if you want to avoid overflow. It can lead to fails, but it does have use.
Oh ... take it easy man...! It's just a technique to avoid integer overflow and using
intsafely...it also has some good side effects!It stopped being "just a technique to avoid integer overflow" when you boasted how you tricked other people with it. I agree with dalex, it is a poor practice.
Yes, I guess it's time to enforce the rule. I've seen countless solutions with super-obfuscated code, "#define int long long" is one of the most innocent tricks. E.g., once I've got unsuccessful challenge attempt because someone submitted file with 2 solutions — correct one was at the top, and then incorrect one (with bug) was at the bottom, protected from compiling by some hacks (but not commented out — it would be too obvious).
Introducing unused code rule (similar to topcoder) would also be nice. Yes it slows some people down if they have to clean up their horrible mess before submitting, but making other people read this mess is much more cruel.
Which solution? Unlike TC, at CF contestants can gain from making solutions readable -- because it's possible to resubmit solution if it haven't been locked.
They benefit only from a certain kind of readability; there is no reason to fix hacks like "#define int long long" (and more tricky obfuscations).
Regarding to your first question — I'm not sure I understand, what are you referring to?
so using "small L" should be prohibited because it's exactly the same as "one" in codes! I lost an attempt to learn it ...
LOL, i tried to hack you once, and it returned unsuccessful for the same reason. luckily it was only a testing round. :D
PS: due to Black Day of CF, this submission is no longer visible. :(
so many people even use long long to cin>>n in DIV2 B. and a lots of them passed.... what could i say
Or they used int :) 7389513. And my attempt to hack was unsuccessfull.
I couldn't watch your hack attempt. What were you input?
string: "1" x 100000 + "\n"
In this case, maybe what he got is "1111111111".(The ouput as well as answer is 0) The better way to hack is input "1" x 999999 + "2". (The answer is 4 while the output is 0) :)
People used biginteger and modular exponentiation in div2bB!
Hacked a Java code but python code passed time limit! :(
See this code!
7383987
also see this 7378490 :P
I don't understand, How can they pass the time limit :o
Why not ? Modular exponentiation is O (log N). 7383699
In hacking box, font size is too small. When I was attempting to hack, I couldn't distinguish letter
1from letterl. So I sent an hacking request and got Unsuccessful. This will be better if font (in hacking box) is not Courier New or at least not too small like this.1andlalmost look the same in hacking box, I agree. I've got same problem before.why system testing is not started yet ?
hope all accepted solutions!
slowest ever system test :(((
Because "Pretest testing" hadn't been done.
Oh la. What a large queue. :X
problem div1 A, at beginning I thought we remove all element equal to Ak + 1 not Ak + 1 , who is the same?
Although my eyes are not good but I am not as you !!!
Me too :/
@Nero
Верно ли, что в при объединении двух деревьев если старые диаметры в них d1 и d2, то новый будет максимум из: d1, d2 и
?
Если твои квадратные скобочки — это округление вверх, то да.
1
Да.
Нам не помешает лишнее нытьё. Завалил С из-за того, что при слиянии не проверял, что мы уже и так в одном дереве.
I have a question. How did this "7385674" solution passed the pretest..?? i tried to hack this with a large input. i thought it will fail to take the input. but it still passed.. and gave correct answer, how is it possible...???
Your test you hack ?
Because (x^4 — 1) % 5 == 0 (according to little Fermat theorem). So there are only 4 cases:
n == 0, n == 1,n==2,n==3 (mod 4). Easy to see, that if n==0 (mod 4) -> ans=4,else 0
sorry bother if i am not clear... the problem says the input can be very large... but the solver use long long.. I tried hacking with a input consist of almost 300 digit. how did it take the input a 300 digit long number in long long and still can calculate the correct answer...?????????
passed pretest but it will fail system test.
and your hack failed because when this code reads large number it will overflow so an overflowed variable will have random number so it will still enter either "if" or "else" and in your hack it entered by luck the same as the correct answer for your test so it gave correct answer.
Understood... thnx....
that's incorrect. there is another discussion: http://mirror.codeforces.com/blog/entry/13326
simply put: in codeforces, scanf takes overflowed inputs modulo 2^64 and, as 2^64 is divided by 4, it doesn't change the final result
5464456456456456456456465465456456456456456456456465
At my computer it gives wa
It looks like this solution relies on particular implementation of cin. Actually, what really matters is a residue modulo 4, so it's not so strange that solution works, because when overflow happens "divisibility by 4" is not changed.
counter example : 111111111111111111111111111111132.May be you didn't huck, because for your test answer is 0.
And some submissions have got accepted, even though there has been overflow
If somebody uses cin for taking input, and if your input is too large , it will take maximum value of that data type(I found when I did unsuccessful hacking). If you use scanf(), in case of long long it will just move between 2^-63 to 2^63 — 1(Data type range). In Java it will throw exception, I thought same in c++. His submission accepted because he used scanf.
For Div2, problem c, I used the DP : dp[i] = max(freq[i]*i + dp[i-2], freq[i-1]*(i-1) + dp[i-3]), can someone please tell me why it is wrong and why dp[i] = max(freq[i]*i + dp[i-2], dp[i-1]) is correct?,
What are hackings on problem A div1? At first I think some people doesn't use
long longbut it seems that pretests include that case.Got successful hack on a guy that used int so I don't think pretests cover it.
Mine: image
And System testing starts finally
around 50 minuets after the contest.
Started finally! 45 mins later.
I remember I had even read the full editorial by this time in previous round.
... And system testing is completed!! nearly an hour only for systest!
Registered: 83 minute(s) ago have Contribution: +13 !!!. Link
It's frequent phenomenon happens in codeforces when someone wants to post a joke but he/she is afraid from negative votes so he/she makes a new account and post the joke with that account
You are right ! Maybe he is not excited about that
And when you see that the comment got lots of positive votes, you regret not using your real account
umm, u didn't even take part in the contest! o.O
7377218
This shouldn't have happened...
Could you please repair it ASAP? :P
OK, fixed. Thanks!
Many programs which already passed pretests get "Compilation Error", I think there must be some problems with the judge system.
Is there any problem in system tests? I submitted 2 codes for A, 1 for B and 1 for C. Instead of skipping my 1st A code, the submission page shows my B code as skipped.
Can anybody explain me this: 7377299 ?
UPD. This solution passed pretests; verdict became "Compilation Error" during the testing .
After resubmission, it was "In queue" until the end of testing.
Кстати, в B div 1 проходило решение за O(k), надо было чуть поднять ограничения на k...
wut? Как решать за O(k)?
Показывая пассы Никиты Литвинкова, когда тот говорит о чае Супер-пупер математическим алгоритмом со страшным названием!
Ну, всё как в обычном решении, только вместо if'a на чётность k, цикл :)
Лол)
1H after coding phase and system test still not complete :(
codingphase
Bad influence of topcoder(
Nope. When a Codeforces round ends a message box pops up and says "the coding phase of round xxx has ended"
nope. if i'm not mistaken, the box says
In Div2 "A" — I checked if numbers in each pair are equal...
7383032 Seriously -_-...? Why?? Because of what? Is O(n log n) too slow for 3e5 -_-?
7391661 Even worse :(
Uhm, by what magic doesn't it crash? Your function "Find()" doesn't return results for non-trivial cases...
LOL XD Good point :P
I guess that works because assingnment returns the assigned value (eg. a=b=7; assigns 7 to both a and b).
Anyway I commented the cerr and got AC xD 7396190
Yes, I did the same few minutes ago : /. I ignored it, because it outputs The same amount of text as cout, but it was a mistake ; d. Is cerr slower than cout?
I know perfectly well how assignment works. However, "int f { a = b; }" isn't the same as "int f { return a = b; }" ;) In this case it can be smth with how return value is stored on the stack and how exactly the code is compiled. However, missing return is Undefined Behavior, so compiler has full right to compile it to "while (1);" or to "exit(42);".
That's magic in C. You can program a one-liner gcd or disjoint set XD
в этот раз тесты плохие. DIV2 задача A у меня прошло вообще не верное решение :) Заметил, как всегда, после блокировки задачи...
лоооол
упс...
у меня системные тесты прошли. Вот в чем беда.
Пффф.. Даже простой тест с циклическими данными сломал бы ваш АС код 7385198:
Check out room 23: Slovak domination!
what do you mean?
Me and Bobik are both from Slovakia and take top 2 places. It's rare to see 2 people from a small country in a room together, and taking the best places is much more rare.
two coder in one room means these two coder registered nearly at the same time.
According to the registrants' page for that contest: Bobik is 27., I'm 1102.
nope.avi
I have thought the room is according the order I register... Oh, it is wrong... I want to find out the algorithm for the place of room.
I don't know what it is, but if I was the one coding it, I'd make sure it's randomized and sufficiently complex so that nobody could register 2 accounts in the same room to get hacks — and, of course, people just registering in the same room for the lulz.
Omg, that's unbelievable! How did you manage?
It's magic :D
I have no other idea how to explain it.
http://mirror.codeforces.com/contest/455/submission/7392292 TLE just because I used vector ?
ignore me. I made a silly mistake
can anyone explain div1-B . I was trying something with trie ....but coludnt get it ...
Here it goes, hope I explain my solution well enough:
Firstly we build a trie. The root of the trie is the empty string. Now the game proceeds as the first player starts in the root and then chooses a child to go to. Then the next player chooses a child to go to and so on until you are in a leaf, when the current person loses. Now to efficiently solve the problem you must compute two values for the root position.
1) Can you win if you try to? (is it a Winning or Losing position)
2) Can you purposefuly lose if you try to?
Both are equally simple to compute. Simply start from the leaves and go up the tree computing each vertex through its children. The computation of both values is simple and is as follows:
1) If you can move to any lost position, then the current position is won. Otherwise it's lost.
2) If you can move to any position that CAN'T be purposefuly lost, then the current position can be purposefully lost. Otherwise it can't be.
Now how do we compute our answer? Well let's look at a few cases.
1) One simple case is if the root position is lost, that is you can't win if the second player plays optimally. Well then the answer is "Second" as he could easily win all games and the loser would always play first again and lose
2) If the root position is won, and it CAN be purposefuly lost then the winner is "First". This is due to the fact that he can purposefuly lose until the very last game where he can win, no matter what k is.
3) The last case is if the root position can be won, however it CAN'T be purposefuly lost. Well then it is obvious to see that if some of the two players wants, the game can be played in such way so that the first guy always wins. Therefore it is easy to see that if k is odd the first player will win, and if k is even the second player will win.
Hope I helped you :)
Nice ans .. thanks!!!!
thanks..well explained
if possible please provide the code as well...
You could easily retrieve it from my submissions : 7384830
Array W is true if the position is won and array LI is true if the position can be Lost Intentionally.
Thanks a lot ....it really helped
Why no editorial still?
I dont think editorials cannot be shown during systest (when it takes 100+ minutes)
Oh please show the editorials now.
(Its 2 hours since end of the 2-hr contest)
Все кто писали Union Find без ранговой эвристики или рандомизации обломались. Оно правда работает за квадрат?
Я писал без ранговой эвристики. Зашло.
У меня зашло, и оно работает за O(N log N).
Должно работать за log амортизированно.
у меня зашло.
Более того, некоторые из тех, кто писал с ранговой эвристикой, обломались тоже.
My submission was judged as WA on test 20 but when I use custom invocation, everything is OK. Please check! 7377515
7377531 WA with no reason? I submitted the same thing in practice and got AC...
Same to my situation, I have just resubmitted my in-contest code.
Same problem with mine 7395010
Thanks for minus!
I can't stand that Imagine my excitement when 1,5 min before the end of contest I finally debugged my D. Imagine my anger when few seconds later it turned out that Internet crashed in a place I was coding and I can't submit it. Imagine my anger when I got to know that my C got very weird TLE which resulted in 39->262 change of my place. Imagine my anger when I submitted D on practice and it got AC!!!! And now my C got accepted after deleting one cerr (without endl's, so it is really fast)!!! Words won't describe my irritation at that moment ^&*(%^%^*!!!!! I should have took ~10th place and I got 262th! ARGH!
imagine my anger when I submitted a code for D in last 5 seconds and I got "codeforces is temporary unavailable"
I see that your code doesn't pass 1st pretest, so it is not that bad feeling afterwards xd. Btw I once managed to load my code, but haven't managed to click "submit", I was late about ~1 sec and it passed after the contest. Moreover it was E (I never got E accepted!) and I spent 15 mins of that contest doing nothing on facebook xd.
I fixed my mistakes in that submission then submitted again in last 5 seconds so why it's not a bad feeling ?
Hm. sometimes I also get angry, because of some unlucky circumstances, but when I submit my code after contest and it's not passing I'm getting calm. So far, I don't see your solution among accepted, so I guess that it's the case. But when it gets accepted xd...
Still you gotta admit, getting "codeforces is temporary unavailable" while trying to submit or open a problem is quite irritating.
Yes, I have to. I'm really a professional in category of whining about everything and if it had occured to me I will surely get annoyed :P.
Bredor has never participated in div 1 at all. Hey bro are you going to compete?
I have some problem with my div 1/B submission
this is the code I submitted during the contest, and got queued until the end of the contest. The verdict said WA on pretest 1. But it appears that there is no output in the submission above.
Then I submit this code after contest, the very same code but with assertion commented, and it got accepted (I tried to post the exactly same code but the verdict is exactly the same with my first solution; no output at all).
Does anyone knows what's happened?
Can we continue to solve problems?
System testing...
7392014 is checked still...
Can we continue to solve problems?
I see the most of the solution of DIV 2 Problem LAPTOPS solved using sorting in O(nlogn) complexity. But it can be solved in O(n) . Suppose for "Happy Alex"
price[i] < price[j] ....................equation_1 quality[i] > quality[j] ====> -quality[i] < -quality[j] .................equation_2
let's add equation_1 and equation_2
price[i]-quality[i] < price[j]-quality[j]
Difference[i]<Difference[j]
so compute all the difference , get max difference and min difference if max_diff!=min_diff
then "Happy Case" else "Poor Case"
There is much easier solution using piegon's hole principle.
hussieneloy would you like to explain ?
But does Difference[i]<Difference[j] imply price[i] < price[j] and quality[i] > quality[j]?
@Vintarel yes
Both the price and quality numbers are limited from 1 to N. Since they are unique, the only way the prices are valid if they look like this:
(for example, if N = 3)
So you can just parse it as you read it, and if price != quality for any pair, you just print "Happy Alex" and break. Otherwise, print "Poor Alex".
It’s my first time in CF and feel 2exicited. But I got TLE for cin ,which depress me.
Why is my submission skipped? 7380034
prost))0)
Sorry, but I don't understand what you mean.
simpli))0)
what is up with adding ))0) to the end of every comment of yours?
also, what happened to 7394707? 7395446 is almost the same code (one constant changed, just to make it different from previous code) and it got AC?
do i lose points for 7394707? it says
Only the last submitted solution will be judged. All previous ones will be skipped.
During contest I got TLE 121 on problem C: 7391661
Exactly the same code got AC in practice: 7396418
This might be caused by server load during the contest, and I request that my in-contest submission is rejudged and considered correct.
Your code in practice runs 951ms. IIRC, variation of execution time on codeforces is ~40-80ms, so nothing surprising that it failed during the contest.
If it was WA then yes — it should be considered wrong. But IMHO if a solution once once fails time limit due to overload, and then passes, it should be considered correct.
I can't find how such cases are considered according to Codeforces rules though. I think it's up to problem setters and administration to decide.
That's not due to overload. Try submitting your solution again to practice several times (adding whitespaces to make it re-run the submission). I've just tried, and it gets TLE ~50% of the times.
I think usually on CF they don't change their verdicts. E.g., ~3 years ago one of my problems failed getting TLE and passed in practice with 100ms margin. Back then they probably had slightly different machines, and now it's not that bad.
7396999 Here it passed again, so the fail during contest is definitely due to system load.
And here it failed: http://mirror.codeforces.com/contest/455/submission/7397092
I'm absolutely sure it's due to the natural variance of execution time; 40ms margin is very tiny.
I agree that it might equally fail and pass. My question is, how are such cases handled on CF? May be some of these points:
or something else. I would appreciate an official comment from problemsetters/administration.
Anyway, this particular solution had the same chance to pass during the contest, and I might be somewhere around 50th place, not 286 :)
I believe it's "submission is correct, if it got AC on the systest", with "submission is systested if it passed all pretests, is the last submission of that user on that particular problem and wasn't skipped for cheating". So it has to pass all pretests on 2 runs and all other tests on 1 run. Of course, with possible reruns.
Maybe you noticed that usually, the authors of the round have solutions that fit in the time limit comfortably. That's because the TL is chosen so that a reasonable constant factor wouldn't pose a problem, usually 2-5 times that original solutions' runtime. And I think it's safe to say that a reserve for cases such as yours is included.
The practice is that the system test results are final in this case.
Check out my submissions in practice — I tried submitting your code several times (the only difference is adding a comment) and got AC 2 times out of 9. Based on this, I don't think a rejudge would make much of a difference, unless the code was rejudged until it got AC (roughly 1-5 times, I'd guess).
Когда будет разбор задач?
вчера
ты душка
я не банка ягуара, чтоб тебе нравиться
where is the rating result ?? ?? ?
I'd personally wait until all the matters with weird compilation errors and wrong answers are resolved before updating ratings (there were, and still are, a few). In my opinion, it's way more important to carry out the competition correctly rather than immediately update ratings...
v karagande
Country Wise standings is updated.
Я правильно понимаю, что Дэшка и за
на запрос решается? 7394913
И ещё, это(7397416) случайно не квадратное решение Ешки? Точнее говоря,
. Это было так задумано, ограничивать Amax ≤ 10000, чтоб наивное решение заходило быстрее чем любое другое, пусть даже с правильной асимптотикой? =)
UPD. Всё-таки это тесты слабые. На тесте с массивом вида
1 10000 2 10000 3 10000 4 ...этот код работает больше 2х секунд в запуске.Как я понимаю, это решение по D все-таки за
на запрос.
And it was a pretty easy bug to catch, too... :(
I used grundy numbers for problem B Div-1. I have no idea where it is failing. Can anyone please help me find the error?
Link: My submission
I'm not 100% sure here, but I think that Grundy numbers work only when both players want to win. In this game, it's sometimes optimal to lose until the final game comes around.
I am using grundy numbers only to evaluate one game. For each possible starting move, I find the grundy number for that move.
Now if I find all starting moves to have grundy number > 0, then if k is odd, output "First" else "Second".
If all starting moves have grundy number == 0, then answer is "Second".
Else, answer is "First" as he can keep losing until the final round and win the last one.
Test:
Your answer is "Second", but right is "First". You should check whether first can lose if he wants it, not if second wants it. In test first loses 99 games by a-a-c-a and wins last by a-a-b.
UPD. BTW, you store "edges" in strange way. Are you sure, that you can't make move from valid string by edge into non-valid string (for example, edge was "generated" by other input string, then string to which current position is prefix)?
OH! I totally missed this, thanks a lot!
I think the edges part is fine. For example, in the test case you have given above, ['a'][1] has edges to ['a'][2], ['b'][2] and ['c'][2].
UPD: I've realized why it is wrong. :-|
consider this test :
aab
bac
according to your code edges[a][1] = {b, c} but this is not correct. for "aa" the next letter is just 'b' and for "ba" is 'c'.
It seems I have gone wrong on multiple levels here then. :-(
Thank you for the clarification.
Quote from your code: "//I'll shit bricks if this happens"
You'll definitely do this because of test 71. I did the same mistake.
Hahaha.. Well, hard luck.
Why the output is unexpectedly 0 in 43rd test case ? Submission id: 7389527
The for statement should go till 100000 instead of n and you should cout max(ans[100000], ans[99999]).
oh..Thanks.. I was hoping to become Expert for the first time but became Pupil! :(
Edit: Did not notice that there is already a post that has answered
Is it just me or was Div1-B really confusing? I thought during the contest that the players will play optimally in each game, and not considering all k games....
No, the result is determined by the following sentence:
"Guys decided that the winner of all games is the player who wins the last (k-th) game."
Actually you're right. But for example after contest before system test, I asked my friend who tried to solve Div1B, "Play for win, for each game" is optimal?, he said "I didn't think it". Problem doesn't say "You don't need to play for win, for first k - 1 game.", it says "You have to play win, for last game." So you have to make a little observation.
I don't know if confusing is the right word. It's just a matter of analyzing the problem fully, paying attention to every detail.
I did consider K games, but I forgot about the fact that people can intentionally lose. (I thought of using K mod 2 to determine the output once I analyze a single game).
Обновите рейтинг, я спать хочу
Идите лучше спать). Это будет не скоро.
Почему?
Five hours have passed after the contest and the rates have not been updated yet! What is the problem?
Why is not updpate rating ? I hope very more about this
Why there is a Hack with status "Waiting" after contest?
Look for 107221
LOL, it's still "Waiting" more than 7 hours after you wrote this comment.
but ratings have already been updated. :D
Finally! Ratings have been updated, just now.
I want to ask a question ,why my div 2 C problem's final test statue is Skipped?I am so puzzled.
Yea that is really weird. I submitted your solution and it got AC. link
In contest，I got pretest passed，but after final test，it became skipped.I want to know if it is possible to rejudge it.
It is so unfortunate that they updated the ratings before they resolve problems like this. It is not just you, there are other submissions which have weird verdict (like this, WA with no reason)
Cause you cheated 7394898
Would you please post the editorial for this contest :D ?
Mediocrity netman randrew
would anyone like to suggest how to solve problem E- DIV2 Efficiently ?
Firstly , you are given a graph which is a forest(note every connected component is a tree, as there is only one unique path between any pair of vertices).
Now , to find the longest path in a tree , you first start dfs from the any vertex u. Let, v be the vertex we find which is the most deep node from u. Now from v you do a dfs, and find the most deep node. This height is the longest path.
When you have found the longest path of a tree L, you insert the edges into a disjoint set data structure(actually you do it during taking the input). You find the representative of that tree and then let representative be r. So you mark
longest[r] = L. Here is a thing , the longest path in a tree is called the diameter of the tree.So , we have found the longest path of each tree. Now, answering query 1 is pretty straightforward. You find the set-representative r and print longest[r]
for the 2nd type , note that , for a component , if longest path is divisible by 2 you can take the middle vertex(the center) otherwise you can take any of the middle two vertex. So if you choose this way , in both component where x and y lies, the path length will be (Let r1 ,r2 be representative of x,y)
ceil(longest[r1]/2)+ceil(longest[r2]/2) + 1. Now when you connect the component , the new longest path will be maximum between previous two components and this recently emerged path through x and y.note , if you connect to any other vertices you dont get shortest long path, why ? let you have choosen u and v that is not center. then the longest path is
(larger radius end1 -> center1 -> u -> v-> center2->larger radius end2)which is defineitely larger then previous.Hope it helps.
What is the intended solution of task E?
My submission(7390143) is just an O(nm) brute force with few pruning:
If x[i] < x[i+1] < .. < x[i+k] then start with x[i] is not worse than x[i+1], x[i+2], .., x[i+k].
If x[i] >= x[i+1] >= .. >= x[i+k] then start with x[i+k] is not worse than x[i+1], x[i+2], .., x[i+k].
Since the range of number is 10^4, the number of computation will be under 10^5 * 10^4 / 2. (worst case is x[] = {1,2,1,2,1,2,..})
{1,2,1,2,1,2,..} isn't worst case. With test
x[]={1, 10000, 2, 10000, 3, 10000, 4, 10000, ...}your code works 4 seconds.Suppose you have partial sums at S[]. I used the fact that if you calculate f (i, j) starting at x[k], then you have
f(i, j, k) = (S[j] - S[k]) + (i + k - j) * x[k]
Which is a line, so you can use something similar to convex hull trick to get best k in log n: 7397318
In problem D
solution can pass: 7401453. Is it ok?
UPD. 2808 ms with some shenanigans: 7401820
UPD 2. Looks like tests are weak and there is no test, where all query operations make more than 2e9 operations... 7401924
UPD 3. By the way, in lots of tests you do not need to output anything and there (if I am not mistaken) are no tests, where q = 105 and you need output several (but less than 100) lines. Of course, such testset is vulnerable to obvious pruning: if you have nothing to output don't do anything.
UPD 4. Anti-bruteforce tests were added. Thanks to authors.
I love this contest, even I could't go to orange in this round :( The problem C in div 1 is interesting. Love it. I expect more Div 1 rounds from guys.
In Div2 E/Div1 B, is the case of n=1 and the length of string = 100000 in the test? Some people use recursive, but how do you decide whether you can use recursive or not?
Problem B Div2 :
What is the difference between these 2 codes ?
Hacked : http://mirror.codeforces.com/contest/456/submission/7385428
Accepted : http://mirror.codeforces.com/contest/456/submission/7399213
I don't know how scanf read overflow integer, but i think the accepted solution using int got super lucky accepted, since both solution is wrong because N can far exceed the limit of int or even unsigned long long, and should't always produce the correct answer.
As it was mentioned in the previous comments, cin will just overflow the integer while scanf will input the integer mod 2^64 (not completely sure on this). Since 2^64 is divisible by 4 (which is what you're checking), it apparently doesn't have any effects on the result.
=>
He is really lucky
Problem Civilization is very similar to IOI 2013 problem Dreaming. During the competition itself I simply took my old code for Dreaming and modified it. I had some bugs and it took me more time to fix it than it would to code a new solution, however in the end this problem is just a simplified version of the IOI problem.
I am new to Codforce. plz tell me where to find the solution of codeforce round #260. thanks
The official editorial hasn't been published yet, hopefully Mediocrity, netman or randrew publish it soon. On the other hand, you could just open the standings, double click on the points of some solution and check his code, trying to understand his approach.
Thanks. I saw some editorial in Recent action column. In every round does author publish editorial?
Some competitions end up with no editorials, but they usually publish.
For problem Div 1 D, I am getting accepted using vector cnt in the struct block, but when I change it to int * cnt, I get wrong answer on test case 5. Actually it is giving garbage value on a specific index.
Accepted Code
Wrong Code
Please help, thanks in advance !!!
It's because of your memset. sizeof cnt is 8 and so you don't fill the whole array with 0. I replaced sizeof (cnt) with sizeof(int)*N and got accepted.
Yes, I got that, Actually it has become kind of habit to use memset in that way, It wont work for pointers correctly. Learnt a new point, Thank you so much :)
never, ever use pointers explicitly in programming contests!
JuanMata: I did that to optimize my code, because code was close to TL.
Round Stats
Why are people downvoting this!
don't try to understand logic of voting on CF.
EDIT: now the comment has +6. :)
these people argue that his contribution is increasing. in their opinion, he's cheater
I can explain it. Several people asked this guy to post his stats in separate blog and post the comment like that after each round. Instead of that he keeps posting his round stats every time in blog posts and it pops up in Recent Actions. I consider these blogposts as spam. I don't downvote them but they annoy me and I would downvote them with pleasure if I don't have other things to do.
Я очень удивлён, что таска С такая лёгкая ( жаль на самом контесте я этого не увидел).
Problem A Div.2 I don't sort and accept O(N) , but have many people sort, even Editorial use sort O(N log N). My submission
Is the editorial actually coming out in English at all?
in problem C div 1 when we calculate the diameter of the new tree why do we mazimize between the 2 small trees ??
Because when you merge two trees its diameter will be the length of its longest path. It is not about maximizing, it is about diameter definition.
More precisely, in this problem we are merging in a way that the diameter of the resulting tree is minimized. Merge means adding an edge that connects two separate trees. The optimal way to do this is by connecting its centers.
Trees can have one or two centers. If a tree has only one center its eccentricity will be exactly
, if a tree has two centers, they will be adjacent and they will have 
as eccentricity. Both cases can be summarized as the ceiling of 
.
Finally, when you merge two trees, you must take into account that the resulting diameter can be the diameter of one of the original trees, or the new longest path created by connecting its two centers. That's why you see this max formula on this problem.
Ignore this; it seems that the English editorial is up.