Доброго всем времени суток!
13 августа 2015 года в 19:30 MSK состоится очередной раунд Codeforces #316 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.
Это мой первый Codeforces раунд. Надеюсь, он вам понравится.
Хотелось бы сказать большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.
Участникам будет предложено пять задач и два часа на их решение.
UPD: Распределение баллов по задачам 500-1000-1500-2000-2500
Желаю всем участникам удачи!
UPD: Всем спасибо за участие!
Поздравляем победителей!
great contest :))
I'd prefer 11:30 pm than 9:30 am (my local time), when I need to be in the office working.
No reason to complain, guys — this is Internet (i.e. INTERnational NETwork) and international site. Get used to it.
I almost thought Internet stands for International Network :)
In my city is 00:30 pm QAQ
Me,too.And I had to wake up at night to join the contest.
i just want to don't see unrated Participants as firs & second & third ...
Is it rated?
please answer me for this important problem :))
why ???
why why?
Yes
seriously?????
You change my life by this answer
You are My hero :))
i just don't want to see unrated paticipants as first & second & so on ...
*don't want to see
get it
in my city is too late,it start at 00:30
wo zai zhe li yong pingyin ying gai zhi you ni neng kand de dong le~
What about the point distribution???
Distribution be declared a later
О, Стасян:D
:D
Lets hope this round features a variety of problems with less math :P unlike the previous round
Why? Math is love, Math is live!:D
You won't gain anything Erilyth if all the problems are a piece of cake (except high rating).. It's better to learn something new and this doesn't mean necessarily a low rating by the way :)
Are you saying that all non-math problems are a piece of cake?
I'm alright with math. I just hope the problem statements are a little bit easier to understand.
I think the good round should include problems from different topics ... because if you are not good at a topic you can find another problem with a topic you are good at .. and this will be fair:)... but also math is very important and any programmer should be good at it.
I haven't solved a single good question this week. How do you guys stay motivated? Please give me tips. I love coding, but sometimes, I just don't feel like it, but that won't do. Please help :)
The key is to upsolve once the competition is finished. In other words — read the editorial and solve everything you weren't able to solve during the competition. This way you learn from your mistakes and get better.
My main motivation is that I'm getting better with each competition. When I started Codeforces I struggled to solve A and B, now I'm consistently solving C and pushing towards Div1.
2 hours is a very small amount of time to think about all the 5 problems. Then editorial comes within the next hour, so, 3 hours in all. Shouldn't you spend at least a day before jumping to editorials? Besides, looking at editorials suck out the joy of solving a difficult problem! I like to give the problem a fair shot before I open editorial. Why is your method more effective than mine, can you explain?
I might have expressed myself wrong. I don't look at the editorial immediately after the competition, and if I manage to get some kind of an idea (or anything to work around) within an hour or two, I try to solve it without an editorial.
That makes sense now
Let's look at it in a different way: don't you think that wasting whole day on a problem is bad, because you might spend that day on learning much more things instead of reinventing the wheel?
If I can re-invent wheel, who knows what else I can invent! In terms of ratings and contest performance, I can see my method is hardly efficient......but it is so much fun! I learned DP(whatever much I know about it) almost on my own... I learned LIS in n log n on my own.... and just a few others.....
I heard similar ideas from people who are performing much better than me, so the fact that your method doesn't work for you (at least so far) doesn't mean that it is bad method in general. Maybe you need more time, maybe you simply aren't trying hard enough.
From my point of view — it may make sense when you already know all basics and you are currently working on improving some "thinking skills" or stuff like that — but at the very beginning, when you simply need to learn a lot of different stuff, it doesn't make much sense for me.
I know I lose motivation easily(I don't practice hard) .....that's what my first comment was..... :/
congrats you finally got into div1 !! Happy for you ! and i m experiencing the same too !
Автор не пожелал удачи... Поэтому желаю всем успехов на раунде, побольше подъемных задач и успешных взломов, а так же высокого рейтинга. Ну а я буду решать вне конкурса :)
UPD. Теперь все в порядке.
Наверно автор увидел твой комментарий
Спасибо, чуть не забыл)
О, ASСтас :D
Привет!
Автокомментарий: текст был обновлен пользователем josdas (предыдущая версия, новая версия, сравнить).
This will be the best contest of this week
On this site at this time.
I think this is the last contest of August.
Why do you think that?
591 unrated users ... wow.
591 unrated users and counting.. ok.
Don't submit code. Solve in silence. That's how I'm going to do it
Hi guys! This is my first contest and I hope not the last. I hope that one day we will take part in CF-International:D GL && HF!
Woke up in the middle of the night, and find out that I didn't register after finishing problem A...
Cheers!
Как по мне сложность задач оценена неправильно. По моему задачи скорее вот такие: B, A с подвохом, B, E, E.
Кого тут интересует твое мнение покажи пальцем пожалуста??? На реальных олимпеадах вообще нет ни разбаловки ни сортировки задач по сложности!! Привыкай читать все условия и следить за тем что решают другие ребята!!!
Я думаю, моё мнение, как участника раунда, будет интересовать проблемсеттера. Тем более это его первый раунд.
Спасибо за отзыв, в следующий раз учту.
Стас, при всём уважении, разбор написан слишком кратко. Мне кажется, что далеко не все Div 2 участники могут разобраться с настолько кратким разбором.
Если будешь делать ещё контесты, то делай разбор наиболее подробным, так как на CF есть пользователи совершенно разного уровня знаний, а разбор, вроде как, делается для всех.
На счет разбора я понимаю, мой косяк. Писать начал поздно и просто не умею подробно все оформлять. На будущих раундах отведу больше времени на это.
как решить С?
Например так: http://pastebin.com/Wg9BUS1v
Ответом на запрос является количество точек в строке минус количество групп, образованных подрядидущими точками.После изменения i го символа нужно обратить внимание на i+1 ый и i-1 ый символ строки, Если i ый сивол точка '.', то он может дополнить одну из групп(в который входит i-1 ый символ или i+1), объединть две в одну(i-1 ый и i+1 равны '.') или образовать новую группу из одного элемента; теже мысли также обощаются на разъединие групп.
Спасибо, помогло лучше чем разбор :)
How to solve D?
http://mirror.codeforces.com/blog/entry/19753?#comment-245874
E was almost exactly http://www.usaco.org/index.php?page=viewproblem2&cpid=553
Only difference was it was a rectangle, not a square...same constraints, modulo, and all.
I noticed that and still managed to screw it up... damn rectangles.
Same XD
too many hacks on problem B
Only tricky case was 1 1, right?
No , I hacked 2 or 3 codes with "3 2"
My hacks were :
1 1
5 3
The contest was really nice, especially C and E.
Congratulations radoslav11 you made a perfect contest.
Thank you :)
Hacking Contest!! it's very nice :D
Thank you josdas. Nice problem statements, and not strong pretests -> posibility to hack :)
This round was very interesting thanks to the 'Hacks'. I've never seen Div. 2 this passionate about hacking.
Did anyone solve E with hashes??
How would you do it? There is too many possible paths = too many strings to hash.
I tried hashing, but my solution exceeded the memory limit. In hindsight, it obviously wasn't going to work as there could be (500 * 500 / 2) ^ 2 pairs of positions, which is well over 256MB when hashed into longs.
Did your solution work?
Isn't it something like 2^500? How could you achieve (500*500/2)^2?
My submission
I kept track of two positions while running a DFS, with one starting at (0, 0) and the other at (N — 1, M — 1) and continuing until either the two positions met up in the middle or passed each other. To take care of overlapping paths, I hashed each pair of locations. There are (500 * 500 / 2) possible locations for each the first and second positions, giving a total of (500 * 500 / 2) ^ 2 possible pairs.
ok, it makes sense. Though I don't see a way to improve this solution (cutting memore consumption for example).
Wasn't E too basic/known? At least, I have thought of the same problem a few times when I don't have what to do :D However, it was a nice contest, I liked D :)
Same here.
How to solve C?
With segment tree. If at i-th and (i+1) positions there are points then we have 1 at our segment tree. Answer for query is sum on whole tree.
With string. For every query you look into substring with wide of 3 chars: at query position and +-1 positions. Then you remove from counter the number of possible '..', change query letter, and then add the new number of possible '..'.(12518363)
For D, how to make projection of arbitrary point to arbitrary depth?
Ok, found in comments: DFS with timer (sample submission by FatalEagle)
D has offline solution, right?
Вот это по-настоящему эмоциональный контест! Спасибо за него! Респект таким пацанам!
great contest ! thanks ":))
This contest had a really good difficulty curve.
A,B,C easy, D,E very tough (if you never solved something similar)
It's a lot better than the usual CF contests, which have ~3000, ~2000, and then ~500 solutions, because it let's beginners solve more problems than usual. Although I do agree that D and E were very tough relative to A,B, and C, moreso than usual.
Контест взломов!! Всегда мечтал!
problem D strict time limit :/
... and memory limit :)
Room topper for the first time :D
problem D strict time limit :/
No. For D there is a O(N + Q*logN) algo. Your code is O(Q*26*logN) which should be TLE.
Can you describe the basic idea of the solution? Thanks
Key steps:
FatalEagle got AC with Q*26*logn complexity. See 12502770
My code with same complexity got TLE'ed. :(
My solution is the same U_U , but i got TLE.
Submission
I figured that the constant is low enough so fast input should make it work (input can be very huge).
Your solution with fast input works too: 12517730
I have seen that using the upper and lower bound of C++STL directly in the main , is faster than make a function calling upper and lower bound.
TLE
AC
I got AC by defining my array as 5*10^5 * 26 rather than 26 * 5*10^5. But for similar situation on Codechef defining like the latter one had less overhead than first one. My AC'ed submission after making these changes. 12517583
This was the codechef ques where we had to do the opposite to get 100 points. Codechef Ques
Not sure what is happening here. o.O
You get more cache hits in the first way, since you want each letter of each level instead of each level of each letter (in which case 26 * 5*10^5 would be the better way of declaring the array).
Thanks. That makes sense. :)
is using lower_bound/upper_bound STL faster than implementing binary search? because with the same complexity as yours, mine get TLE.. my submission
mine O(Q*26*logN) solution got TLE What is correct approach though?
Time Limit was weird. My code with the same O(26QlogN) complexity passes in 1980 ms . This seems unfair towards many participants .
Link : 12513092
yeah, I had same implementation with vectors and STL lower/upper_bound functions. I got TL when submitted it, and decided that it should work fine if I remove vectors and STL lower/upper_bound functions, but this did not help either. :( I do not really understand why my solution has bigger constant though :( I'd like to understand it.
Very nice idea with bitwise xor's!
Nevertheless, my solution similar to yours gets TL. Could you tell me why?
Unnecessary strict constraint i think , a improve of a 26 constant is not a big improve in my opinion . BTW the problem was very interesting.
I think you misunderstood my comment. It was NOT 26 --> log, it was 26*log --> log, which makes the program 26 time faster.
oh, I think I got it. We have to use bitmasks. thanks for the hint.
I mean a 26 constant improve is not a big improve in my opinion , i think a nice improve is taking for example improving n^3 to n^2 , and if someone really like improving some kind of things of contasts , there is a lot of problems in SPOJ that you can solve , i know that my algo is 26 n log n and it past pretest , but fail in system test.
Well, maybe the 26 constant improve is not a big improvement according to you. But, there's also a O( n + 26 * q) offline solution, which might be a bigger improvement according to your judgment. Link: http://mirror.codeforces.com/contest/570/submission/12517417.
It's improvement big enough to distinguish solutions by time. So it is a big improvement.
my O(Q*26*logN) got AC :)
how to optimize it to O(N + Q*logN)?
UPD: sorry my code is O( Q*( 26+ log(n) ) ), but it took about 1800 , strange!
Unfortunately mine not.. To take away 26 you make xor sum on BIT,and every character is represented as a bit.
If the answer on interval has more than two 1 bits in its binary configuration the answer is no.
Xor helps you for parity,because 2 bits of the same (two 1's) make each other disappear.
Really strange. I have the same idea. 12517064 — 967 ms.
i upsolved D using this thing: "if there r no letters X in subtree of vertex V -> continue;" passed in 1300 ms
http://mirror.codeforces.com/blog/entry/19753?#comment-245981
Changing 26 * N array to N * 26 array gave changed TLE to AC :/
Haven't read B statement to the end. I can't understand what the importance to the player of which number he chooses — bigger or lesser if it gives the same probability to win...
Хнык хнык(3 таски слетели)
Are future contests going to be scheduled on weekends? I know many of us have school starting soon.
Agree x100000. These contests are in the middle of school for me at 11:00 or 11:30 AM. Would be really nice to have them on the weekends.
The only thing I've thought about in D was to cache the parity of all descendants of a node on all child layers in that node. This could occupy a single int per node per layer, if encoded as a bit string. However, this wouldn't be enough, since it's obviously an O(n^2) solution in terms of both memory and time, so it is definitely not feasible when n=500 000. How did you solve it?
UPD: The shortest submission 12506489 is also quite clear. I guess using a DFS clock and then binary searching on each layer is a standard technique.
one of my friends :
here
I think i can relate to it.
Not reading whole problem, or reading it incorrectly is a major issue for me. I don't know what happens during a contest, so i got three WA in problem A.
Weak pretests in problem B :'( I can't believe I missed the "minimum" part ._.
Codeforces Round #Hack (Div. 2)
From CF Round #Hack (Div. 2)
What were the states and transitions for the problem E dp?
dp[x_first][y_first][x_second][y_second], but this will TLE and ML.
So we can convert the state into dp[x_first][x_second][len] witch is O(N ^ 3) Memory and Time.
Can you please explain in a bit more detail, the DP solution for E?
Thank you for such a wonderful contest!
How did someone hack 24 solutions? can we hack people's solution from other rooms ?
You can easily open a room and see that there are more than 24 users in a room
There are 26 contestants (at least submit once) in our room, including myself, and only 23 of them pass at least a problem's pretest :)
But you can hack one person more than once.
Yes, so i am just pointing out that the number of users can be less than the number of hacks.
you can hack a person more than once and you can hack more than one problem .
Also, it's possible to hack someone's solution twice. Submit, hack, resubmit, hack. Of course, the hacks must be distinct cases because resubmitting requires the submission to pass previous hacks.
Why this code http://mirror.codeforces.com/contest/570/submission/12498380 passed system test ???
It should be wrong answer. For 11 6 test it will be generate garbage value.
try 5 3 , it should generate garbage but it gives 4 !! can anyone explain why this happens ?
Try custom invocation. Miraculously it gives correct ans for this and all other cases -_-
I think compiler removed "if(l>r)" since "a" wasn't initialized anyway.
http://mirror.codeforces.com/contest/570/submission/12515787
Code works fine on my pc as well as [on ideone].
However, same code gives tle on codeforces for same test case of n=5. What is the reason? (http://ideone.com/G1AApF)
I guess you have some bug (like checking array[-1]) and it causes undefined behaviour. Then everything could happen.
I can't find it! :(
E.g. here is checking s[n] — "while(s[i]=='.' && i<s.size())". Use custom invocation to debut 5th test. You can comment part of your solution and check if you still have TLE.
This may be a dumb question but .. is the 'problem set' page temporarily blocked during a contest ?
josdas Thank you for this contest , keep going :)
задача Е несколько месяцев назад была в US Open 2015(USACO)
Добрый!
Я новичок, недавно зарегистрирован. Вердикт по задаче "Решение взломано" http://mirror.codeforces.com/contest/570/submission/12506136
Можете пояснить, как считается что "Решение взломано"? или ссылку на правило где про это написано!
Спасибо!
сылку?
Переходим: Главная страница -> Помощь -> "По каким правилам проводятся соревнования?"
Автокомментарий: текст был обновлен пользователем josdas (предыдущая версия, новая версия, сравнить).
Got five successful hacks on B using the "1 1" test case.
After system tests: WA on "1 1" case.
Dammit.
At least you have gained more than you have lost :P
Problem C = KISS
Keep It Simple, Stupid!
:( I never learn
Auto comment: topic has been updated by josdas (previous revision, new revision, compare).
That moment when you make 3 problems in one hour and you realise that you did the first problem wrong because you did not analised the simple case ..... So disappointing. But still my rating raised. A positive note though.
thank you for contest!:)) we want Editorial fast :((
By the way, the second problem from here is pretty cool: http://mirror.codeforces.com/blog/entry/17291?#comment-221267 :D Seems like this was the source of my thoughts about such problem.
How to solve E?
You will start travelling in both directions (from the upper-left to the lower-right and from the lower-right to the upper-left). For making it simpler, we can make a copy of the input matrix and rotate it on 180 degrees so we move in the same direction in both of the matrices. The dp state will be dp[row1][col1][row2] (the number of ways to reach those cells and have the same strings so far) since from this we can get col2=row1+col1-row2. We can notice that if a[row1][col1]!=b[row2][col2], then dp[row1][col1][row2]=0. Otherwise dp[row1][col1][row2]=dp[row1-1][col1][row2]+dp[row1-1][col1][row2-1]+dp[row1][col1-1][row2]+dp[row1][col1-1][row2-1] so we need the information only for row2-1 so we can store only the last two tables. You can take a look at my submission for more details, although it looks really crappy.
Firs 3 problems so eeeeasy! NOOOOOOOOO! Why did I miss this contest, I am such a looser, guys!
I hope you were successful on the other front.
У меня одного архив не доступен?
Although this may seem stupid, but can anyone explain how to solve Div2 Problem B?
There are two main cases we can check:
Either there will be more numbers between N and M, or there will be more numbers between 1 and M
Take this set of numbers, for N = 10, M = 3
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
M is 3^
Notice that choosing 2 will mean you win on 1 or 2 Now look at what happens if you choose 4: You will win on any choice from 4 to 10.
In this way, you want to choose either (m+1) or (m-1), based on what would give more winning numbers Some code might look like
if (n — m > m — 1) print m + 1 else print m — 1
.... and don't forget to print 1 when n = 1
Thank you, that was really helpful :)
Don't feel ashamed to ask questions!
Auto comment: topic has been updated by josdas (previous revision, new revision, compare).
D had a very simple offline solution too in O ( N + Q * 26 ) !! here is the link to it http://mirror.codeforces.com/contest/570/submission/12505776
Hi,
I can't figure out what's wrong with my solution for D... Here it is: http://mirror.codeforces.com/contest/570/submission/12521712 Please help!
Не мог бы кто-нибудь, пожалуйста, объяснить, а то никак сам понять не могу. Мое решение на задачу В было взломано тестом (5,3), оно вывело ответ 4. Почему он не является верным? Спасибо.
Ответ 2. Там вероятности выигрышей и у 4 и у 2 одинаковые (так как m — центр, в данном случае), но в условии сказано:
Если таких значений несколько, выведите минимальное из них.Жалко, что на задачу D такие жесткие ограничения — она очень похожа на задачу 208E - Братья по крови, однако я не смог запихать такое решение по памяти :(
Решение все-таки зашло после замены deque на вектора.