Всем привет!
Первый раунд start[c]up начнется совсем скоро. Участвовать могут все желающие, никакой дополнительной регистрации, кроме регистрации на сам раунд, не требуется. Регистрация закрывается за пять минут до начала раунда.
Раунд пройдет по правилам codeforces и будет рейтинговым. Распределение баллов будет следующее: 500-1000-2000-2000-2500.
Задачи приготовлены разработчиками MemSQL pieguy, nika, exod40, SkidanovAlex и dolphinigle.
Лучшие 500 участников пройдут во второй раунд, а 25 лучших участников из Кремниевой Долины будут приглашены участвовать во втором раунде онсайт, где будут разыгрываться специальные призы.
Удачи на раунде и приятного кодинга!
UPDATE: Обратите внимание, что распределение баллов изменилось
UPDATE: Опубликован разбор задач!
Регистрация закрваетя за 5 минут до конца? оО
Похоже, закралась опечатка. До начала, разумеется.
А какой сложности примерно будут задачи? (Div. 2)
Где-то писали что Див1 Пруф
Glad to hear of such contest :).
How will you determine the top 25 Silicon Valley residents? And what's the definition of Silicon Valley residents?
Will summer interns be eligible? Anyone that is visiting SV during that period? Or anyone who can make it to the round at MemSQL HQ on their own?
"Silicon Valley resident" just means "willing to provide own transportation on-site, or close enough that we can pick you up in a car".
Wish this will be my first contest in codeforces.I just registered and hope for a better start. :)
Nice! :) Well you can solve a couple of problems here to get used with this platform :)
"Wish" — "better"
R.I.P English
Can you please explain what do you mean by that? :)
Woww... 17:00 is the final round of the international volleyball league 2013, Iran VS Germany... Who will hold the contest at this time???
Yeah, there are at the same time but I will hold the contest...
Will it be rated for DIV 2 ?
Yes it will be rated
1 a.m. o'clock in China... It will be so late and tired at that time though I wish to participate in...
So late in China... Obviously I can't participant:( because tomorrow is the first day of National Olympiad in Informatics
Wish everyone good luck in this round as well as NOI...
Best wishes to all who will participant in NOI2013!
Is it a new round for ioi2014?
Yeah...50 gold medals will have the opportunity to IOI2014
Can you explain Chinese NOI format? It's strange for me that ioi2013 ended and NOI for io2014 will start next week)
NOI 300->50 Winter Camp 50->12 Chinese Team Selection Contest 12->4 IOI 4 Gold Medals So long a term is Because the large population:(
Is the contest the same rules as div.2 ?
Хм... А почему все ссылки на страницы авторов контеста ведут на профиля TopCoder, а не на Codeforces? Oo
судьба такая!
А рейтинг для Див2 будет начисляться отдельно ?
Вот почему заминусовали его ? Объяснили бы хотя бы причину...
I hope it'll be a nice contest.
Изменение разбалловки "воодушевило" див. 2
500! among all reds & purples
Почему появился протокол "неизвестный вердикт" при попытке взлома? Ссылка на попытку.
Да, когда меня ломали, так же было. Из-за этого и цейнтнота на последних минутах не успел найти ошибку :( Так нечестно!
UPD: Как следствие, уведомление о взломе пришло по данным CF в 23:00:00.
Was someone else also confused by statement of problem A? I thought we needed to test if a subset of given rectangles forms a square.
Yes, me too. Strange that this wasnt covered in pretests
Really? My first solution just checked if any of the given rectangles was a square, and it failed the pretests...
That will fail pretests when no single rectangle is a square but the union of all of them is.
Mine checked if any subset of rectangles forms a square, and it passed pretests.
I've got some bad news for you....
i have succ. hack with this test case
2
0 0 3 3
3 0 4 1
there is 2 square and answer is "NO" this explains all of this questions:)
That was my interpretation as well. I found the problem statement extremely confusing.
We were trying to be more mathematically correct than "check if the union of all the rectangles form a square", but looks like it backfired... :/
Actually, I like this one. Simple and easy to understand.
This is a little confusing -- example: in this interpretation it's not clear if a square with a hole is considered a square.
Then why not: "check if the union of all the rectangles form a square (without hole)" ? This is much easier to understand. Or somehow have both sentence in the problem statement.
And then there's the recent trend of "shorter statement = good" in CF
...but you're right, we should've done that here. Apologies and lesson learnt.
(First, thank you guys for organizing the contest.)
If you added something like "all rectangles must be used", then there would be less confusion...
"at least one rectangle" ???!!!
I interpreted the same, and got hacked as well. Rest of the contest I tried many interpretations except the correct one.
same here, considered all possible permutations :\
Same here +10086
" determine if the set of points inside or on the border of at least one rectangle is precisely equal to the set of points inside or on the border of some square. "
Then What do they mean by " At least one rectangle " ? I thought we have to test subset of rectangles. I Understood this After "One Unsuccessful Hacking Attempt ". The problem statement should have been more clear .
The key phrase is:
"The set of points inside or on the border of at least one rectangle"
There is a single set of points which defined by the rectangles you are given. The reason for "at least one" is that a point could be on the border of multiple rectangles.
I understand by "The set of points. . ." you meant any point. But during the contest, I overlooked it and was scratching my head to understand, why answer for sample case #2 is "NO" while it has the same set of integer points of sample case #1.
I couldn't manage to submit A correct but I'm not complaining as I believe, dissecting a problem statement is part of the challenge to solve it correct. But I can't resist myself from saying, "Statement for problem A could be a little bit more clear. Perhaps with a note or analysis of case #2"
If n<=100 there wasn't be such understands.
Thank You. I don't know why didn't I understand that in contest. May be I have to learn English too along with Programming.
So, that statement includes all rectangles because of "The", correct?
I guess some people have better understanding of English than others.
I cannot blame problem statements for misreading them (happens to me a lot) but this one, IMO, was a bit too subtle for a non-English speaking person — especially because of "at least" part (or should it be "... the 'at least' part"? You understood me either way, right?).
Still, I don't know how I understood the second part to mean "all points within some square" and not "some points within some square". I am inconsistent, that's it. Or the second example clarified it.
I interpreted the same. Something needs to be done about it.
I too got confused with ambiguous statement of A. Developed both cases, and they both passed pretests. So I chose to leave the more difficult case (any subset forming a square). Wrong choice...
I made the same mistake,I realised that it wrong when I tried to hack somebody.
So did I :) Thanks for the guy who challenged my solution
I think this was a big mistake in the problem statement its also very clear it says : " determine if the set of points inside or on the border of at least one rectangle is precisely equal to the set of points inside or on the border of some square."
Все-же мне кажется, что условие А неоднозначное.
хотя бы одного прямоугольникаможет означать, что нужно взять хотя бы один прямоугольник и посмотреть получается ли квадрат. Еще при условии, что прямоугольники не имеют пересечений.да, я тоже так понял и мое решение прошло претесты. Долго размышляя над верным пониманием условия я сделал с таким пониманием неудачную попытку взлома на последней минуте.
Не вырывайте из контекста. В условии было:
множество точек, лежащих внутри или на границе хотя бы одного прямоугольника. ИМХО, вполне очевидно и однозначно, что тут имеется в виду.Господа минусующие! Объясните, пожалуйста, что непонятно в формулировке вида:
Даны множества. Объединение множеств - набор элементов, лежащих хотя бы в одном множествеНо ведь вполне можно было написать:
проверьте если данные прямоугольники составляют квадратЗачем путать участников на пустом месте?
Так это и было написано
Я на эту фразу долго моргала (прямоугольники образуют квадрат? чё?), пришлось разобрать примеры, повыбирать из двух пониманий и решить, что на 500 баллов, наверно, просят проверить объединение всего множества прямоугольников, а не объединение какого-то подмножества.
Как прямоугольники могут образовать квадрат я и сейчас не понимаю, так не пишут. А свой выбор пришлось проверять взломами (и ура, мне повезло).
По-моему, очевидный анрейтед раунд.
Что такое "составляют" не очевидно. Также непонятно, прямоугольник — это фигура на плоскости, или четыре линии? Может, именно линии должны образовать квадрат(и на внутренность при этом наплевать)?
Если уж выдирать из контекста…
множество точек, лежащих внутри или на границе хотя бы одного прямоугольникаКак по мне, так это в чистом виде определение объединения.
upd меня опередили
А можно пояснить почему неверно понять так: возьмем хотя бы один прямоугольник(да и вообще какое то непустое подмножество данных нам прямоугольников) и соответсвующее ему множество точек и сравним с множеством точек квадрата?
Потому что выбор прямоугольника относится к определению множества точек: сначала берутся точки, которые лежат
внутри или на границе хотя бы одного прямоугольника, а потом получившаяся штука сравнивается с квадратом.Как по мне, так это в чистом виде определение объединенияНу и что мешало взять и написать слово объединение в условии? Опасения, что условие стало бы чересчур понятным?
+1
Непонятно, что мешало. И куча людей не попалась бы, и я бы чуть меньше времени потратил.
Впрочем, формальное определение в условии написано было, так что я не вижу причины делать раунд нерейтинговым (как предлагают выше).
Почему В падает на претесте 9 ???
Переполнение.
http://codeforces.net/contest/325/submission/4064902
http://codeforces.net/contest/325/submission/4064759
Что тут не так, учитывая что n>=2. UPD: Починили.
пи*ц, такое состояние сервера — это международный уровень? да сколько падений, да еще и в конце упал, когда все сдают из последних сил. в конце сервер упал точно больше минуты — где продление контеста?
а задачи найс
Really disappointed by the last minutes of the contest.., I submitted the solution of the second problem 6 minutes before the end and it remained in queue until the last 40 seconds and then showed compilation error although it was running on my machine...!! http://codeforces.net/contest/325/submission/4064969
I think that it is being fixed. Because the number of ACs is increasing :)
The reason for the increase was not the fix but perhaps those submissions which were still in queue.. :(
So how do we solve B? ^_^
For any answer, let 'x' be the odd number one gets after dividing that answer by 2 repeatedly. then
n = x*(x-1)/2 + (2^a — 1)
solve this for 'x' using different values of 'a' (which are very few).
I think you mean
n = x*(x-1)/2 + x*(2^a-1)
Suppose a required number V has K powers of 2 in it (i.e. we will get an odd number after K rounds of matches). Then V is O*(2^K), where O is an odd number. Now you should write the number of matches as a function of O and K. It is an increasing function of O.
Then, iterate on K (0<=K<=64) and binary search for a valid O.
Why not start system test first..?
Because there is still a problem with hacking attempts...Some of hacks hasn't still been judged
Is it a guess? Or one can see it somehow?
Problem A was extremely confusing : subset v/s union. Something needs to be done about it.
Completely agree with you.
Someone tell me how to solve B?? I was stacked by that problem, then turn to E.Bu..guess what, my E pass the pretest...
This problem is straightforward.
Assume the answer is 2^k*k1, where 61>=k>=0, k1 is odd.
You need to find all (k,k1) such that 2^k*k1-k1+k1*(k1-1)/2=n
Since k is limited, you just need to solve the quadratic equation when k=0,1,2,3....
In the end, check whether k1 is odd, sort the solution...blah blah...
The difficulty is that n is too large.
I have to use BigInteger in Java to solve the equation.
I also saw someone use long double in C++ as well
Emmm...Generally clear(Why didn't I think of that>_<).THX~
Как решается задача В?
А она вообще решается?
Пусть x — это число, которое будет ответом, а y — максимальная степень 2, на которую оно делится. Тогда до того, как оно станет нечетным, будет сыграно x * (2y - 1) матчей, а потом еще
. Итого надо решить уравнение 
. Поскольку y достаточно мал — его можно перебрать.
Правильно ли я понимаю, что в double-ах можно было поймать ошибку точности и что решать следовало в целых числах бинарным поиском?
А если подходящие "приближенные корни" проверять, можно ли обойтись без бинпоиска?
Отличная идея! :) При проверке 100000 целых чисел слева и справа от корня тесты проходят, 4065977.
Спасибо! До формулы дошел, но забыл, что можно решать уравнения =(.
Для количества команд вида (2^M)*X матчей будет N = (2^M-1)*X+(X-1)*X/2. Вы знаете количество матчей. Перебирая M от 0 до log_2(N+1) и решая квадратное уравнение вы находите X и печатаете ответ.
Это не очень круто, когда сообщение о взломе приходит через 3 минуты после окончания контеста, хотя взломано оно было за 2 минуты до конца.
The first problem was very poorly written and not clear at all.And no explanation of the test cases made it worse.Very disappointing.
Can't agree more!
You just wait for system tests. I suppose something will change...
And for 2 hours I believe the statement for problem A was correct and couldn't understand how that could be a 500 point problem...
I couldn't agree more...
Хоть я и не участвовал в контесте, но скажу, что задача С мне очень понравилась. Идея решения весьма красивая :).
Yeah... This contest was exactly 0,5 sec too short for me to send my solution to E :P. I loaded my code but I didn't manage to click "Submit" :P. My greatest fail on an algorithmic contest!
Indeed, Accepted, eh :P. And 335th place instead of ~30th :P.
It's 3:30am in China,I'm waiting for the system test.....
Anyone know, why http://codeforces.net/contest/325/submission/4064830 got compilation error?
is that your main function without return 0?
It is ok to hava main without return, but it doesn't work for g++ if you do not have a return type for main(even if the standard says that no return type means return type is int)It is really strange.
(I use gcc version 4.6.3 (Gentoo 4.6.3 p1.13, pie-0.5.2) )
However, this is just a warning.
It's strange. Your code works on the "Custom Test" tab.
Maybe you should connect MikeMirzayanov and report this issue?
I've tried your code on the "Custom page" test and it ran correctly. Looks like not only JVM was crashed.
Make this contest unrated for those who suffered in the A problem..
I decided not to participate because I had a similar problem with a previous contest where although problem A was ambiguous I decided to submit a solution anyway which eventually turned out to be wrong.
when does system testing end usually ?? :)
Usually it doesn't start soon... :(
:(
thanks :)
How long does system testing usually last? :-)
system testing!! where are you??
Those who submitted the subset solution to A, should also get AC. Its lame that there was no such case in the pretests. My solution dint even get hacked.
You are right.
Some people was afraid to send one valid submission. 2551 people registered and only 1188 people sent solutions. Hard contest for div 2 coders like me.
Interesting .. I think I have never read problem statement so many times. And as a bonus, my interpretation of statement is wrong (at least according to the discussion). That's kind of disappointing.
My solution to problem A was submitted at 00:32. It was hacked at 01:32 but the hack was shown to me after around 10 mins of the contest. btw, I locked my solution at around 01:55. :P
subset solution passed XD
Very strange. My solution doesn't passed and all solutions, which failed on test 26, too.
Can you please tell What your code returns for this Input
2
0 0 1 1
2 3 5 6
Strange ... Dixtosa 's code return "YES" for the above case . yet his verdict is AC . bt I got Unsuccessful Hacking Attempt using this case. That Code returns "NO" . Can Anyone plz clarify me the reason.
It prints NO, because he have a bug: if(bit&(1<<i)>0) -> if((bit&(1<<i))>0)
Wish my code had bug too .
My subset solution failed test 26. But it's strange that I cannot find any difference between mine and yours~~
I answered above.
Ё-моё, систест больше, чем конест. Они что, с мобильника тестируют?
Наверное, не ниже айфона 4
The submission 4064843 got Compilation error and it should be Accepted, can you fix it please? And I made the following submissions after it: 4064970, 4065029 and 4065041. Can you delete them please?
Fixed.
Суббота, 13-е, вечер — сервер отдыхает, наверное, и не только сервер ...
Странное у авторов понимание "среднего" раунда, если победитель решает только 3 задачи
Ну первые 2 задачи, можно было давать, как B и C в div2. А Остальные три очень красивые и интересные. Получается, что всё норм.)
When and how will you announce the top 25 Silicon Valley residents?
Will be 2nd round :P
I think the 2nd round will be the onsite round.
Oh ye, sorry, i misunderstood the rules.
The 2 quotes that are not consistent. "with the top 25 Silicon Valley residents invited to participate on-site," Top 25 SV residents => eliminate all non-SV from rank and get 25 people.
"Yes, top 25 people from Round 1, who are in the Silicon Valley as of August, 3rd." => Top 25 from current rank who are also SV residents..
I guess there are no chances to get invited onsite if you are not in original top 25...
About Task B... I'm curious about how many test case is made by the author, or from which case it's from Hacking attempt. In fact, many got Wrong Answer in case #38...
4063931 4063524 4064205 4064405
One more: 4064766 (I suppose they just solved it the same way.)
Thanks
And what about this one 4064895? Will you ban it too?
Administrative repressions during online rounds of annual competitions continue...
IMHO, you have no ethical right to ban these submissions. This is like ban similar solutions for A+B problem. Once someone got the idea of this simple solution there are only a few possibilities to code it. So no wonder they are so similar.
4065191 4064895
Right. In this case there is matching of pair of submissions. Typically, if it is first time violation we skip the latest submission. I hope it will be a lesson for both of them.
I clarified the reasons about submissions noted by [user:cerealgy] below (in Russian).
O_O я надеюсь, у вас аргументы за бан повесомее, чем похожая реализация одного решения. А то страшно жить.
============================= (sorry for Russian)
I hope you have better reasons to ban them than just similar realizations of one idea.
Наташа, зачем на русский перешла?
Ты правда полагаешь, что это просто "похожая реализация"?
Она не просто похожи, синтаксические деревья программ совпадают. Код копировался и правился. Первые два кода вообще различаются практически только форматированием. Неслучайно код у zfmdhy786 набран без шаблона, тогда как все остальные попытки на C++ со вполне заметным шаблоном. А еще сравните решения kAc и zfmdhy786 по B. Опять "похожая реализация" с одинаковым синтаксическим деревом. Последняя троица из одного универа, что увеличивает вероятность не просто совпадения. Парочка kAc и liouzhou_101 давно практикуют парное программирование. Посмотрите контест 317. Там несколько задач имеют "похожую реализацию".
Я полагаю, если замечено очевидное списывание, то надо принимать меры.
Прошу прощения, потеряла дар речи от удивления. Сейчас переведу.
Я-то, когда кидала ссылку на еще одно решение, имела в виду не "это читеры, забаньте их", а "ух ты, какие короткие и похожие решения".
Я правда полагаю, что это может быть похожей реализацией. Решение-то простое: строим с конца, ставим каждый раз большего из возможных предков, когда доходим до 1 — заканчиваем дописыванием "0 1". Как это еще писать, если не так в этих посылках? Тем более, если участники из одного университета, логично, что у них один стиль. Вот еще, кстати, такое же решение: 4064517, от автора одного из раундов CF, тоже читерское? (Я и Gassa как-то написали еще более похожие решения на контесте, одинаковые вплоть до отступов, причем находились при этом в одной комнате физически. Списывания не было, был одинаковый ход мысли. Без шаблона я тоже иногда пишу, когда мне кроме stdio ничего не нужно — приятно, когда решение короткое.)
А может быть и списыванием. Если приглядеться, решение действительно странное (половину случаев в dfs-e можно безболезненно удалить, они нужны только для нечетного n, но для него все равно не строится), и предыдущая история, да, тоже подозрительная, и это как раз аргумент. Но даже с ее учетом, откуда уверенность, что ВСЕ они списывали?
==========================================
Sorry, I was so surprised that lost my speech. Will translate now.
When I gave a link to one more solution I didn't mean "ban these cheaters", I just meant "wow, how short and how alike are their solution".
I really think this can be just similar realization. Their solution is simple: construct the answer from the end, putting every time the biggest of all possible anchestors, and when we get to 1 — finish by writing "0 1". How can you write it other way than they did? And if they are from the same univercity, they can easily have common style. Here is one more similar-looking solution 4064517, by the author of one of CF rounds, is he also cheating? (Me and Gassa have once written even more similar solutions, ans there was no cheating. And I also don't use template when I don't nead it — I like short solutions).
And still, yes, it can be cheating. The solution is strange (a half of it is unnnecessary), and the previous story is strange too (and it's really a reason). But how you can be sure that ALL of them cheated?
... I print the result in a external file and observe them for more then 45mins but still have no idea until someone tell me "try to build the reverse-graph" then I have realized why it works.
Although it is a nice problem, but I think the score distribution may should be 500-1000-2000-2500-1500, there are some "constructive algorithms" problems are much harder then this one. http://codeforces.net/problemset/problem/198/D
Ouch.
Seems that 4064517 was not cheating. And make_pair (kAc, liouzhou_101) have shared code with 99% probability.
This is the same thing as when you're copy somebody's homework in school. Even your handwriting will change.
I'm not that sure now.
And thanks, i didn't know about changing handwriting and it actually explains some issues with my students. I wish I had that experience at school :)
4064825
I'm a little worried about the difficulty of Round 2. The announcement (http://codeforces.net/blog/entry/8051) says "comparable to a regular Codeforces round" for Round 1, and "higher than a regular Codeforces round" for Round 2. If today's C,D,E becomes A,B,C, and harder D,E is added...? I don't want to imagine that!
Actually this round's "more-than-difficult-C" was an accident.
...and we just underestimated the difficulty of D (this always happen for my problems... i wonder why).
Problem C is very straightforward and it's solution quite long. As I think, many participants solve it quickly and then spend a lot of time writting and debugging it. So, they simply haven't enough time for other problems. On the other hand, D need nontrivial ideas and have simple realization (very beautiful problem). In my opinion, such tasks are difficult for most of contestants due to lack of mathematical imagination. I think the main reason is that usually algorithms are taught directly instead of helping to invent them themselves.
I've found the main idea in D, but have problems with realization (there were two missed special cases: m = 1 and m = 2). The most difficult was contest time (21:00), as for me.
In problem D, my way was: let's start with maximal network flow of size M. To block it, there should be a cut of size M. But what is a cut of size M in N*M grid? It's obvious that it is a cycle in 8-neighbours grid.
Lots of corner cases is an idea problem, not realization. For example, I used another idea for searching a cycle which works correct with c=2 and I have only one small "if" for c=1 and still contains only one dfs to merge components without storing them explicitly. Finally, of course, using for(i=0;i<8;i++) with constants dx[8],dy[8] help you to reduce the size of your code and save you from bugs in copy-paste, but it is really realization optimization.
So, imho, mainly you have problems with ideas, not with realization. You've found the main idea, but not all.
Wow, I failed B on case 101 because of a precision error. I don't like this contest.
I liked this contest because it reminds me that precision errors are very important!
Is there something special about test #24 in D? Can't find my mistake.
Same here.
Try this:
6 6 14 1 1 1 4 2 2 2 5 3 3 3 6 4 1 4 4 5 2 5 5 6 3 6 6 1 6 6 1
Expected answer is 13
Thanks!
I got this runtime error during the contest: Error occurred during initialization of VM java/lang/ClassNotFoundException: error in opening JAR file C:\Programs\Java-7\jre\lib\rt.jar
http://codeforces.net/contest/325/submission/4064975 Anybody got any idea why this is the case?
[EDIT] http://codeforces.net/contest/325/submission/4066219 It's AC! Can this be fixed? :)
problem B wa on test45,but the code gives the right answer when running on my own computer.change unsigned long long to long long,I got accepted.
Please ignore this comment, editorial is already posted by AlexSkidanov
Пожалуйста, поменяйте линк на разбор в русской версии сайта. Он ведет на английскую версию разбора, более того, он ведет на
codeforces.comи происходит разлогинивание.Для меня русская версия сайта — это http://codeforces.net/?locale=ru, и очень надоедают ссылки, ведущие на codeforces.ru.
В любом случае, линк ведет на английский разбор, при наличии русского. Непорядок :)
На всех четырёх сайтах CF для таких случаев удобны относительные ссылки с кодом
[относительные ссылки](/blog/entry/8341), они не перемещают между сайтами.Hello. I have competed in the first round and have taken place 311. So can I compete the second round at home via internet? And when will the second round be held?
The second round will be held online for the Non-Silicon Valley Participants I believe. I will (hopefully) be there too, although I was told I took place 386 but the standings show me at place 408.
any update on SV participants?
Mike will send out all the information to top500 very soon.
Тем кто прошел во второй раунд прислали письмо, и попросили ответить на пару вопросов.
Отличный вопрос про размер футболки, с вариантами ответа ES, S, M, L, EL.
У меня есть две футболки от одной и той же компании, но разных лет.
Так вот футболка с буквой M больше футболки с буквой L
Так бывает, если одна из них Ж (а другая М).
Так бывает всегда.