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

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

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

Раунд 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
  • Проголосовать: не нравится

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

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

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

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

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

Codeforces Round #183?

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

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

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

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

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

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

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

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

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

Am I right that original statements will be in english?

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

Why this blog was not on home page ?

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

The first time I can participate in

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

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

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

Why time is non-standart?

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

    There was a risk of yesterday’s TCO Round 2C being cancelled and moved to 16:00 UTC today. Codeforces’ usual 15:30 UTC would conflict with it. It already happened with round 2A on 31st of March.

»
12 лет назад, # |
  Проголосовать: нравится +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.

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

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

»
12 лет назад, # |
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....

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

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

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

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

»
12 лет назад, # |
  Проголосовать: нравится +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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Congrats for making unrated contest.

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

The contest was perfectly prepared and tested :D

»
12 лет назад, # |
  Проголосовать: нравится +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.

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

Missed the round — no mail?

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

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

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

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

How to solve Div2 D?

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

    first make a and b coprime try to max the length of x such that x%a=0, then check if y falls in range. if not, max y such that y%b=0

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

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

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

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

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

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

    python lol)))

    from datetime import date
    
    a1 = map(int, raw_input().split(":"))
    a2 = map(int, raw_input().split(":"))
    
    print abs((date(a1[0], a1[1], a1[2]) - date(a2[0], a2[1], a2[2])).days)
    
»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

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

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

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

»
12 лет назад, # |
  Проголосовать: нравится +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.

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

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

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

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

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

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

    if so, this will third continuous unrated contest :)

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

    I agree with you.The questions were published so late that we had misunderstanded the problem and wasted much time. BTW, the D is a popular knowledge which you can find it on the Internet.So, I hope this round will be unrated.This is the only way to make it fairly.

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

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

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

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

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

What a funny round!

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

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

import java.math.BigInteger;

public class D {

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

}

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

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

Great round, interesting problems. :-)

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

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

»
12 лет назад, # |
  Проголосовать: нравится +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...

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

    an O(n^2+ans*k^2+a_max ln ans) solution was expected.

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

      Sorry, I mistook the analysis of my order... My solution was your order, thank you.

      I think TL is too short because my solution passed in over 1800ms with a lot of brunch-cuttings...

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

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

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

Intereting problems!

»
12 лет назад, # |
  Проголосовать: нравится +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".

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

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

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

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

»
12 лет назад, # |
  Проголосовать: нравится +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

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

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

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

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

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

    Нет, просто разбор случайно опубликовали и потом сразу скрыли в черновики.

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

    Автор убрал блог в черновики

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

ORZ failed div.2 A

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

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

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

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

»
12 лет назад, # |
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? ...

»
12 лет назад, # |
  Проголосовать: нравится 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...

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

    Are you sure your solution is your own, not copied from others?

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

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

Thanks!

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

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

»
12 лет назад, # |
  Проголосовать: нравится +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?

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

    I've got TLE 8 during the contest, but later I optimized my solution a bit and now it's giving the same answer as yours on the 8th test even when I use long doubles.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -36 Проголосовать: не нравится

    All tester's program have different solution so you know

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

    the model solution of E is wrong...it has precision problem.

    the setter is trying to fix it... but still rng58'solution seems has precision problem too...

    actually they all work fine when n=40, but start to differ when it become bigger,when I change the double in model solution to long double,it seems it is the same answer with KADR.

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

    I've asked the author to give me his solution, and the author's solution returned even worse answer (smaller than -10000) for the following case:

    int main(void){ int i; cout << 80 << endl; for(i=0;i<80;i++) cout << i << ' ' << i+80 << endl; return 0; }

    My solution during the contest (got WA) also contained precision errors for this case. The probabilities were between 0 and 1, but the sum of the probabilities in some row was more than 22 (while it should be 0).

    Currently I guess it's impossible to solve this problem precisely under the given constraints.

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

    Yes, you are right. The author's solution is wrong for that tetscase. But all the pretests were right.

    So, now we are discussing how to solve this problem with precision and make the results of the round as fair as possible.

    Thanks for the notification!

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

    I have seen you solution, it is a good idea but it actually run in O(n^5),maybe there's some test can make it TLE (the inner running time is (the number of segment contain givn sub-segment)^4. I have optimize it a bit and now it run in O(n^4 logn). check it 3716717 here. Now I think this problem is solved.

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

      It seems that my solution's running time doesn't depend on the actual test case as long as li ≠ lj, ri ≠ rj and li < rj for all i and j. A gap of 110 ms is not big enough, though :)

      Your optimization is nice, thanks! Now the problem is really solved.

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

        I checked WJMZBMR's n^4logn code and i believe that it has precision problem too, though it pass all the test datas.

        Besides, I guess it may require O(n^5) to get the right answer, and so i suggest either enlarge the time limit or reduce the size of n ;)

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

    We discuss for a long time with a setter this problem. So we change the solution to a correct one. All the solutions that passed pretests at the contest failes on the system test as expected. So, this problem doesn't affect on the participants, because the pretests were right.

    My appologize for this situation. And great thanks to tourist for the notice!

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

    Can you write tutorial for this problem?

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

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

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

It seems I solved 303C - Наименьший модуль 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?

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

    Your solution is not brute, cause you calced values s and use them as optimization. Your solution is very close to right solution.

»
12 лет назад, # |
  Проголосовать: нравится 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.

  • »
    »
    12 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

    EDIT : The proof I have post is wrong. See the comment below.

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

      Please correct me if I am wrong, but I am not getting the proof.

      When you say even-odd pairs, does that mean all the evens come from A and all the odds from B. But, we can still get n/2 odd by mixture of ( E,O) And (O,E). Precisely n/4 (E,O) and n/4 (O,E). And same applies for getting n/2 evens. In essence this points that we can still gets the even-odd configuration.

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

        You are right. Sorry for having post a wrong proof.

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

          No problem at all. Actually, this is way I was trying to prove that any configuration possible not for even n.

          I just got proved that if n is even and if it is not divisible by 4 then there is no configuration with the above reasoning.

          If you get the proof using the above logic please let me know.

  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +46 Проголосовать: не нравится

    If , then or just , where S = 0 + 1 + ... + n - 1 = n(n - 1) / 2. So, there must be . But when n is even, .

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

      Where S=0+1+2+3+...n-1=n(n-1)/2

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

        Thank you, fixed.

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

          there must S = 0 mod n. But when n is even, S != 0 mod n. I do not understand the above statement. Could you please elaborate more. Thanks

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

            When n is even, S = n * (n — 1) / 2 let n / 2 = p which is smaller than n S = p * (n — 1) Clearly, S in this case is not divisible by n.

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

              But also when n is odd. The sum formula stays the same. or I am getting this wrong ?

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

              Ahh Now i get it. S = n(n-1)/2 this sum is divisible by n because S/n = (n-1)/2.

              Now if n-1 is even then n-1 is divisible by 2. else if n-1 is odd(n is even) the sum is not divislbe by 2. thus not divisible by n.

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

      this is fine, i got the logic, but how to get the sequence as all sequences are not valid. your formula just tell if a valid sequence is possible or not.

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

        for N is even output -1 for N is odd the two permutations like this: 0 1 2 3 4 ... n-1

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

          Why is that? How do we come to this?

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

            I had the same doubt. But I guess it is expected that we try the obvious permutation first and observe that its the required one. When N is odd having the permutation

            0 1 2 3...N-1

            0 1 2 3...N-1

            gives a permutation of required category. While it has been proved above very nicely that for N-->even there won't be one

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

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

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

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

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

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

  • »
    »
    12 лет назад, # ^ |
    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).

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

      Similar solution of mine in Java (3754545) gets TLE. I think time limit is very tight for java solutions. Any thought?

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

        Replacing ArrayLists to Arrays makes it much faster. I got AC. Lesson learned.

        Thanks.

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

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