Всем привет,
А знаете ли вы, что завтра состоится Codeforces Round #157? Его автором являюсь я, и это мой седьмой раунд на CF. Помогает мне его строить Gerald, спасибо ему за это.
Разбалловка в первом и во втором дивизионах стандартная: 500-1000-1500-2000-2500
Желаю вам удачи!
Top-7 Div1:
Top-4 Div2:
Спасибо за участие.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
Since GCD(4,7)=1, every round number can be considered lucky ;)
If you are to find positive values, only any greater then ab-a-b.
157 div 1 = 7*7*7 — 4*4*4*4 — 7*7 — 4*4 — 7 — 7 — 4 — 4 = 7^(7-4) — 4^4 — 7^(sqrt(4)) — 4^(sqrt(4)) — 7*sqrt(4) — 4*sqrt(4); 157 div 1 = 77 + 44 + 44 — 4 — 4; 157 div 2 = 44 + 44 — 7 — 7 + 4;
It can be concluded that the round for first division will be more difficult than for the second division.
Exactly how much time did you spent calculating it ? :P
5 minute
Why this article is not on the main page?
"Round will not use dynamic system" Shouldn't it be more explict to write "Round will use standard distribution"?
it's because the score distribution may won't be standard(for example : 1000 1000 1500 2000 2500 is not dynamic nor standard)
It is the third "Ukrainian" round in a row! Waiting for a nice one)
Ну и зачем ты кичишься "украинским" раундом? Ты националист? Признавайся, это [ты]?(http://www.youtube.com/watch?v=RrwLGOCiqGA)
И этот недотролль на девятом месте по вкладу. Парадокс, одно слово...
Petr?
Мне кажется, что из тех троих с вкладом 136 не сложно догадаться кто это пишет)
ivan.popelyshev? So unexpected!
By the way, if you think somebody uses multiple accouns, you can contact MikeMirzayanov.
You can send him a private message on Codeforces. May be, you know his e-mail.
What does "the score distribution will be announced later." mean? isn't it always like 500:1000:1500:2000":2500 ?
Not always. The most common distribution is 500 1000 1500 2000 2500 but there are exceptions. That means that some problems will be harder or easier than normal.
what does "dynamic system" mean?
Dynamic scoring system is the system in which you receive points only for a correct solution and the received points are inversely proportional to the time it took you to solve the problem.
No, this is dynamic system.
Oh, I didn't know that. Thanks a lot ! Sorry if I confused someone .
Wow! Mr. witua's problemset is always great! ;)
when the score distribution will be announced.
Good luck to all^O^
More and more times we help little Elephant :D
Is this the first round after end of the world?
I have a doubt . If I solve the first problem 10 minutes after the start of competition and second problem after further 15 minutes i.e. 25 minutes after the start of competition . Then while calculating the score for the second problem solved will the time considered bye 25 minutes or 15 minutes . If it is 25 minutes , then is it not better to solve difficult problems first because there the penalty is larger . The text says it is better to solve problems by order in difficulty ( ascending or descending ) . May be difficult problem will large time so will affect time of larger number of problems , hence ascending order of difficulty . But just clarify which time will be considered . Thanks .
25 minutes after the start of competition
You'll have the penalty for 25 minutes, since they can't know how much time you have used for each problem... The most people start with the easier problem but others prefer to start with problem E, up to you to choose your strategy.
Thanks for responding before my 1st contest . Good luck
25 minutes.
Почему в английской версии присутствует "магическая" строчка, а в русской нет?
Потому что в английской версии будет не динамическая система, а в русской — динамическая :D
что за дискриминация по языковой принадлежности?)) Так делать нельзя))
Задачи наперно как всегда про слоников)
Обязательно про маленьких!
Немного зафэйлили сложность
Contest was interesting, but it has a problem: from the one side first 3 problems were really easy, but the next 2 were very hard (as for Div 2). But thanks in any case.
Apparently not that easy actually; there are a lot of hacks happening. (I think problem C has many hacks.) The first three are easy but somewhat tricky.
any challenge case for C?
Nop, but some have forgotten the cases with only 1.
I did.and u hacked me :( However good that you did,else it would have failed system tests and I wouldn't have got any points.
Even so, they were too unbalanced. 1200 ppl having OK on pretests for A-C and 30 for D?
I'm fine with problems whose difficulty is based mostly on tricky cases (or using an appropriate bruteforce to escape such cases), as long as they don't make up more than half of all problems, which was not the case in div. 2.
Задачи просто супер особенно на взломах
контест какой-то упоротый
3 халявы + 2 гроба(для 2 дива) ---> за счет взломов можно было подняться, поэтому все зависело от участников в комнате
Расскажите как решались задача Д и Е(див 2) Очень уж интересные задачки)
в D перебор размещений с разбором каждого из 8-ми случаев. Пусть S — количество счастливых чисел <= m. если мы нумеруем партию однозначными счастливыми числами(4 и 7), то, очевидно, количество способов будет 2*A(6,m-S) если мы нумеруем партию двузначными счастливыми числами(44, 77, 47, 74), то количество способов будет 4*A(6,m-S) + 4*2*A(5,m-S) и так далее
D:
Посчитаем динамику d[cnt] — сколько чисел от 1 до m с cnt счастливыми цифрами. (С помощью второй динамики d[len][cnt][0..2] — сколько чисел длины len, с cnt счастливыми цифрами и меньше/равны/больше соответствующего префикса числа m).
Будем рекурсивно "фиксировать" текущее число, т.е. напишем функцию, которая возвращает количество способов составить последовательность из len чисел, и чтобы общее число счастливых цифр не превзошло cnt. Внутри — переберём количество счастливых цифр в текущем числе, вычтем единицу из соответствующей динамики(!), прибавим к ответу (количество способов выбрать текущее число)*(вызов функции для len - 1), прибавим единицу обратно.
Это решение делает не более (грубо) 107 операций, т.к. чисел 7 и количество счастливых цифр в каждом из них от 0 до 9.
Код.
Вместо подсчета динамики можно сделать предподсчет. Посчитаем локально массивчик p[i][j] = количество чисел из интервала [1..107·i], в которых ровно j счастливых чисел. Сделаем это за O(MlogM). Предподсчет работает минут 5. После этого в задаче мы сможем за O(107) досчитать нужный нам кусок.
Если сделать более мелкое разбиение (например, 106, то не хватит 64 Кб на исходный код, а если больше, например, 5·107, не хватит времени). А константа 107 укладывается идеально. Пример решения 2816283
Любой коммент про решение с предподсчетом минусуют. Не знаю почему, наверно, намекая, что надо уметь писать динамику..
Как решать E?
Сделаем структуру данных, чтобы хранить в каждой вершине дерева число и уметь добавлять и вычитать единицу в поддереве. Это можно сделать, пронумеровав вершины в порядке обхода в глубину и построив дерево отрезков. Будем решать офлайн. Для каждой вершины запомним список вершин, с которыми она есть в запросе. Сделаем обход в глубину. Числа в структуре данных будут обозначать количество общих чисел в списке текущей вершины и каждой из остальных. При входе в вершину добавим единицу во все поддеревья, которые есть в запросах в паре с этой вершиной, и в саму вершину, если в нее есть запросы. После этого получим ответ для вершины как количество вершин с ненулевым значением. При выходе из вершины вычтем все обратно.
i think that the A,B,C questions were very easy
Were*
REALLY ???
First 3 problems all done in 14mins... Well it's all problems that I can finish
Контест был прикольный. Из 3-х халявок я зафейлил 2 (мне их взломали), при этом С-шка уже была заблокирована. Получались очень интересные взломы. Мою С-шку взломали на тайм-лимите (невнимательно прочитал ограничения и написал квадрат). Радуют только 3 взлома на А-шке.
Гыгы, где-то с 35 по 120 место почти все делали взломы.
Мне одному показалось, что Div1-A по сложности как Div2-A?
Не тебе одному. Даже легче.
Задача на разрыв шаблона.
На решение уходит 60 секунд, а потом взгляд в монитор... Хм... никто еще не сдал... Где же здесь подвох?
Нет, не может быть так просто...
Ищем подвох...
Продолжаем искать.
А когда Egor начал ломать с интервалами в 30 секунд, у меня вообще сердце в пятки убежало.
Во-во, увидев кучу взломов, тоже побежал искать контрпример)
А на чем тут ломать можно?
1111111
1111
111 не учитывали что нет 0
Не знаю, я один взлом сделал на банальном слишком маленьком массиве.
Если я правильно понял, то некоторые искали, где в строке первый ноль, не учитывая, что его может и не быть
Многие невнимательно писали решения, от чего не удаляли единицу, если не нашли нулей. У меня в комнате на этом погорело 5 или 7 человек. Див2, конечно, но на этом, думаю, и опытный человек может погореть случайно.
ну я неправильно обрабатывал числа состоящие из одних единичек
У меня был взлом на 11111...11111 (х100000)
При том рассчитывал на ВА, а взломал по ТЛЕ)
Задача на храбрость. Я вот долго-долго искал подвох.
мне кажется, это просто хороший способ привлечь больше людей к контесту.
задача щимитель очкунов — вон почти все участвовали, когда А более сложная, участвуют около 400 человек из примерно 680.
in div1 second problem had a hard implementation and no special algorithm which i didn't like.the whole contest had too much mathematics in it i guess. calculating expectations is HARD.
You can brute force (10^5 is easy). Or otherwise just note that the sum of all numbers minus the sum of the main diagonal is exactly twice of the sum of a line, but this is also exactly what we're given. The rest is left as an exercise (read: implementation problem).
...misread comment. I need to pay more attention to "1" and "2".
I don't mind a lot of mathematics in the contest; in fact I like it. (Okay I'm an IMO participant so that's biased.) But the point is that it helps you to learn more than usual implementation problems. You can use Google/Wikipedia while you're competing right?
It's Div1 B, not Div2.
are u sure u participated in div1????!!!!
I'm sure I did B Div1 (D Div2) though.
...yeah, now I reviewed my solution, I agree that it's hard to implement and has no special algorithm. Sorry for the confusion. (I must not take contests at 1 AM.)
No idea on how to calculate number of numbers with at least some number of lucky digits in a range... I suck.
классное изменение условия Б в начале контеста, конечно. со сложностью С пофэйлили, и не кажется ли автору, что давать две задачи на подсчет количества способов очень странно, мне кажется, все задачи должны охватывать разнобразные темы.
Это было не изменение, а просто обращение внимания.
исправление двусмысленности условия
Fast testing: Is it our christmas's gift?
That awkward moment when you can't decide whether to try the next problem or start hacking other's solutions.
Как я понял, запилили фичу: просмотренные решения помечаются зеленым. По-моему, решения, которые были пересланы остаются зелеными. Хотелось бы, чтобы это пофиксили.
да нет, вроде синими после перепосыла становятся, не?
Хмм, что-то я криво посмотрел, может быть. Или вы про цвет текста? Не очень очевидное поведение. Да и оно скорее всего не пропадет при просмотре
Ну, у меня взломанные или переотправленные решения начинали иметь светло-синий фон.
Ага, и мой ViewedSubmits-юзерскрипт торжественно поломался и заблокировал возможность просмотра чужих сабмитов. Надо пофиксить.
That awkward moment when you can't decide, whether to try the next problem or to start hacking other's solutions.
When the system tests start?
Started already, enter the contest and see the "Status" tab
ok thanks
WOW new feature in codeforces that when hacking, every code that you have seen it before will colored in green to make it easy to know what codes you have not seen it yet.
It was already on the previous contest. And yes, it is awesome. But I'm disapointed that we can't reset the colors (like "mark as non read" for client mail).
I found someone submitted only his template code and got passed. Maybe Div1 Problem B is a previous used problem. Look at these submissions: 2812620 2812759
Just finished up my first contest at CodeForces . I attempted the first three problems in Division 2 and spent rest of time trying to figure out problem D , but to no avail . I have a question : Do the hacks have to made within the 2 hours of the contest itself . And can I hack within my room only or elsewhere also . Can I hack a solution of problem that I have personally solved or can I hack solution to any problem . I was thinking that hacking phase would be after 2 hours . I recently started participating topcoder.com SRM's and there hacking phase which is called challenge phase starts after the coding phase . They have 75 minutes coding for 3 problems , 5 minutes intermission and then 15-20 minutes of hacking phase . I guess I had to press the hacks tab during the contest to be able to hack . Still have not seen the interface of hacking . Tell me something about it .
1- in 2 hours
2- your room only
3- only problems that you solved after locking it
FAQ page is not meant only to make the menu bar bigger .You should go through the rules here
fast system test :)
Good round overall, but i couldn't submit any hacks on problem C div 2.
Thanks @kingofnumbers What is the process of locking the solution . I didn't lock any solution . I just submitted and watched the message that it has passed pretests . I have not suffered because of that because system testing of DIV 2 has ended and I can see myself in final standings with points of all 3 problems I did . Do I need to do something else also to lock my solution of just a submit means locking . Or is there some concept of lock once I click on the "Hacks" tab . ????
Meanwhile I too feel like many , that the first 3 problems were too easy and last 2 two too difficult . Some medium level problems were missing , I feel .
You can lock your problems by going to the dashboard of the contest and clicking on the lock icon aside of the problem you have solved.
don't be afraid, you will get points on problem that you solved even if you did not lock it, but you may lock it if you want to hack the others' solution , locking a problem means that you can't resubmit your solution again if you find a bug in your solution
Глупый слоник меня минуснул
Минусуйте меня полностью
И Слоника позовите
red ^_^ thanks for the contest
Congratulations! Waiting for Div 2 rating update, hopefully I will be first time in Div1. And just before new year, like a new year gift
Congratulations!~
the contest was terrible. you sucked with your problem set.
How soon are the ratings likely to be updated . I want to know whether I will be eligible for next Div2 contest which is happening soon or will I be promoted to Div 1 . I have 376 rank in Div 2 today .
Sorry, but you can be sure you'll remain in Div2
I think to be eligible for Div1 for first-comers(rating 1500), you need to have a rank of 5+ or so.
My experience: Rank 16-> Rating 1476->1663
Anyway my rating is going to drop >_<
You are in div2 for sure. the real question is will you be blue or green?.
about 1550 I think ....
I cant believe it. My submission number 2812603 passes the test case 11 (458754) for which it gives the answer 667496909 on my computer.
It is giving correct in custom test as well, better contact the admins.
Yeah! Finally div1
+1
Задача B div2, на 8 тесте получил ошибку "wrong output format Unexpected end of file — int32 expected", что бы это значило?
Ваша программа ничего не выводит на том тесте.
Ввод 0 98721 99776 99575 0 99123 98922 99977 0 Ответ 99550 98721 99776 99575 99349 99123 98922 99977 99148 Протокол тестирования wrong output format Unexpected end of file — int32 expected
вроде как выводит, не понимаю...
Вывод программы следует искать под словами "вывод", а не "ответ".
Вау, я стал фиолетовым!
УРАУРАУРАУРАУРАУРА
Думаю, ненадолго
Тут "не надолго" пишется слитно
А ещё предложения стоит начинать с большой буквы, заканчивать точкой (в данном случае) и после "думаю" запятая не помешает :D
Now waiting for the tutorial
what happened!! my code still running!!! after updating new ranking !!!
http://www.codeforces.com/contest/259/standings/page/42
Problem A, Div-2.
00:07:28 Running on test 31 [final tests] → 2808294
i lost 87 points... showing my rank 823.. what the is this??? @codeforces authority.
AC now, after sending mail to admin, but rating not yet updated..... hope to recover the bug soon.... :)
и опять контест от witua, и опять автор перепутал местами D и E.
Жду твоего раунда, где ты ничего не перепутаешь.
Не нужно быть поваром, чтобы оценить блюдо (с)
во-первых не дождётесь, так как я не известен в кругах сообщества сп и не являюсь красным. во-вторых, предыдущий контест, я так понял тоже от вашего друга Sereja, абсолютно такой же получился, так что ради интереса я жду ваш контест.
а вообще я это написал к тому, что если и подразумавалось такое, то и динамическую систему очков можно было поставить...
Дискретная динамическая система, а именно такой она является, никуда не годится, думаю все соглашаться, что когда 1 сабмит делает задачу в два раза дешевле — это немного не то.
Возможно, когда-то и будет мой контест, но объективно понимаю, что здесь нужны разнообразные задачи, а у меня они все чем-то похожи. Я предпочитаю давать задачи на индийский проект, там за все время не видел ни одного участника, который ругал бы авторов. Там все обсуждения состоят лишь из благодарностей за контест и, прошу заметить, содержательных обсуждений задач. Мне это больше по душе. Возможно, это потому что у тех людей менталитет другой, и они понимают, что никогда не ошибается только тот, кто ничего не делает.
Конечно, на кодфорсес есть масса приятных и умных людей, ради которых я и захожу на эти блоги, но такими далеко не всех назвать можно.
Why these submissions got TLE? I don't have a clue.
In the first submission you calculate
strlen(A)in every iteration of main loop. There are exactlystrlen(A)iterations of main loop, so you solution is O(strlen2(A)), it is about 1010 operations, so TL.Thanks. I had thought the compiler or CPU may cache this constant.
About first submission — strlen function works in O(n) time
About second submission — I don't know Java at all, but it seems that this code
res+=line.charAt(i);works in O(n) timelen.charAt(i) is O(1) but res = res + len.charAt(i) uses string concatenation which is O(n) because a new string object is being created
You are right, thanks.
Когда будет разбор?
Как скоро будет разбор?
Уже есть на инглише http://mirror.codeforces.com/blog/entry/6213
На русском будет?
There's something wrong in test program on div2 A. Somebody prints "No" as the result(2817648), but the answer should be "NO". I tried to hack it, but failed.
Maybe validator check the first later of output :D
In contest time I solve problem A with Submission Id 2814881. But in System test I get a verdict "Running on test 33". And my ranking and Rating is built on without accepting A. But Why ?? Please Rejudge my submission.
А где noh4h_ss в списке победителей Div 2?
И вправду, где? Человек старался, выигрывал контест, а о его достижениях никто не упомянул.
Задача div2-C: Почему 2810793 не падает на максимальном тесте? Это же квадрат, или нет?Блин, туплю, там O(NlogN).
why am I div 2 winner? noh4h_ss won the contest. no?