Привет, Codeforces!
27 декабря 2015 года в 14:05 MSK (время московское) состоится очередной раунд Codeforces #337 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса. Обратите внимание на необычное время начала раунда!!!
В этот раз задачи для вас готовили я и Эдвард Давтян (Edvard).
Хотелось бы сказать большое спасибо Глебу Евстропову (GlebsHP) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский и Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.
Участникам будет предложено пять задач и два часа на их решение. Разбалловка будет объявлена позднее.
UPD Раунд переносится на 10 минут. Разбалловка 500-1000-1500-2500-2500
UPD2 Соревнование завершено! Всем спасибо! Разбор
Yee this contests digits are prime :-D
What a nerd ...
Recently Edvard prepared so many round, like a Problem_HULK ! Sorry to say , but description of problems prepared by fcspartakm are really hard to understand. Hope this time , it will be okay !
Странно, но судя по количеству взломов, задача "А" оказалась самой сложной.
Really appreciate the effort Edvard is doing here.
As usual, the round starts in the unusual time :)
Worst unusual time ever :(
I agree... contest begins when I am at school
So me.. like you.
But it is very suitable for us students in China. :)
Also suitable for students in India (4:50 pm) :D
I think so too。
GL & HF
Hope to be an expert after #337 div2!Come on,Parco!
My brain after reading this comment:
M-x replace-string "expert" "candidate master"; M-x replace-string "Parco" "KostikBigOne"rank 300,i think i could be an expert :D
btw,what's wrong with the rating now?
Guys, I don't want to meet New Year with negative contribution, but when I help somebody, I get no pluses at all, so I decided to post something extremely cute in hope for extra pluses!
Enjoy and
:
Коты, самая крупная слабость интернетов.
Не знаю почему, но это соревнование и следующее для меня будут самыми интересными и значимыми. Может быть это потому, что сегодня уже 26 декабря... В общем желаю всем успехов, великолепно провести последние дни 2015 года :)
афтор за футбольный клуб спартак москва болеет?я тоже
It is unusal time. Thanks everyone who participate in this contest.
negative to positive.
The scoring distribution will be announced after the contest.
Total: 4206 Contestants: 3959 Out of competition: 247
wtf!!!! the sitre went down!!! i didnt had time to register
The site was down for the last 5 min, i couldn't reg :(
you can register now
I love delay :(( :|
Been getting this a lot lately ;_;
Scoring distribution will be announced after the contest?
Been seeing a lot of this recently... ;_;
when CF so laggy, you accidentally send the same comment twice.
" UPD The start time of the Round is moved on 10 minutes.". Should be: The start time of the Round is moved on 15 minutes, right?
For most people at UTC+8, it will be the best time forever XD
They will enjoy a real "usual" time contest.
Anyway, gl & hf, thanks to fcspartakm & Edvard.
I think just like the football ,we should have some round at different time to make people over the world enjoy the happiness that cf brings to us.
Надеюсь раунд будет рейтинговым, учитывая все эти проблемы с сайтом на данный момент.
Надеюсь, что твоя надежда не сбудется
Wow, the server is so buggy today. Takes minutes to load pages... Really impacts contest performance and productivity negatively...
hacked after locking is this possible
Yes.
Locking just gives you access to others code. If other person has locked his/her solution then he/she can hack others solution even when other participant hasn't locked his/her solution. So submit only when you are sure.
I too realised this during a contest.
Задачи хорошие, но что то пошло не так...
WA on test 7 >_<
If you are about problem B, try this test on your solution: 5 1 1 1 2 1 Correct answer is 6. I also have a lot of problems with test #7, but i have already passed all system tests with completely different from first implementation.
Hm, my only problem with test 7 was using int32 instead of int64. When changed — AC.
В случае sarvagya3943 ошибка как раз таки в неправильной реализации, а не переполнении переменной.
problem is with my logic i guess !
A is mad ! O(n) solution would get ac really ? i tried to hack an O(n) solution with 2000000000 but i got UHA :(
I think not. May be he did some constant optimization like this one: 15044253. The complexity of this solution is
As far I know, CF allows 4 * 108 operations in one second roughly.
And always think twice before hacking any solution for
TLElike me!This solution was in my room, but I am not that fool. :)
I've seen a lot of times when bad complexities pass, because of marginal optimizations.
You are wrong. CF can make 10^9 operations per 0.6 seconds: 14032294
Mainly I told about
C++.However, it varies on the computation you did in every iteration. But our consideration is only the worst cases.
Or may be CF increasing their speed day by day! :)
http://codeforces.com/contest/610/submission/15052683
Check this submission I tried to hack. It gave me UHA. It actually failed on systest when codeforces gave the test 2000000000. However when we hack it it gives UHA. Some bug.
Fluctuating pupil / specialist . ;(
Fluctuating pupil :( :P
:(
Look for garbage value in B. I was getting WA in pretest 3 then i realized that when there is only one minimum then some values will be garbage.
I get WA 7 :(
WA 7 is about int overflow, use long (64-bit) data type for calculating a sum.
mathforces :)
Don't you just love it when you get hacked in a solution, but your hacker is so nice, he gives you ample time to rectify your mistakes ^_^ .
Yea that happened with my A. I was first thinking they should have written print -1 when not possible so that it will cover odd case. But i submitted my code without thinking over it. Pretest passed -> Hacked -> AC. :)
В D нужен был метод сканирующей прямой?
Isn't the k=0 in question c controversial ?? I mean u cannot have two vectors in it .. So some simply print + as their solution while the others ignore.
does pretests of C include all K s?
There are people with successful hacks on C.
Lol,no. Why would they do that
nope because the person that commented just before u had his C hacked :)
Nope ... My friend got hacked in problem c for k=0
Isn't the k=0 case in problem c a controversial one ?? Because some consider that there is no solution for it .. while others printed + for it .. U cannot have an orthogonal set over there r8 ??
Let's just accept the fact that if you got hacked in C, it was because of k=0, and then rectify it.
The condition was that any two vectors are orthogonal. Since there is only one vector, the condition remains true.
Problem C is very unoriginal: https://en.wikipedia.org/wiki/Walsh_matrix#Formula
And D is the most original problem ever :P
Sorry for that. I didn't know about that. Actually the legend is true story about me.
How to solve pC ?
is it gray code or something?
i solved it next:
start from K = 0, then lets say the vector is + Now for all numbers from 1 to K do next:
and how to output 2^k answers?
Each time you iterate the cycle I described your number of answers gets doubled. So for K = 0 you have 1 vector '+', for K = 1 you will have 2 vectors, for K = 2 you have 4 vectors and so on.
Technically, I solved it using char arrays. And then just pring every char array on its own line
What was the intuition behind this?
My solution was:
answer for k = 0: (1) (or "+")
answer for k:
all vectors from (k-1) answer doubled and all vectors from (k — 1) answer doubled, but second half is inverted
А тупая какая-то, O(n) проходило, перебор до n/4 проходил.
Компилятор С++ оптимизирует цикл. Если убрать флаг оптимизации, такого чуда уже не случится (видимо)
Hello,can anyone look into my hack #192799? I think there is a problem with the checker maybe?
How can this be correct?
Print 2^k lines consisting of 2^k characters each.
Yes,he printed 2 lines of 1 character but he should have printed 2 lines of 2 character.
really this print + * on test 1
We are working on this issue.
Issue is now resolved, everyone should be happy I suppose)
Can you please open problemset now? It says temporarily blocked
It seems that his submission 15050289 was still accepted and he still got 1200 points for that problem?
Yes. He has a correct solution that works incorrect only in this case, so we decided to keep it accepted.
I accept your decision but I think it is a bit unfair,since it goes against the spirit of competitive programming.It is wrong even if only on one case.What if there is no bug in the checker in the first place,will it still be accepted?Let alone I should get +100 points for a successful hacking.
If there was no bug in the checker in the first place, it would have given me "Wrong answer on pretest 2", then I'd read my code again, find the bug and resubmit. But since it passed pretests, I assumed it was correct and moved on to problem D.
I think that what would actually be unfair is get -1200 points on a contest because the checker failed on pretest 2.
контест будет нерейтинговым? таблицы изменятся? у tenshi_kanade всё ещё Accepted за C
@fcspartakm ; There has been solutions to problem A with an O(n) solution, which is getting passed. I tried to hack one with input as 2*(10^9) and it still passed. How is this possible?
Compiler Optimization most probably.
I don't think that should be allowed. And it's a pretty straightforward O(n). Where the loop runs n/2 times.
I read about this here: http://codeforces.com/blog/entry/21585?#comment-263052
http://codeforces.com/contest/610/submission/15052683
This is the link to the submission. It got a WA in systests, and it is giving WA on my system as well for the input for which I hacked. In sys-tests this guy has TLE's on the same code. How come the hack passed?
Can you please check this fcspartakm, Edvard, [user:GlebsHP)]?
Em I really do wanna know what is point of retarded hacks like in this contest, a good hack should be one that needs your effort to find test case that is not working, not having no pretests and then first guy, that gets the idea of: Oh, maybe they have no pretests, get like 1500 points?
So how do you check intersecting points in D without checking all lines which are in the range?
Like you have a horizontal line from -1000 to 1000 and there are 100000 vertical lines in this range — how do you avoid checking every one of them?
And if you can't, then the solution complexity is n^2 right? Because if there are 10 horizontal lines who all start from -1000 to 1000 on different Y positions then you still have to check 100000 vertical lines for each of these horizontal lines, right?
Tried to optimize my solution for 30 minutes without any luck :(
In problem B, 3 WA on pretest 7 with int, even in JAVA! :( Finally passed it
Hahaha, the same to me! But TLE instead, and something like 4 times :p. Finally AC
I got 2 WA with long long :(
During contest my friendlist was behaving weirdly. Did this happen with others?
when will the system tests start
Уже который раз замечаю, что хорошие идеи приходят слишком поздно. В 4 задаче надо же было написать сканлайн и ответ считать деревом отрезков?
По-крайней мере, вроде бы так оно решается. Придумал за 30 минут до конца, понимал, что с моим опытом закодить не успею, но хотя бы попытался :(
Вот моё решение: сканлайном создаем все сегменты, потом для каждого горизонтального отрезка ищем первый входящий в его рендж вертикальный отрезок, и начиная с него проверяем по каждый отрезок пока не выйдем за пределы горизонтального отрезка.
Time limit http://codeforces.com/contest/610/submission/15054415
Либо я что то не так накодил, либо не проходит с такой сложностью. Сегментовое дерево как бы ускорило этот алгоритм?
Худший случай, который может быть, это когда имеем по 50000 вертикальных и горизонтальных отрезков, которые полностью одинаковы. При таком сценарии ваша оптимизация не даст ничего — выродится в полный перебор.
UPD: не обязательно полностью одинаковы, достаточно что бы все вертикальные входили во все горизонтальные или наоборот.
Я сам на этом же месте застрял :)
Ну, я дописать не успел. Идея была такая. Упорядочим все точки по x координате. При этом надо учесть, чтобы все "открывающие" отрезок точки были перед "закрывающими".
Рассмотрим множество всех координат y, которые встречаются. Отсортируем их и перенумеруем. Теперь дерево отрезков будет помещаться в память. Также надо знать, сколько раз координата y накрыта различными отрезками.
Теперь понятно как обрабатывать горизонтальные запросы: добавление — увеличить покрытие на 1) удаление — (уменьшить покрытие на 1).
Если приходит вертикальный, то просто посчитать сколько координат y накрывается (покрытие не равно нулю).
UPD: Я совсем недавно решал похожую задачу, но тогда я писал её где-то дня 2-3 не спеша, при этом ещё и со стресс-тестом.
Теперь понятно как обрабатывать горизонтальные запросы: добавление — увеличить покрытие на 1) удаление — (уменьшить покрытие на 1).Как отделить что поступивший горизонтальный запрос включает в себя вертикальную точку из множества координат y? Так как горизонтальная линия может не доходить до этой вертикальной точки или начинаться уже после нее
Не понимаю в чём проблема. Ты же проходишься сканлайном по x. Соответственно, у тебя могут быть события 3 типов: левый конец горизонтального отрезка, правый конец горизонтального отрезка и вертикальный отрезок. Тебе важно лишь поддерживать в некоторой структуре данных актуальные точки y, которые задействованы в данный момент и эффективно находить их количество на заданном диапазоне. Примерно это же написано в разборе, правда там посоветовали дерево Фенвика.
Way too much China :P
I worked so hard to get over my addiction to chineese food, and now you remind me of it ;_;
in problem b the wa was due to the constraints 10^9 not anything else
можно было и продлить раунд,у меня минут 15 сервер не отвечал на запросы.
To the person who answers questions, if I am taking time to ask a question very specific to the problem, I have carefully read the statement and understood as much as I can. After that, if I am still not able to understand, the fault is not always mine.
After solving C, I had to wait for 10 minutes on clarification of case k = 0. This penalised my time for D which I could not code in time.
I am still not able to understand problem A at all. The contest had good problems. Please be a little more helpful and kind with the statements.
Мне кажеться, что очень похожая на D была на e-olimp. Никто не вспомнил?
I was able to register only coz of the delay, and luckily, I'm getting a notable jump in ratings this time!
Wake me up, when the ratings change
I should have solved B faster :( one hour for an easy problem is not good...
So after 3-4 WA on problem B: Wrong answer on test 53 :\ :(
You also have to consider the distance between first minimum value and last minimum value.
Yeah added that now and got ac now :)
Nice fast editorial! Thanks fcspartakm!
смотрим на 2ой тест и радуемся
Good Contest and give me good luck.
am I the only one who think that D is repeated and very dull problem?
maybe the right place for this problem is educational rounds not rated rounds
Maybe, but it is Div2 and only 123 ppl solved it. So seems very fine :)
It was standard task, but I decided to do the third task, new and interesting for me. After nearly two hours of thinking I realized that I am very stupid guy :)
After thinking of C for nearly an hour, I found D an easy task but finally failed to code it out before the contest ended...
The same with you...
And C is just weird someway... I don't think the solution can be called 'algorithm' anyway.
yes, it's "guess the pattern" problem
Can you share your ideas on how you found the pattern?
I kept thinking about it but nothing found until I read the Hadamard_matrix
I thought I should use the answer for K-1 to compute the answer for K, since the answer for K-1 is 2^(K-1) * 2^(K-1) square and for K it's 2^K * 2^K square then I knew I have to complete the other 3 parts of the square using the first one
Thanks.
Haha, yes. Guessed the pattern, then copied and pasted k times :)
Неактуально
ho-jo-bo-ro-lo, the perfect complexity analyzer: 15049767 :)
how about this one 2563497 not even a single millisecond margin
А когда заработает API ?)
Its been an hour, still no rating change. They probably caught one cheater at least, because my standings improved by 1.
My standings improved by like 15 positions since system testing finished :)
Nothing to see here.
Well, my position improved by 2 so that must be the case :)
If yours improved by 2, then mine should too, you stood better than me.
where is the rating changes ? :(
Its coming, just like winters . FYI winters hasn't reached my country yet.
А почему некоторым фиолетовым рейтинг поменяли? Например, Temirulan и NurlashKO
why unoffical Participants still rated ?
I think any participant who hack in contest will be rated
Div 1 users got rating changes. For example, Alex_2oo8 went from 2590 down to 2315. Please, you have to correct that...
а разве для div1 раунд не должен быть нерейтинговым?
kingofnumbers got -176 rating change although he's unofficial participant.
I got -169 and I'am unofficial participant too
all participan hacked still rated
mb cheats?
Will this round be unrated?
Seems ratings are difficult to calculate →_→.
Will this round be unrated ？
Why do I have less rating increase than I had an hour ago?
Because the ratings calculated earlier included Div 1 unofficial participants who hacked during the contest, and that's not supposed to happen.
Ok, thanks! :) And congrats for getting back to div1 :)
Thanks!
I solved problem A without any wrong ans. But my rating decrease 8. Why?
Rating is calculated considering time of solving and first successful attempt. And also with some special expected and real positions. To more information click in this link.
минут 30-35 назад я увидел,что к моему рейтингу прибавили +72 и стало 1284, но сейчас все как прежде 1212 интересно что случилось? или у меня галлюцинации?
теперь опять 1284?!
WTF is happening to the rating ?
It has been saying "System testing 100%" for quite a while now.
It seems that the last educational round was also rejudged ???
And why did rating changes disappeared ?
This round has given me more anxiety than I know what to do with.
OK, back to final standings :-)
They may take our lives, but they will never take our rating changes :D
Seems indicative of a zombie apocalypse...
It reminds me what happened at the Miss Universe ceremony.
Like "You are Miss Universe", and then
Here, it's the same but for a "+162" in rating...
Is there any chance the contest is unrated? coz its should not be! What is it with these judges just give the rating and get over it!
Mike just found a submission that was judged as "cheating", but in the end it was not. Give it some time to recalculate again.
Where have the rating changes gone? They were calculated, then reset because they were wrong, then recalculated, now I come back and they are gone again. What the... ?!?!?!
I know it is a strategy to kill us with anxiety :-|
English is not my native language
Your English is pretty good. I think that adding that note at the end (or "sorry for poor English") is what makes it look bad.
Has anybody any information about our ratings? I'm very excited)
You shouldnt worry that much , sir. Rating is not the most important thing in your life.
Actually, it is))0)
Rating change seems to be John Cena. I can't see it.
^ We have a winner over here
I just can't sleep. I want to be candidate master today ^_^. Give me my rating :D
Its really not the greatest thing that can happen for you :) Back in the days before colors revolution it was like "I'm in div1 now, yay! Why is there only div2 contests? Finally, a div1 contest! Damn, I'm back in the div2 again." :)
After being rejected from MITACS, EPFL, Google, Jane Street, Microsoft and many more, this is surely the best thing happening in long time.
These are not the days before color revolution.
Let me celebrate my happiness. I am in love with it :D
Huh, then congrats!
First they reject you, then you build something so awesome, they buy it for billions of dollars(remember whatsap). Chin up, buttercup! :D And congrats. I am inspired by you :)
I love this! :D I check my status it says pupil then i come back after two hours it says i am specialist! Codeforces changing colours of people like colour change on a Christmas tree! :D
You are a pupil again.
Yea it is switching itself after sometime. When contest goes rated i am pupil when it is unrated i am specialist! :D
Did you re-rate the contest? My rating change seems to be different than it was several hours ago...
Also some features on the website don't seem to be present (search). Is it just on my phone or is there some problem on the server?