Привет, Codeforces!
25 мая 2016 года в 18:05 MSK (время московское) состоится очередной раунд Codeforces #354 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса. Как обычно, обратите внимание на необычное время начала раунда.
В этот раз задачи для вас готовили я и Григорий AGrigorii Ахременко (это его дебют в качестве автора задач).
Хотелось бы сказать большое спасибо Глебу GlebsHP Евстропову за помощь в подготовке задач, Михаилу MikeMirzayanov Мирзаянову за замечательные системы Codeforces и Polygon, а также Илье IlyaLos Лось (да, его фамилия не склоняется!) и Артуру ikar Свечникову за прорешивание задач и ценные советы.
Участникам будет предложено пять задач и два часа на их решение. Разбалловка будет объявлена позднее.
UPD Разбалловка 500-1000-1500-2250-2250
UPD2 Разбор
UPD3 Поздравляем победителей
UPD4 До скорых новых встреч!=)
Will it be rated? It is not stated so I think it's a valid question.
Sure
Hello everyone! I am red_black boy!!
I make a mistake.I am Black_red boy!!
I will beat everyone today.good contest hahahahahahah....
Are you five years old??
If you are red_black boy, what can you do in O(log N) ? :)
why in each time when GlebsHP helps preparing the contest , problem C be easy :p
He is now codeforces coordinator, so he helps in every codeforces round, that has nothing to do with Problem C :D
Are you sure? Look at this round and at this problem.
Какое необычное предложение : "Как обычно, обратите внимание на необычное время начала раунда"
Div. 2 only contest, which means loads of fake new accounts of Div. 1 people... :(
This is bad. Those who are in Division 2 will not be able to rise, as will constantly play fake members of the first division.
the people from the first division. Please participate only out of the competition!
That's not true anymore. After the rating revolution the number of fake accounts decreased significantly. There was less than 30 new accounts in top-1000 in the last two div2 only rounds, and most of these are not fake for sure.
Although there are just 30 new accounts, but many contestants of div1 have many accounts which had rated. So there aren't only 30 people of div1 use div2 account to participate this round.
Why?They can also participate with asterisk.
Maybe because they love the feelings when their ratings make a big jump (who doesn't, right?)
Like me :)
Учим русский язык вместе.
http://new.gramota.ru/spravka/letters/71-rubric-482
13.1.4. Все прочие мужские фамилии, имеющие основы на согласные и нулевое окончание в именительном падеже (на письме они кончаются согласной буквой, ь или й), кроме фамилий на -ых, -их, склоняются как существительные второго склонения мужского рода, т. е. имеют в творительном падеже окончание -ом, (-ем): Герценом, Левитаном, Гоголем, Врубелем, Хемингуэем, Гайдаем. Такие фамилии воспринимаются как «нерусские».
СЛЫШ, САМ ТЫ НЕРУССКИЙ А ГОГОЛЯ НЕ ТРОГАЙ ОН НАШ!!!!!!!!
С возвращением!
Здесь вчера был коммент Huyum_nik-а. Почему его удалили? Вроде бы он не нарушал никаких правил.
unlucky , i can't participate in this contest because the electricity power cut off from my home at start time of this contest .
Sad story.
Maybe that's good for your rating...
and maybe not
Дебют в подготовке задач — это всегда здорово. Пошумим!) Надеюсь на стандартную разбалловку.
И да свершится раунд!
It maybe my first contest in codeforces, good luck to everyone.
Good luck, I think you are excellent and beautiful.
Friend-zoned people everywhere ^
Thank you.
I have a feeling you will rank the top.
Let's see if I am right after contest.
Just a feeling , take a look at his submissions and you'll be sure :D.
You must take a mistake, and I am a newbie.
You must be joking.
I found you using advanced techniques in ur submissions.
Mo's algorithm, I don't think a newbie know this algorithm.
Do you mean the mo's algorithm is advanced technique? I really just start to study Algorithm for one month....
Okay...
Good luck to you, xiao ai.
Good luck. My first contest as well. :)
Good luck to you.
This my 4th time to take a round. But it's my first time to find the round announcement before the contest... I wonder Why their is not a link to this announcement in the contest page...
Is Delinur still a translator in Codeforces? I feel I haven't see her name in a round announcement for a long time.
Unable to parse markup [type=CF_TEX]
$Как говорится: «Пошумим, б*#%ь!»
А если серьезно: надеюсь, что раунд получится крайне интересным.
Oh god, I have two university exams tomorrow :(
But wait a second, stupid university exams won't help me reach the AMC-ICPC :V :V :V
I'm in :D :D :D
Now back to the exams :)
Exams are stupid, they can still wait :3
This contest may become my debut. I looked at your profile and I saw you make contests with more than 5 tasks. Will this hold for today because I want to solve as many problems as possible?
Can't wait to be a candidate master.
So am I. Best wished to us. Good luck & have fun.
Congratulations! You did it
Thank you
You guys are pretty close becoming a candidate master. I still got a a lot of work to do! Best of luck!
Good luck to everyone:)
Hope you all have a great leap in your ratings(which is impossible)
Challenge Failed, Congratulations!
My memories of usual Codeforces' rounds are fading... Usual time? haha! BTW I like contests being held at 8PM MSK. It's a good time for me. I wish it was the usual time.
I wish it wasn't, 8PM MSK is 1:00AM in my local. It's very bad.
At least you can sleep less and participate, in my country it's 12:05pm. I normally work at that time. I wish it were at 1:00am, I would participate a lot more!
I like this time too. I have high school students work on it and it is 11 am EST which is when the class is. It was perfect!
Study for Exams or Codeforces Round? why am i even thinking about this :D I am in
Good Decision! A few weeks ago I had the same problem. I decided to go for CF. Got 80+ ratings :)
Though I have an exam at University, I am not thinking about this. Absence in a CF round give me much pain than getting less mark in exam.
Damn I have 4 exams tomorrow... Shit I forgot I finished school
wow! problem D, E got the same score? D must be hard.
or E might be easy
or both
or none of them :D
very easy problems
Seems fine — only 249 people solved D and 105 solved E.
Nice contest.
solve E ! it's the best problem also easy as E
E is easy if you know a thing or two about polynomials (namely, that the remainder when dividing f(x) by x - k is f(k)).
However, I didn't find any non-annoying ways to check whether f(x) is divisible by x - k if all the coefficients are already known...
You can calculate it modulo a couple of random numbers or primes. That will nearly always work.
I don't know if there is a nice way to do it without randomisation though.
To check if f(k) = 0, note that f(k) = a0 (mod k). So a0 must be a multiple of k or f(k) cannot equal 0. So you can add a0/k to a1. Call this a1'. But then the new a1' must be a multiple of k or f(k) cannot equal 0. So now you can add a1'/k to a2.. and so on.
Are you using floating point for this? Does that not give you issues with precision? Or alternatively, give you very large fractions?
If a_i is not a multiple of k, the algorithm terminates. You only divide a_i by k if a_i mod k is 0.
I don't know if it worked... but I just used python and did it in O(n) :D (python handles big integers)
I'd love to see Python handling 10000100000 in one second...
If he used Python2, the multiplication would have just overflowed, and he may have been lucky that it worked.
Hodor :v :p
how to solve B?
Create 2D array for your glasses, put T * CONST (e.g. 2048) water in first one.
Iterate from top to bottom, layer by layer. For each glass substract all water that left (higher than your const), split it by 2 and add to two glasses on the bottom layer.
Count how many glasses have >= const water in it. O(N).
We use CONST to avoid of float computations. It should be power of 2, enough to fill all levels.
Ээх, я не додумался, что через T * CONST можно все к int-ам свести.
I put 1024 water in the first one and used the similar approach that you told. Is there any problem with 1024? Since the first and last glasses of the last(10th) row will receive 1 unit.
It should be enough. But you should put T * 1024, not just 1024.
I use double,is my solution wrong?
Well it depends how you implemented it. With double and division operation you could get wrong comparisons. With integers it will be always correct :)
For what I know, such dividing by 2 cannot cause precision problems with double (it behaves the same way as bit shift), so it was safe in this task. But its a bad habit for sure, I agree.
Ya I meant for each second I passed 1024 units on the first glass and then repeated the process for T time
Hack testcase of E?
I think K=0.
i handled it still it got hacked
There are still different cases when K = 0. Think about the case where all Ai = 0 but one is '?'
is there any case for K = 0 other than
* a[0] is already 0 "Yes"
* a[0] is nonzero but not '?' "No"
* a[0] is '?' and its human's turn "Yes"
* a[0] is '?' and its computer's turn "No"
?
If all Ai are 0 then it should be "No"
the question says P(x) is divisible by Q(x) if there exists a representation P(x) = B(x)Q(x) . if all A[i]'s are 0 , then if we make B(x) also a polynomial with all coefficient's as 0 , then wouldn't P(x) be a multiple of Q(x) as well?
How did you handle overflow? with modulo of some prime?
i just took 4 prime modulos
Share your approach for C. Your code is pretty simple ! @rajat1603
Take the Case when we want every element of the subarray to be equal to a . (For other case just change all a to b and b to a and run the same algorithm again).
Now consider a to be 0 and b to be 1.
We want to select the longest subarray with sum ≤ K .
So we take a right pointer and move it from 1 to N .
We also maintain a left pointer denoting the left endpoint of the longest subarray ending here. When sum exceeds K , we move the left pointer 1 step ahead.
So now we have longest subarray with sum ≤ K ending at every index.
Thanks !
Any fixed prime modulus can be hacked.
Huh! 10 seconds left, i submitted. The result on final page: Pending system testing DAMMMMMMMMMMMN. Now i don't know whether i should be happy or sad in case it passes after i submit later on :\
I think it will be counted if your submission is in queue before the contests ends
Now it isn't in my submissions too. Though i got redirected to some link with some token value at the end but probably there was a bit of lag b/w my submission and before server received it. :(
Is there a nice way to solve E without randomization?
Gorner's way)
Gorners?
Other than my reply to your other comment, one more option is to observe that if the absolute value of the partial sum becomes greater than some small value (roughly 10^4 / k-1 or 10^4*n if k is 1) then it's impossible for it to come back to zero. So you can just terminate if that happens, and otherwise proceed as normal, so you'll never get overflow.
It was a good contest with easy problem, but I could solve only A :D , i couldnt find the formula for B(i think it's something bounded with pascal's triangle ). How you solved B and C ?
That is what I thought, but I found to many exceptions in it. So I just simulated it.
It is easier to just use dynamic programming approach to solve it in O(N): http://codeforces.me/blog/entry/45031?#comment-295709
I have three big critiques. Problem C was given before and I could hack it easily. But I didn't. Problem D is awful and easy to come up with a solution. Nobody likes such problems. Problem E is easy.
Ok, so you know that problem C was given before, even though this 5 problems are the first that you solve in Codeforces? Suspicious...
Illuminati?
What I want to say is that the problem is a common use of 2-index technique, I don't mean it was on Codeforces. I don't solve Codeforces, I only solve hard problems and this contest was just to test my level.
I was trying to hack A and I wrote the exact same code of other contestant and tested it on custom invocation. It gave a wrong answer but I got unsuccessful hacking attempt. Anyone knows why?
Sorry, my bad! Everything is ok!
I solved D and found contest just finished for a few seconds...
I hope my solution has some bug so that I won't be so sad...
BTW, D is easy to come up with a solution but not easy to code it, I don't like such problems.
Well, if you are experienced enough, there's nothing to struggle with:
30 lines of switch-case to rotate a symbol clockwise 20 lines of creating edges to adjacent cells given a symbol 40 lines of bfs + misc to read/write
In total, not too much if you know what you are doing.
What I usually do — I just start coding, and quite often it appears that it is not so hard as I expected it to be :)
you are right, I'm not so experienced in program competition. When I write a solution having code above 100 lines, it often contain some bug(maybe stupid typing error like typing i for j ...), I need to do more coding. This is a nice platform :)
You should check some solutions out. E.g. mine uses only 1 line to do rotation and 5 lines to generate neighbors.
Mine failed, so yeah all cool now :P. 2 silly mistakes. I wrote somewhere 'V' and somewhere as 'v' and other i didn't checked that to go from a to b, a path from b->a and a->b must both exist.
Who the hell thought it would be a good idea to put problem D -_- like... What's the purpose of it??
with all due respect to authors
It's a good exercise in implementation.
Well, I kinda don't like it too. Easy algo (just BFS), but requires careful implementation of all cases.
That's the purpose
pretty ugly ruined my round because of a silly mistake :/
Anyone else got WA'd / TLE'd in D test case 10?
I got WA too.
Well I did get it, but fixed later. I've used too much memory :)
Did you use NxM matrix to store distance for each state in shortest path algorithm or NxMx4 matrix? I used both, with NxMx4 i got TLE and NxM got WA :(
In last submission I used NxMx4 matrix of int64 to store distances. Plus one matrix NxMx4 of int8 to store direction flags. Plus three queue's of int32 to queue positions. Around 50 Mb total.
I used simple BFS.
Just got it AC after systest, 1500ms and 50Mb.
I guess the problem is that i used Dijkstra's then. Never thought about state graph being unweighted
I don't think the size of the array is the problem. I used
4 * N * Mand it was fine.sad...fst 2 problem..
Первые две на реализацию, третья на малюсенькую идею и реализацию, просто огненный контест :(
Why GlebsHP accepts rounds with such classic problems like those in today's C, D?. I thought the round will be cool because fcspartakm is the problem setter but found only one good problem. :D
Please, wake me up if the problems of Div. 1 contests will become easy and classic for you.
even for a div2 contestant, i spent 3/4 the contest time coding / debugging instead of thinking , i didn't enjoy this contest at all, the only good problem is the E and didn't have time to read it tho
Just read D and E and the same time. It often happens that one is harder on implementation and the other is harder on the idea.
I'm not saying they were easy or they should be hard. Just saying it'd be better if they were kinda unique.
Just when I saw C has more submissions than B, I knew something was fishy. And it turned out it was similar to Hard Process(ER 11) and Repair road. Problem B was also based on how good you are at google search(But I was unable to solve it :P).
I solved hard process today only :D
how to solve pC?
i choose odd ones to connect left even one and right even one.
scan odd ones from left to right
then choose even ones like odd ones
but stuck at pretest 12
If we divide the problem in two parts and return the max of both:
After that two pointer approach can be used to solve each subproblem.
Fill consecutive gaps of A OR Fill consecutive gaps of B. Find maximum among both.
In problem E, if you use fixed modulus then you can get hacked. For example, if you use 109 + 7 and 109 + 9 as modulus, write (109 + 7) × (109 + 9) = 1000000016000000063 in base-10000 number system so we get "4 10000\n63\n0\n160\n0\n100" as a hack case.
Now I came to know that my solution will fail in system test!
Can someone debug this code for D?
My logic should be fine, but I get WA on #10(hate implementations) Logic is to BFS the graph with 4 states for each node(representing number of rotations).
I know, the implementation is pretty messed up, but I did comment a little bit if that helps
В задаче A больше 117 тестов. 117, Карл!
Я как-то видел ~210. И бывает и больше.
Объясните кто-нибудь, почему это получило WA 94(B): http://pastebin.com/0MrgPqew
Если стакан не полный, то из него ничо не переливается, а у тебя переливается!!
Какой смысл в последней задаче? Мб я чего не понимаю, но в случае если кол-во "?" > 0, то при нечётных степенях побеждает человек, а при чётных комп, а если кол-во вопросов == 0, то надо тупо посмотреть на сумму?
Те, кто тупо посмотрели на сумму, получили WA/TL/ML.
всё равно на задачу под номером Е не тянет
Ее решило правильно 16 человек из Div2, помойму вполне тянет.
D и E с очень нудной реализацией
18085379 Why do I get WA? Anyone care to help me???
Your recursive Fill function does not exit early enough, it continues "pouring" water past the n-th level. Change
if (i>9 || j>i) return;toif (i>=n || j>i) return;. Then it passes all tests: 18093994Can you see the standing without the starred people from div 1?
Just untick show unofficial located on top — right corner of standings page. :)
Как я понимаю, AGrigorii автор задачи 676D - Тесей и лабиринт Она крутая, хотя и перегруженная (ИМХО).
Но, я рандомным тестом n,m=1k из {+,-,|} сломал одного участника в комнате по TL, мое решение на нем также падает по времени (10сек). При этом системные тесты я прошел.
Тщательнее готовьте, молодой человек.)
n,m=10k? Там же ограничение 1k, разве нет?
Вообще согласен, задача крутая :)
Если это так, то появляются вопросы к окси по-поводу валидатора, поэтому
Тщательнее готовьте, молодой человек.)остается в силе.Te4NIK ошибся. У него во взломе n и m равны 1000.
Тогда респект рандому и удаче Te4NIK за создание крутых тестов :)
Ой. Люблю большие числа.) Конечно 1к.
Обида, D не сдал только потому что мне почудилось, что "v", обозначающая движение вниз, написана заглавная :(
У меня такое же было написано, но я заранее сделал
std::map<char, int>и использовалat(char)для получения маски направлений по символу, поэтому на третьем претесте оно выпало с RE.Auto comment: topic has been updated by fcspartakm (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем fcspartakm (предыдущая версия, новая версия, сравнить).
About D: You know what "X" and "Y" usually mean on a 2D grid? You have some idea, right? I can not imagine why the problem statement for D was written with the exact OPPOSITE meaning for those letters. Got WA for this, upsolved after swapping X and Y when reading input. Is Codeforces supposed to be a reading competition?
I agree, a painful mistake. For me it has always been misleading — we store 2D maps and grids as arrays of rows, so if you want to access column X and row Y, you should call Array[Y][X] <-- counterintuitive, isn't it?
What works for me: just change your perception and think of X as of the first coordinate and of Y as of the second one — then array item access becomes logical — and meets the problem author's expectations.
In my memory in the majority of tasks which has x,y in GRID in statement it is alwasy that X — row, Y — column.
My memory is the opposite.
When this happens
when I see such large pictures, I shit bricks...
You guess that you can change your 'V' into 'v'.I have made a same mistake.
Holy fuck you're right. I have never been so stupid in my life. :/
Thanks a lot guys for your efforts and splendid problems :) AGrigorii, an awesome start! — looking forward to see your next rounds in future.
Problem C is a bit more sophisticated version of 645C - Enduring Exodus. Same idea, but instead of finding the minimum, you ought to find two maxima and compare them. There is also a possibility of k being 0 in today's one (many solutions got hacked/WA'd because of that).
It's exactly the same as C from EDU11 that happened less than two months ago.
Why there are no precision errors for problem B with solutions based on double data type?
For example in my room, 18074368 solution.
Sorry for my poor English.
All the numbers are dyadic rationals, which can be represented exactly by doubles.
I suspected that, thanks for confirming.
Wow, next contest is also Div.2 Only. And it's only after a whole week.
I find no reason for a Div 2 only round. It simply encourages more fake accounts.
Here's a reason: It takes more time to prepare a Div 1 round.
When the ratings are calculated?
Your question is NP-hard
I participated to this contest , but when i go to my profile, my rating is still 0 and the contest it's not showing in the contests tab on my profile. Please help !
Wait for some time. The ratings are not yet updated.
Начинает казаться, что некоторые авторы клепают миллионы раундов ради гонораров. Придумали одну неплохую задачу (и то она выделяется лишь на фоне остальных задач контеста), а остальное добьём задачей на два указателя, которую месяц назад давали на Educational round, и бфсом по гриду.
Авторам контестов платят деньги?!
Ждем контест от Huyum_nik)
Ну если Вам интересно, то все задачи кроме А были предложены Григорием, в остальном я только помогал ему, так как это его первый раунд. Последний раунд мой раунд, где я полностью придумывал хотя бы половину задач, был с Эдвардом в декабре) Удачи.
Окей, т.е. фразу "клепают миллионы раундов" надо игнорировать, а интересность задач списать на неопытность.
По поводу интересности это Ваше субъективное мнение. Я считаю здесь Ваш тонкий троллинг не уместен, но это всего лишь моё субъективное мнение)
Раунды итак очень редки, спасибо что хоть такие есть :) автора с дебютом :)
Скажу по секрету — авторы, которые готовят задачи ради гонораров, захламляют ими другие сайты :) Потому что там гонорары намного выше, а вероятность прочесть потом вот такие комменты — намного ниже :)
Эм, а что еще можно давать в див2? Бфс по гриду было достаточно трудно писать из-за особенностей переходов. Education — а разве автор перед подготовкой задач должен учитывать все возможные соревнования за последние полгода?
На кфе и так в комментах кричат, что рейтинговые раунды достаточно редкие.
Если раундов мало, то это еще не значит, что можно давать шлак. Я сейчас не конкретно про этот раунд, а про подавляющее большинство div2 only (и иногда даже div1) в принципе
Умник, запили свой, покажи как нужно.
Тут нельзя 5 задач на FFT давать.В том и смысл, что слова "А давай раунд запилим!" должны появляться тогда, когда уже есть идеи клевых хотя бы на твой взгляд задач. Больше, чем одной. Ну либо после этой светлой мысли нужно придумывать задачи, ждать хороших идей.
Как думаешь, сколько задач нужно придумать на div1+div2 раунд? 7? Я бы сказал, 15-20. Потому что половина придуманного — это какая-то хрень. А потом внезапно оказывается, что на B есть 3 варианта, на D есть 2 варианта, а на C как-то ничего. Потом играешь SNWS, и видишь там свою D (true story).
И я не понимаю, как при этом можно давать 10 раундов за год. Конечно, готовить задачи быстро можно. Но претензии и не к качеству подготовки :)
I nearly got my first ever "5 out of 5" on codeforces, and then I fail task B on test 83 ;-(
Is it possible to make contests on weekends?
Решается ли задача B за O(1)? Была идея использовать логаритм, где (int) log2(t + 1) — уровень заполненых боковых бокалов, + x, где x — заполненные с центра бокалы, но как бы его умно вычислить?