Блог пользователя MinakoKojima

Автор MinakoKojima, 13 лет назад, перевод, По-русски

Три промаха друг за другом, и вот я мигом вернулся в желтый цвет...

Раунд Codeforces Round #183 пройдет в воскресенье, 12 мая, в 17:00 MSK (21:00 CST). Сразу после раунда Google Code Jam Round 1C.

Авторы раунда:

  • Yuzhou Gu sevenkplus (Задачи B и E)
  • Yuping Luo roosephu (Задачи A и D)
  • Jiatai Huang CMHJT (Задача C)

Тестеры:

YuukaKazami, havaliza, Velicue и я.

Мы благодарим Геральда Агапова (Gerald) за помощь и советы по задачам, Delinur за помощь с переводом задач на русский и MikeMirzayanov, разработавшего такую мощную платформу.

Настоятельно рекомендуем Вам просмотреть все пять задач, хотя бы одна Вам обязательно придется по нраву.

И еще кое-что. В этот раз будет динамическое распределение баллов по задачам, тем не менее задачи расположены в порядке предполагаемой сложности.

Удачи!

  • Проголосовать: нравится
  • +128
  • Проголосовать: не нравится

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Great!! I think it will be a great contest while the setters and testers are very good. Thanks for your soon post :)

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

Not in midnight in Japan(and other far east Asia and Australia) Great!!!

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Codeforces Round #183?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Are you sure in number of this round? Think, it should be 183.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Very early announcement and score distribution (many peoples has like it), great setters and testers — I think it will be very interested.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Haha noone even mentions Div2 A and Div2 B problems :D

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

I think the problemset is easier but much more interesting this time..

»
13 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Am I right that original statements will be in english?

»
13 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится +6 Проголосовать: не нравится

Why this blog was not on home page ?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

The first time I can participate in

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Hmmm contest time changed? 6AM in California...

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -7 Проголосовать: не нравится

Why time is non-standart?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +17 Проголосовать: не нравится

It would be interesting for me(and I think not only for me:)) to know some additional information about the authors of the contest — your hobbies, photoes, interesting stories etc.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится

I wondered why comments by MinakoKojima got so many negative feedback?

»
13 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +39 Проголосовать: не нравится

A question : is MinakoKojima (Feihu Tang) boy or girl?

I thought the name is a boy's, but in his(or her) photos shared above it's a girl....

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +39 Проголосовать: не нравится

I recommend you all to participate in this event. You would enjoy solving this set of beautiful (and challenging :D) problems. :)

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

давненько не было динамического распределения ^_^

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

It is the Chinese round. I am really excited to see the problems! :) We had American problems (with USACO cows' background), we also had Japanese problems (rng_58's and the rest). And now is Chinese round. Love it.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Спасибо за контест! Всем высокого рейтинга(правда такое невозможно :) ) и удачи!

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -6 Проголосовать: не нравится

=w= unsuccess to reach 1500 last match...=w= so ..hope my friends and i can reach blue again ..T_T

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

в задаче B может быть 2 дата быть раньше чем 1 ?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +22 Проголосовать: не нравится

Получать в div1 клары по поводу задач div2 — это баг или фича?

  • »
    »
    13 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Не баг и не фича. Просто это так. Более того если ты во время контеста просто будешь находиться на сайте, то тоже будешь видет клары.

    • »
      »
      »
      13 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      Вопрос не только в этом. Это я сам уже понял. Сегодня меня заинтересовало, зачем в контесте отображать клары по задачам, которые не имеют к нему отношения (div1 D — div2; div2 B — div1). Уже, кажется, сам догадался, что это вызвано особенностями самой системы.

      Подозреваю, что для приведения этого в более логичный вид — надо многое в системе переделывать, так что обойдемся:(

      • »
        »
        »
        »
        13 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        Ну представь, что ты начал решать контест но пока ничего не послал. Тогда тебя невозможно отличить от человека, который просто читает посты на сайте. Ты отличаешься только тем, что зарегистрирован на контест.

        • »
          »
          »
          »
          »
          13 лет назад, скрыть # ^ |
           
          Проголосовать: нравится +5 Проголосовать: не нравится

          Захожу я в контест, смотрю "Вопросы по задачам", читаю то, что там написано. У меня там отображается одно и то же для обеих дивизионов, все клары для всех 7 задач дня, а не только клары по тех 5 задачах, которые были именно в этом дивизионе.

          Я об этом "отображении". Прошу прощения, если сначала не совсем понятно выразился.

          • »
            »
            »
            »
            »
            »
            13 лет назад, скрыть # ^ |
             
            Проголосовать: нравится 0 Проголосовать: не нравится

            А понял. Ну это нехорошо. Но дело в том, что сообщения со всплывающим окном заведомо делаются общими и не несут связи с дивизионом. В этом и проблема.

  • »
    »
    13 лет назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    У меня сразу при прочтении возникла мысль, что клар к div1 В и из-за ошибки в переводе слова "data" речь идёт не о данных, а о датах .

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

are there any mistakes in sample tests in problem B div 2?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -21 Проголосовать: не нравится

Congrats for making unrated contest.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +26 Проголосовать: не нравится

The contest was perfectly prepared and tested :D

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

Why in B in the second sample the answer isn't (29,22,75,78)? In this rectangle distance from the center to the point (x,y) is 0, and in the answer to the sample it's 0.5.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Missed the round — no mail?

»
13 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +124 Проголосовать: не нравится

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +36 Проголосовать: не нравится

Как нормально решать С?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div2 D?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -10 Проголосовать: не нравится

Когда хакал, у чувака было время выполнения 2.6 секунды, а в задаче ограничение 2 секунды. Хак не защитали. То есть это ок, да?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +43 Проголосовать: не нравится

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Lots of hacks on A div2 with test "10000", library solution on B div2 on Delphi, unprepared B div1. Nice.

»
13 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

У меня вопрос к тем, кто готовил задачи. Вы вообще свои условия читали? Вы хотя бы картинки смотрели в них? Мне весь контест приходили клары, которые заставляли меня открывать браузер и проверять, не взломали ли меня. Зато по злой иронии (я пока что не знаю почему) взломали мое решение по C за 15 секунд до конца, а нотис об этом я получил через 15 секунд после конца контеста. Задачи, в общем-то, неплохие, но уровень подготовки контеста оставляет желать лучшего. Особенно порадовал клар по задаче второго дива. Спасибо, будем чуть больше знать про даты.

UPD. Простите, поторопился с оценкой качества задач. Ниже написали, что задача D решалась популярной статьей из wiki. Набор задач после такого вряд ли можно назвать неплохим.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +108 Проголосовать: не нравится
»
13 лет назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

Кстати, у меня после успешной попытки взлома переходило на английскую версию сайта. Устраните проблему, пожалуйста.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

I think the limit of n for A div 2 should be 10^3 or 10^5. Most of my room has a O(n^2) solution. Especially a nearly O(n^2*log(n)) succesful in defended 2 attack.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -13 Проголосовать: не нравится

Объясните, пожалуйста, а почему у всех проходят (по крайней мере, претесты) такие простые решения по С?

Почему не может быть так, что если бы удалим одно число, это повлияет на много пар, в которые оно входит?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +24 Проголосовать: не нравится

Because of so many mistakes, I strongly think this round should be unrated.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +100 Проголосовать: не нравится

Не знаю как в английском варианте, а в русских условиях количество ошибок было больше чем в моей контрольной по матану на первом курсе!

»
13 лет назад, скрыть # |
Rev. 5  
Проголосовать: нравится -40 Проголосовать: не нравится

Dynamic scoring usually makes scoring very different from past. Will it influence the rating system?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +15 Проголосовать: не нравится

What a funny round!

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +23 Проголосовать: не нравится

Сегодня я узнал, что такой код

import java.math.BigInteger;

public class D {

	public static void main(String[] args){
		BigInteger.valueOf(3).isProbablePrime(1);
	}

}

под Java 6 и 7 на CF в запуске работает 5 секунд :(

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -21 Проголосовать: не нравится

Great round, interesting problems. :-)

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

The problem is nice,but clarifications too disturb.Waiting for next round.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

My O(N^2+k^2 a_max log a_max) solution passed system test of problem C with a lot of brunch-cutting... I think it is not intended...

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Nice problems. A lot of maths, but It's enjoyable. :)

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Intereting problems!

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +50 Проголосовать: не нравится

The data for div1 D seems weak. When N=1, it's clear that every base works, so the answer is x-1 if x > 2 and -1 if x = 2. However, some solutions that didn't handle these cases still passed system tests. For example, 3709363 gives 1 on the case "1 2".

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

What is the solution for problem Div 1 — C (Div 2 — E) (Minimum Modular)?

»
13 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

System testing of Div.2 was very bad.it was finished , but final standing was not ready!

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

Div.2 A

My code is TLE. ~~~~~ ans=sqrt(0.0+SQ(i)+SQ(j)); if( ceil(ans)==ans ) cnt++; ~~~~~ But I change “(int)ans==ans” ,then get AC....

TvT

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Долой 31й тест в задаче B див2! "сколько между ними дней включительно"

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Только что с права видел ссылку на разбор. Но когда кликнул попал на свой профиль. И всплывающее окно, что недостаточно прав. Мне кажется, что это бага.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

ORZ failed div.2 A

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

For Div2 C, now I understand why I could not find any formulas for even values of n..

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Weak pretests :(. B-Wa 11 because of mixing up n and m.

»
13 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Wow constraints were really strict.

My DIV2 A didn't pass because of the c++ floor method which is too slow, compared to a cast. For DIV2 B, why doesn't it work using mktime and difftime from ctime? ...

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

my final tests are checked but its showing skipped what does it mean????? http://www.codeforces.com/contest/304/submission/3709339 please clarify it...

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится
»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to get full test cases for: http://mirror.codeforces.com/contest/304/problem/E?

Thanks!

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +32 Проголосовать: не нравится

Такого со мной еще никогда не было. Я хотел взломать решение dilutedream а. За 23 секунды до конца вбил тест подумал, что он не корректен. Подправил его и снова сделал взлом. У вот теперь я вижу, что мой первый взлом оказался удачным, а во второй раз за одну секунду до конца я взломал kingofnumbers. :-)

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +307 Проголосовать: не нравится

Having spent about 20 submissions trying to find out the reason of my wrong answer on test 8 in Div1-E, I've managed to receive the following outcome from the judge:

wrong answer 201st numbers differ — expected: '-0.0132824', found: '0.0124727', error = '0.0257551'

This doesn't look like a correct probability, does it?

»
13 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится -19 Проголосовать: не нравится

Задача D div1 во время систеста имела 56 тестов, сейчас там есть как минимум 57, и некоторие accepted решения не проходять етот 57 тест.

»
13 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

It seems I solved 303C - Minimum Modular with brute force 3712393 which, I think, is O(5000*10^6) in the worst case.

Is there any testdata which challenges the program or I calculate the complexity wrong?

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone provide a proof of Div I Problem A? I just noticed the pattern for n <= 10 and just submitted that hoping it would work.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится -30 Проголосовать: не нравится

Стоит tourist-у написать комент, как он получает кучу плюсов :)

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

For this very fast solution to problem A in div2, could someone explain the math behind it? Thanks.

»
13 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

How to solve div2 E-Minimum Modular? Thanks in advance.

  • »
    »
    13 лет назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится +44 Проголосовать: не нравится

    means "ai - aj is not divisible by m. So calculate the differences of all pair of integers.

    We check that "if we choose m to modulo, we can do the array satisfies conditions?" for all integer m until we find m from (n-k).

    Answer ≤ 106 + 1 because if we choose 10^6+1 for m, obviously it satisfies condition.

    When we search about m, all we have to do are research about multiple of m and get the array of "Which pair of integers are same modulo m". If the size of array exceed 10(), give up search.

    In this solution, the order is O(N^2+a_max log a_max+k^2 a_max) because O(1/1+1/2+1/3+...1/a_max)=O(a_max log a_max).

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

When will the editorial be published? I really want to know how to solve Div1E...