Hello, Codeforces!
Codeforces Round #278 will be held at Nov/21/2014 20:00 MSK for both divisions. Note that the time is 30 minutes later than regular Codeforces time, and Moscow is currently UTC+3.
The problem setters are taorunz and me. This is our first Codeforces round!
We'd like to thank Maxim Akhmedov (Zlobober), who helped us prepare the problems very much; also to thank MikeMirzayanov for Codeforces and Polygon platforms.
This round is involved in MIPT Fall Programming Training Camp, and top-20 of contestants from the camp will be rewarded with Codeforces T-shirts. For other contestants it will be regular Codeforces round.
Hope you enjoy the round, and wish you high rating.
UPD: Score distribution:
Div. 2: 500 — 1500 — 1500 — 2500 — 2500
Div. 1: 500 — 1500 — 1500 — 2000 — 2500
It's not for everyone that the optimal strategy is solving tasks in order. Make sure you've read all problems before the contest ends.
UPD: Very sorry that the round will be moved 20 forward due to technical reasons.
UPD: Top 5 participants:
Div.1
Div.2
Honorable mentioned:
anta, who solved Div.1 E!
CKYang, who solved Div.2 E!
UPD: Editorial is here!
> "top 20 contestants blablabla CF T-shirts"
> reads it again
"from the camp"
Yes, that's what I found out when I read it again.
I agree, this valuable information could be spread among participants attending the camp.
No necessity to write to others about t-shirts which could not be received by them :D
It gives additional motivation to visit this camp in future:)
Oh maaan , the time is too late for me.
Its never too late for a Codeforces Contest!!!!!
Only too early :-D
i guess codeforces took me seriously another 20 minutes delay
Today is
Nov/20/2014— are you really writing about the date in past?I think he want to express Nov/21/2014.... Because the url is http://www.timeanddate.com/worldclock/fixedtime.html?day=21&month=11&year=2014&hour=20&min=0&sec=0&p1=166
Very sorry that the round will be moved 20 forward due to technical reasons.
Two amazing events in one day :
1.A (maybe ;) ) rated Codeforces Div.2 + Div.1 round after a long time.
2.Hunger Games Mockingjay part I release.
Oh my god, the time is unscientific， it's toooooooooo late
I want a T-shirt..... I haven't get the T-shirt of Codeforces! What a pity!
Omg
one contest after another
really cool...
if you start ten contests on a week i will join all of them...
ツ
top-20 of contestants from the camp will be rewarded with Codeforces T-shirts
There's no chance for us
It's all decided for us
This world has only one sweet moment set aside for us
...
Here's a problem you may enjoy: http://cerc.tcs.uj.edu.pl/2012/data/b.pdf :). (In fact with really cool solution!)
Really do not like that time.
First contest that forces me to participate until 24:00 :)
And this comes in a day that tomorrow i have region olympiad :(
I think i will not wait for system checking and updating ratings today.
The contest is prepared by Chinese but I really don't think it is prepared for Chinese because it will start at 1:00 am UTC+8.
Maybe we want to make something different from previous Chinese rounds. As you can see, no one is here saying anything like "yet another Chinese round, huh?"
So ? You do not want the Chinese coder's to do this Chinese round?
I think it should be a Codeforces round first.
yet another Chinese round, huh?
Please consider Chinese coders' sleeping time. Contests starting time has been moved from 23:30pm to 01:00am now, so sleeping time of Chinese coders moved from 01:30am to 03:30am.
my mistake: 03:30am -- > 03:00am
Why do the Chinese have so much problem with staying up late ?
Late night contest is great adventure
This unusual start time is good for me. I can start contest after taking my dinner :D
I want to take part in this contest because of the e-mail says: Attention! Unusual start time: the round starts on Friday, November, 21, 2014 17:00 (UTC). However , this time changes. I cannot do it now. Chinese people don't want to the Chinese one's to take part in? OK . OK.
It is 17:00 UTC, isn't it?
Yep. 20:00 (UTC+3) == 17:00 (UTC).
the later 2 days is one of China Regional Contest....SO, most of coders will decide to have a good sleep.
So why you not?
我是来测试一下能不能发中文的
wat?english pls
Translated by Google :-D
He said:"I just come here and test if it can post Chinese."
(sigh)
For Japanese, it starts in 2:00 AM and too hard to participate...
In Arabic, "saffah" means a murderer! i hope this has nothing to do with today's contest :D :D. No hard feelings bro :D
Okay this name is randomly typed when I was 9 years old and needed a nickname......
Just like WJMZBMR... randomly nickname.
In what place have you used this nickname first time? (just curious :D )
Baidu Tieba
Well I guess it had many things to do with the contest xD. It was a MASSACRE! :D :D.
It seems so late, maybe I will be hungry at half.
oh my god! 1:00 am! I have a class tomorrow morning ==
I bet there will be at least 1 pure math problem! :D Because it's a Chinese round...
Close condition?
It's not a typical Chinese round.
(At least the time is unusual, isn't it?^_^)
We hope to break the stereotype about Chinese rounds.
hey guys plz unlike me
hope for some dp!!!
Loving this series of CodeForces Rounds :) ..
playing clash of clans and coding and coding and coding in CF.
thanks MikeMirzayanov
Google==codeforces
I love codeforces and Google too:)
The links now work as "No such blog entry" = "No such blog entry". You need to start links with http://, or they'll be considered internal.
I also think :)
Too late for Chinese.T_T
Interesting score distribution!
can't wait. want to see new winners and at first get in div.1 :D good luck everybody
a3333333... why :'( !!
Is B harder than usual?
Please don't delay the contest! I have to go to school tomorrow and now the contest will finish at 11:00 PM in my country! :D
20 mins delayed?!
Why delay the contest...
If you were here in MIPT Fall Training Camp, you wouldn't even ask :)
What!! It's been put off...Oh no, i must go to sleep
very bad :(
So for this time does "technical reasons" mean "dinner on training camp" again? :D
so we are waiting for them to finalize their dinner :D
I know nothing about their dinner, but i was able to finish my dinner thanks to this delay :Ъ
well atleast somebody's happy for the delay!!
good rating 500 — 1500 — 1500 — 2500 — 2500
Seriously O_o
Moved is always better than unrated ;-)
Better hope it won't be unrated in the end, then :D
You are right, hopefully the'll fix the problem completely not partially, we will see...
[Deleted]
Задержка — это плохо =(
А нельзя уже сделать как на топкодере, контесты в разное время? Я, конечно, понимаю, что основной контингент хороших программеров России обитает в Питере, Москве, Саратове и им удобно, когда контест начинается в 19-30, 20-00 и т.д., но чем восточнее город, тем решать становится сложнее, и реально не прет решать задачи на ночь глядя после рабочего дня и ещё 4-5 часов ожидания. Просто сложно нормально выступить, даже если ты неплохо кодишь.
В следующий раз я забью на все правила конфиденциальности и не затру имя и фотографию.
Что-то последнее время на codeforces вообще много странных личностей развелось, то решения просят, то постят всякую ерунду в блог. Кажется, пора как на хабре, систему с инвайтами вводить %)
"Note that the time is 50 minutes later than regular Codeforces time, and Moscow is currently UTC+3."
Why profiles are locked?!
I can't even open my own profile.
UPD- Now Everything looks ok.
For no chitting mb=)
to reduce the load I think
Yeah, that's to prevent cheating and begging solutions during contest.
That has already happened during last 3(/4?) contests.
it seems we should expect so many "Codeforces is temporary unavailable" during the contest !!
Is it unrated again?
Сделайте, пожалуйста, чтобы при нажатии на регистрацию на контест, если человек не залогинился на сайте, его отсылало на окно логина, а потом на окно регистрации на контест, а не как сейчас — только на логин. Уже второй раз пропускаю из-за того, что думаю что зарегестрировался, а оказывается что нет. Или возможно подсветку красным-зелёным окна, где написано время до ближайшего соревнования.
Its really disheartening and frustrating when you cant submit a code for like half and hour just because servers are not working.. :\
За 50 минут до конца:
А мне начинают нравится китайские раунды. И пофиг, что по А было TL4 и WA3.
Как-то мало во 2 диве взломов в топе оО
Мало кто может решить С... Я прям до последней минуты сидел и ждал, когда же еще кто-нибудь тупой перебор зашлёт)
Что не так с перебором?! :D
Зависит от перебора. Если перебирать все 3 значения, то можно упасть на том, что иногда выгоднее накупить много (больше того, чем многие ограничивали перебор) дешевых жизней, чем немного дорогой атаки/защиты.
Тест:
Все упорно перебирали характеристики до 100, в то время как атаку нужно перебирать до 200, а хп не скажу точно до скольки (но точно не более 10000).
На тесте
1 1 1 100 100 100 1 100 100необходимо купить 990 хп.В 1 диве со взломом этой задачи намного веселее было)
Я заметил: у I_love_Tanya_Romanova 16 взломов)
Keep getting "Server down" errors for the last 15-20 minutes. Need to cancel this round for sure.
I don't know if It happened only for me (!) , but CF kept "Connecting ..." for me half of the contest, and was "Temporary Unavailable" for another 15 minutes! Couldn't even submit ...
Guess It wasn't only you ... :|
I left the contest ~1 h ago
Nice contest ^_^
When I saw so many people were getting extra points by hacking A, I thought to give it a try myself. Then I found that almost all the hacks in my room has already been taken by someone. Not to mention, I couldn't think of any tricky case either. What case did you use?
I tried to find minimal test case to let people do the same mistake again =) Most of all can beat with follow test case:
1 2 1
2 100 1
1 100 100
And second test (for those who tried to fix solution but failed):
1 2 1
30 100 1
1 100 100
What should these test cases return?
first: 198
second: 994
Ehooo, i hope i'll get AC
True rampage! You are amazing!!!
Your room mates hate you, I'm pretty sure :-D
To tell the truth I have found mistake in my own solution. =)
Actually he is doing them a favor. It is better to know that your solution is wrong earlier in the contest than towards the end, or not know it at all. :)
Did you add your profile pic now to go with the picture? :D
No. But it fits perfectly :)
poor people. :D
забавно, что на тесте
1 1 1
100 100 100
1 100 100
у тебя падает)))
Your profile pic + the image = perfection =))
Very nice problems. Can't wait for the system test to end so I can submit solutions at C.
was hard problems mostly mathematic so i couldn't write good. but i love math and hard problems really waiting for editorial(tutorial).
...yet another chinese round...
Is that enough to check attack decrease up to 100?
1 1 1
100 100 100
1 100 100
answer is 11890(i hope xD).
Thanks,
No, for example
2 1 1
100 2 100
100 1 100
requires increase attack by 199
Attack decrease (that is, increasing defense) is enough to 100; once your defense is more than the opponent's attack, you won't be harmed. But attack increase must be checked up to 200, an HP increase must be checked up to 10000. (Someone in my room used 1000 and passed, but 10000 is easier to prove.)
No. There is a easy test when you need 199
Solution to C:
n must be prime or 1 or 4 (trivial), so let n be prime number
a1 = 1, an = n and ai = i / (i - 1) :>>
i/(i-1) = 1 (i >= 3)
Division is handled in Zp field. In other words, i / (i - 1) = i·(i - 1)p - 2 mod p.
...I tried to figure out whether 9 is possible or not, since I saw that the primes and 1 and 4 worked. I should have just hardcoded the solution for 4...
Why cannot n be a degree of a prime?
Because we have p and 2p, if p > 2, so for p2 number 0 will occur too early.
If n = pk, k > 2, then we have p and pk - 1.
Because for non-prime N, (N-1)! mod N = 0, since N has to be last, we'll get two 0.
Except for 4, which I forgot. I can prove it for all non-primes except perfect squares — you just decompose the number into prime multipliers and then get rid of powers — all of numbers are distinct from 1 to N-1.
Same here, forgot 4 and will get 0 for this apparently =( Hate these rules, why can't we get partial scores or see the results right away.
4 should be in pretests... You would force people who didn't see it to lose points, but they wouldn't get 0.
No, 4 should not be in pretests. It makes good hacks. (And 1 too.) That makes people need to figure out all corner cases.
It also disbalances the contest completely.
Your argument that the contestants should adapt to the rules applies to any system, good or bad, so it's not relevant here.
You can have all the codes in your room hacked by someone in your room who saw the corner case 5 minutes earlier, and therefore has 700 points more than you do now. In that case hacking was never an option for you.
Ideally, the system should be as little luck-dependent as possible and as fair as possible, in that it allows for people who performed similarly in a contest to be placed in similar positions. What I mentioned above is an example of that not happening.
Which simply means you need to practice to find corner cases faster?
I don't see any luck involved among contestants in a single room (barring server problems and so). Which means I should suggest that rating updates only see people inside a room, but that will make a single position up or down to have a major effect in rating, in which those unexpected troubles (server problems) will now have big effects.
Wow, it's much easyer, than I have.
I found generator, and set ak = r(k - 1) * ( - 1)k.
My solution is more sophisticated :| Let n = p be a prime number, We find generator g mod p. Let a be the sequence 1, - 2, 3, - 4, ..., (p - 1) / 2, ..., - 3, 2, - 1 mod p - 1. The answer is 1, ga[0], ga[1], ..., ga[p - 2], p.
Oh, it's the same as PavelKunyavskiy's solution.
Hah, I alredy knew this problem, it was posed on PMO 8 years ago and I have solved it using generators, but later I read that solution: http://archom.ptm.org.pl/?q=node/105 :).
How do you know that ai = i/(i-1) is unique for each i? Is this a known theorem or something?
i / (i - 1) = j / (j - 1) implies i·j - i = j·i - j, so i = j.
Let
i * k = (i + 1)
j * k = (j + 1)
then
(j — i) * k = j — i
then k = 1
1/i is a unique reciprocal of i in Zp field. This is such a number k that
. There is exactly one such number and it can be computed as 
You got lucky you were hacked with 4... I didn't share the same happy ending :)
Haha, yes, indeed I'm lucky :).
I forgot to print "YES" , if n < 5 :(
Used the same approach, can you prove that a will contain distinct numbers only?
i / (i - 1) = 1 + 1 / (i - 1)
Yes. x / (x - 1) = y / (y - 1)(modn) if and only if x = y(modn)
Suppose you have i! = j so that i / (i - 1) = j / (j - 1) < = > i(j - 1) = j(i - 1) < = > ij - i = ij - j < = > i = j, so it contradicts the hypothesis.
Got around 12 WAs on Problem B inspite of checking all possible permutations of the given numbers. Can someone point out certain corner cases?
well, for me I got 6 WAs, re-wrote the code 3 times, and in the last 2 mins, I found that I accidentally wrote 2 instead of 3 xD, (though I still don't know if it'll pass system test or not)
div1, I'll be back!
thanks shigule for nice problem
really !! :D
nice??? :|
nice and very hard :)
Seeing so many people harvesting points through hacks, I got impatient and lost 100 points :p Never doing such a silly act again! Not gonna unless I am sure of what I am doing.
How I can solve problem B?
Div2 B For n=0 :Print 1 1 3 3 or any other satisfying numbers For n=1 :x2=2*x1, x3=2*x1, x4=3*x1 For n=2 :Sort the given numbers. x3=4*x1-x2, x4=3*x1 For n=3 :Sort the numbers. And check if (2*x1+x2+x3)/2 == (5*x1+x2+x3)/3 If true,then print anyone of these. For n=4: Sort the numbers and check them. Take float datatype here as integer may give wrong answer(Hacked 1 solution on this)
I hope it passes final test. I am not sure if it is right.
what about this test? 1 1000000 u forgot that Bi must me non-negative and <=10^6
Problem statement: "The next n lines contain integers ai, denoting the number of candies in the i-th box (1 ≤ ai ≤ 500)."
Candies wont be more than 500 so no need to check for <=10^6. I forgot to include Bi condition. Thanks. I have included it in my solution though.
Nice contest, but I can't pass B problem's 5-th pretest, so good bye blue colour(((
I passed 5th pretest but not 6th. Don't even know what's wrong with my method. Hoping that the editorial comes out soon :)
small bug(
forgot
return 0(((Why B was worth more points than usual? I think it was straitghforward, easier than usual... By the way I really enjoyed problem D, I'm fond of interval trees composing funny things :).
В задаче А див.1 есть тесты, на которых нам будет выгодно брать больше 100 какого-то итема?
109 раз Attack
как минимум 100500 взломов!
Да. 1 1 1 100 100 100 1 100 100
В теории:
Защиты нам не нужно более 100, ибо имея 100 мы сможем отразить любой удар.
Атака нужна максимум 200, ибо в худшем случае, чтобы убить монстра одним ударом, нам нужно пробить 100 защиты и 100 ХП.
На счет количества ХП трудно что-то точно сказать, но рассмотрим вот такую ситуацию: у нас защита 1, чтобы убить монстра когда-либо нам нужно наносить 1 хп, а так как у монстра максимум 100 ХП, значит нам максимум понадобится 100 ходов, чтобы убить монстра. Следовательно, нам нужно, чтобы монстр убил нас более чем за 100 ходов. Допустим, монстр бьёт на 100, значит нам нужно (100-1)*100 + 1 = 9901 хп, чтобы монстр не убил нас до того, как его убьём мы. Но вряд ли в действительности нам когда-нибудь понадобится такое количество ХП, потому что, скорее всего, нам будет выгоднее купить атаку (и ускорить победу), нежели ХП.
Поэтому могу предположить, что достаточным было сделать перебор ХП до 1000, атаку до 200, защиту до 100.
UPD: Нашелся тест, где перебирать ХП нужно до 2000. Возможно, есть и хуже, поэтому лучше вообще отказаться от перебора и вывести формулу необходимого количества ХП при данной атаке и защите.
Можно перебирать до 1e4, т.к мы в ход теряем не больше 100hp и нам нужно не более 100 ходов(иначе мы вообще не убьем). Если добавить break, то это успевает отработать за секунду.
Я по-тестил, тупой перебор 10000 x 200 x 100 не работает, а вот перебор 10000 x HPm + DEFm x ATKm заходит.
8792822
8792817
Достаточно в ваше первое решение добавить бряк, как только мы нашли что-то (если мы выигрываем из состояния (h,a,d) нет смысла смотреть на (h+1, a, d), (h, a + 1, d) или (h,a,d + 1).
Добавил break — все залетает. 8796090
UPD 1 x defence and 100 x attack = 200
Sorry for mistake
why not 100 atk?
yes, 100 atk, my bad
This platform is always crashing during competitions and I can not submit another try during last minute as it keeps crashing. Really think you need to spin up some extra servers for this platform.
in what time it was not working?
During the previous 3 competetions(including today's) it has been crashing constantly .
It was quite rare for me. ( twice at the middle ) Also you can save the statements locally...
The contest was like "Lets hack as much submissions before I get hacked myself xD ".
it was really like this
specially problem B...
let me say the reality
This problems was worst problems that i have seen in contests :(
But like other times thank u that try to make this site better and better
Worst problems because they allow many hacks? I call those challenging problems. Although why do you think they are "worst"? I think they are nice.
Man I'm so slow, I can barely handle Div 2 questions, I have no idea what kind of mindset other experts pack, its like I'm from a different planet, it really hurts my feelings when I'm incapable of solving these supposed to be easy problems x_X
Think about guys who don't even try! You are at-least trying to solve questions and slowly you will be able to solve these questions! I joined CodeChef 4 months ago and I wasn't able to solve even a single question untill my 5th competition and here in codeforces I have not solved more then 1 question! So never lose hope!
Thanks, I been here for 11 months but did not participate much due college and other things however I solved so far over a hundred problems, yet when it comes to real time events, I'm incapable of thinking clearly that it becomes frustrating, I guess its just a matter of time until I get the hang of it, tomorrow is my birthday Q-q , I'll make a wish to break this infernal limit!
Best of luck and Happy Birthday in advance! :)
It is probably psychological then. Just try to approach it as a nice game. Do not treat it as a duty to perform well. Because as A. Einstein said, "Love is a better teacher than duty". I had the same problem for a long time (3 years), I was solving problems on USACO gold and solved some not so small portion of it, I was able to think of algorithms and code it when there was no pressure. However, I was making too much of a deal when it would come to real contests. Just let it flow, try to approach it with love and passion and you will be getting better :) Have fun!
I think your rating will be increase today... 1 problem solved.
Man, Don't feel bad, keep trying and practicing!
You got your Birthday gift one day before see you ratings! :) :)
Hope you will do much better tomorrow or the day after tomorrow contest! :)
Unbelievable, I actually got points UP and saw a new message for the first time haha!!!! My jaws almost broke from over smiling - This is definitely the best thing happen to me over the past few months, even just for once seeing points going up is miraculous, I will no longer feel down, I will keep coding, I will code....FOR THE GLORY! -
Thank you all for the encouragement!!! :D
It was difficult to read solutions of guys from room, because they usually didn't appear, because of lagging, or appeared after a time.
Test for A, where you need to get more than 1000 HP:
Your test upgrade :))
Yeah, I stopped as soon as I got over 1000, because that was a constant in the code. I've also seen 2000 as a constant, but I don't think it's possible to create such a test.
I was too lazy to think tonight, so I checked hit points up to 100000000 using binary search:)
first time ever I see myself on the first ranking page during the contest
probaly means that my solutions are wrong
Oh man. Don't tell me everything is going to be delayed today. The contest started late. Now, the system test is pending. Later rating update will be slow. And finally we will see analysis after a week? lol. Feel like going to sleep (already 2 AM), but can't beat the curiosity to see what will happen to my rating. What a dilemma.
Why it didn`t start evaluation?
Awesome problem set! I'm so gonna be red after this <3
Edit: 2179 ._.
It was very bad contest. CF was not available. It's better to unrated this contest
totally agree :)
I had a bad day, but this contest was good!! I'll never use printf, I promise :/!
But where is 277.75?.. :D
I have a doubt in problem A Div 2
what should be the answer of -5?? 3 or 13
if you say 3 then why the answer of -1 is 9 and if you say 15 then OMG OMG I left more then 5 hacks and what I thought is that my solution is wrong which is giving me 13 on -5
of course it's 13, it says such that, if he walks b floors ""higher"".
For -5, its 13. You can only take "positive" steps. That means you can move forward and not backward.
but what about -11 when I solved it with 19 get a WA while solving this with 3 I got accepted! Wasn't it confusing?
-11 + 3 (minimum) positive steps = -8
-11 + 19 (not minimum anymore) positive steps = +8
I hope its clear now.
Look at 19 numbers starting -11.
Problem B: DIV2: I wrote my solution assuming that the inputs are ordered! After getting update, I had to come up with a complete new solution.The update came after almost one hour. Which means I took part in the round for only one hour instead of two! Will it be fair that the contest is rated for them who faced the same problem (Who misunderstood B and had to re think the problem for a while and rewrite the entire code)?
Same here! It was a completely new problem when they updated and my this round (which could really go well) went too bad! :(
yea agree +1
the is are ordered but not the ai s
Well, that's not right. You weren't promised that inputs are ordered, so you're the only one to blame for that. The autor actually helped you (and me aswell :P), but honestly he didn't have to.
It is always advisable to not make assumptions until explicitly mentioned.
The description told that x1<=x2<=x3<=x4, missing some integers does not change the order! does it? Leave all other cases, my first solution was like : if a valid set(1,1,3,3) is shuffled(3,3,1,1) I as giving NO O.o . I thought they had to be satisfied x1<=x2<=x3<=x4 as well as other three conditions. Anyway , leave it. Those who has experienced problem setting knows that how difficult it is to make statement clear for all. But, I am a bit upset because the clarification took a long time to come, and the contest could be extended for 5-10 minutes.
I could figure out that we would have to order the input in such a case as otherwise a median or range would not even exist if it was not ordered.
How long it takes in system testings ?
Hello Everyone can anyone help on this ....
http://codeforces.com/blog/entry/14789
Time Limit Exceeded for System Testing :D
Height of Revenge : akashdeep :D :D
Maybe you're wondering why your picture doesn't show. That's because you don't link to the picture itself, but a page that shows the picture. You need to link directly to the picture, or it won't work.
Thanks :)
Can't believe missed an endl in problem B when only 6 people solved it, and took me 1:53 to find the problem at last :(
finally the system testing is started!!
and suddenly finished :D
It's time to change the color :D
I hope I change mine too.
Что отделяет меня от 2 места в div2:
for( ll a4 = a1; a4 <= 1500; a4 ++ ) {for( ll a4 = 1; a4 <= 1500; a4 ++ ) {IMHO n=4 for C should have been in pretests. After all, it is just an ugly corner case with with hardcoded answer:(
A contest full of hacks and failed system tests.
Indeed! Never seen another similar to this one
Why did D have a special limit of 10000 change queries? It can be solved in n*log(n), which works fine with 100000.
Could you tell this solution?
Segment tree with mappings. To answer a query, we go up the tree until the left node brings us to an edge or cycle, then down until we reach the bottom of the tree.
Could you kindly give more detailed explanation about your solution? Thanks.
We can express every row as a mapping from 0..9 to either a column 0..9, Left, Right or Cycle. Then we can build a segment tree on these mappings, where each node stores the composition of all mappings in the subtree (from right to left). After updating a row we simply need to update nodes on the path to the root (log(n) operations). To get the answer, we start in the leaf node corresponding to our row, then go up the tree, changing the current column whenever we go left. If we get Cycle, we output immediately. If we get Left or Right, we need to go down the tree to find the exact row where we left the table.
Thanks, I got this idea already by scanning your code. I like idea of Segment Tree with mappings. Could you recommend other problems with this idea?
I misread the task and thought that all "<>^v" are possible and solved that version, 10000 constraint helped a lot.
Wouldn't that make it a lot more complex than simple sqrt decomposition, since you can go back and forth between chunks?
You can do (maybe not so simple) sqrt decomposition on C type queries. For each 100 C type queries mark those cells as important and for each other cell calculate first important cell on it's way. Now when you have A type query you can just traverse through important cells (at most 100 steps, each time you move from important cell to it's successor (probably unimportant cell) and use precalculated data to go to next important cell) and when having C type just change corresponding char.
"for each other cell calculate first important cell on it's way" — how do you exactly handle that thing?
Every 100 queries do a DFS, for every cell follow links until you hit an important cell or a cell you visited before.
Such a bloody Div.2 Contest! Congratulations to those who were able to correctly solve Div2 C :) And thanks for the nice problemset
O(n) div. 1 B solution: 8791632
In Div #2 Problem B Candy Boxes it was mentioned
"All your numbers b must satisfy inequality 1 ≤ b ≤ 10^6....."
but the system doesnt check for 10^6 condition
Example: the case
1 999999
the ans should be
YES 333333 333333 999999
but it also passess the solution
YES 999999 2999997 2999997
1 999999 isn't even a valid input! "(1 ≤ ai ≤ 500)"
1 <= ai <= 500
yup... my bad
Got a rank of 185 by solving only Div2 A! 5 Hacks saved my day .
158 place "A" and "C" ... "B" hacked :( Next time I'll take purple :D
Where can we obtain the editorial?
Editorials has not been published yet. Once they are published, it will be updated in the main page
Кто-то уже посчитал, по какому месту кат-офф футболок на сборах?
Рейтинговый? Млять, вы шутите?
Please explain why my solution get ML ? http://codeforces.com/contest/487/submission/8791889
You don't call "build" anywhere.. not sure why the ML though.
Problems were very interesting, thanks!
Despite my rating increased by 82 but I think this round has to be unrated
I left the contest after about 45 min every time I make refresh I found no response
I tried a lot of times to submit A but no response also at a moment I make refresh I submitted an old code for C and didn't manage to submit it again about 15 min.
so I think it's unfair to make it rated unless it's a problem of mine
Thanks
I didn't really face any problems during the contest, other than the contest problems of course :)
How to solve 487B - Strip?
Лично у меня и у моих знакомых, которые тоже писали раунд, пол контеста сервер был недоступен! Как так раунд рейтинговый?
В самом начале открываешь все задачи, и если кодфорс недоступен решаешь следующий...
У меня был недоступен в районе 70-90 минут от начала контеста. Если страницы и открывались, то невозможно было посмотреть чужой код для взлома. Всё остальное время работало более-менее нормально.
After contest i got AC in B (div.2) despite my program would incorrectly print a solution for such corner case:
2 n n*3(separated by newlines), but tests doesn't included it.Почему взлом №125675 был проигнорирован? На контесте я заметил, что по мне была неудачная попытка взлома от VArtem, сейчас (в окончательных результатах) её нету. В списке взломов она присутствует с вердиктом "Игнорирован".
already orange ))
Why the author's solution produces different output in these two hacks: 125341 and 125632
What is even funnier is that checker didn't accept lac of EOLNs (-_- ...) : 8783190, so that second answer of author's solution won't be accepted :pp.
Can anyone explaine me what is a monotonic queue (editorial)?
Thanks x_x
Country wise standings has been updated. Also I want to ask a question that how much beneficial is it to the community now and should I continue with it ? I ask this because I have to pay for the hosting from my pocket and it becomes a bit expensive to do it every month and it is going to end pretty soon.
I think it's really useful, thanks for the effort!
captain my captain
i wonder
why do you prefer this round to be at midnight? @shigule