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

Автор gridnevvvit, 11 лет назад, По-русски

Всем привет!

Скоро, 2 ноября, 12:00 MSK, состоится очередной Codeforces Round #209 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса. Обратите внимание на время старта раунда!

Автором задач являюсь я. Большое спасибо Гере Агапову (Gerald) и Лось Илье (IlyaLos) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

UPD1: Распределение баллов будет таким: 500, 1000, 1500, 2500, 2500.

UPD2: Поздравляем победителей!

  1. cptbtptp
  2. FancyCoder
  3. Oyk
  4. E.B.
  5. orzkbc

UPD3: Разбор задач

Удачи!

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

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

wish all participants a very happy Diwali! :)

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

I don't know in other countries how is this time for participants, but in our country in this time all of students went to school , and they can't participate in this contest .

Is there a specific reason to take this round in this time ?

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

Весь раунд промучился над С, так и не решил, но мне все равно понравилось))

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

Восхитительное системное тестирование! Всегда бы так!

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

Fastest system testing ever!!!

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

Fastest system test?!

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

That was the fastest system testing I've ever seen! Great Job! :D

Waiting for updated ratings. :)

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

Когда будет разбор?

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

    Я надеюсь, что завтра с утра будет финальная его версия.

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

woah! this is certainly the fastest system testing ever on Codeforces!!!

EDIT-1: why are the testcases still not available for viewing though?

EDIT-2: now able to view the testcases. thanks!

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

Если системное тестирование прошло так быстро, то почему все еще нельзя смотреть тесты?

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

Как решалась B?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    int n, m, d=1; 
    cin >> n >> m;
    int i;
    
    for (i = 0; i < 2*m; i += 2)
    {
        cout << d << ' ' << d+1 << ' ';
        d += 2;
    }
    
    for (i; i < 2*n; i += 2)
    {
        cout << d + 1 << ' ' << d << ' ';
        d += 2;
    }
    
  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Ставишь числа в виде 2 1 4 3 6 5 ... И потом K раз меняешь местами числа в соседних парах, например, для k=2 ответом будет: 1 2 3 4 6 5 ...

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

    Возьмем перестановку n, n-1, ..., 1. Для неё значение рассматриваемой разности равно нулю. Если менять местами элементы с номерами 2i и 2i — 1, разность будет увеличиваться на 2 с каждой заменой. Таким образом можно сделать k замен, и разность станет равной 2k.

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

      Распишем сумму последовательность 2 1 4 3 6 5 ... и заметим, что она ноль. На каждый обмен местами результат изменится на 2 => для изменения на 2k нужно сделать k замен.

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

        Я случайно отправил копию =( Хорошие задачи! Спасибо автору.

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

    А можно по-другому:

    На первое место поставить число 1, на второе K+1, остальные числа отсортировать по убыванию. Если аккуратно раскрыть скобочки, видно что отсортированная часть сократится.

    Мой код: http://mirror.codeforces.com/contest/359/submission/4963564

    Upd. Отдельно рассмотреть случай K = 0. Тогда просто отсортируем по убыванию.

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

    Можно было сразу сливать перестановку в вывод:


    for (int i = 2*k+1; i > 0; i--) { cout<<i<<" "; } for (int i = 2*k+2; i <= 2*n; i++) { cout<<i<<" "; }

    Если на бумажке проверить аккуратно, то такая последовательность всегда проходит

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

Great problem set.. Thanks to the author and testers!!!

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

My skipped solution[submission:4965469] turn out to be accepted when I submit it after the contestsubmission:4967854, testdata for problem D may be too weak.

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

Thanks for the fast systest! :)

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

any solution for C ?

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

can anybody tell me what's wrong with my submission 4967509 for problem C? thanks!

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

Как решалась D?

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

    Заметим, что каждое число может принадлежать только одному искомому интервалу [l..r]. Далее будем рассматривать каждое из чисел, начиная с наименьших, и искать максимальный интервал, содержащий данное число. Если число уже было отнесену к какому-нибудь интервалу, то его больше рассматривать не нужно, поэтому имеет решение за O(N).

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

      "Каждое число может принадлежать только одному искомому интервалу"
      Не всегда: 3 3 3 6 2 2.
      Поэтому решение нужно доработать. В частности, мое решение 4995186 очень похоже, только для каждого числа кэшируются все позиции, на которых оно участвовало.

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

systest is amazingly fast, but the rating update is slow :(

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

look at this submissions:

4966994 4966935 4966174

i think they are same people!

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

I am looking forward to updating of my ranking...

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

About problem C, we know that if x1 is large enough and a, m is smaller than N(=1e9+7), and x1 ≡ a (mod N) is satisfied, then gcd(x1,m) mod N = gcd(x1 mod N, m) = gcd(a,m) is good.

But if x1, x2 is large enough and a, b is smaller than N, and x1 ≡ a (mod N), x2 ≡ b (mod N) is satisfied, how to solve gcd(x1,x2) mod N ?

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

Where is the tutorial?

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

Почему в задаче B не проходит такое решение. вот псевдокод:

for i = 2n..2+k вывод i

for i = 1..1+k вывод i

При тесте 50000 25000 WA система выдает. Хотя всего 100000 различных цифр и разность сумм равна 2k то есть 50000. И по идее это правильно.

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

For Problem B, Did anyone else thought of this solution?

I got this solution after scribbling four pages of my book. But don't know why it is right!

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

    My solution is the same as that. But my coding is ugly...

    BTW, what book is it? It seems quite helpful.

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

    Let me explain my way of looking at it. I will take an example. n = 2, k = 1. Firstly, my permutation should have 2*n = 4 elements. For now, I do not know anything about it so let's say it is:

    a1, a2, a3, a4.

    According to the given formula,

    (|a1-a2| + |a3-a4|)-(|a1-a2 + a3-a4|) = 2*k

    In LHS of the above equation, Let's denote expression inside first parantheses as A1 and second as A2.

    Now, 2*k is always even. It means that there are 'k' terms which are being added to A1, and 'k' terms which are being subtracted in A2. One way of looking at it can be:

    A1 = C+k

    A2 = C-k

    where C is some constant.

    How can I form an expression such that k gets added in A1 and gets subtracted in A2? By reversing exactly k pairs whose absolute difference is 1!

    So, if my sequence was 4 3 2 1.

    A1 = (|4-3| + |2-1|) = 2.

    A2 = (|4-3 + 2-1|) = 2.

    Say I reverse exactly 1 pair, (2, 1) becomes (1, 2).

    New sequence = 4 3 1 2.

    A1 = (|4-3| + |1-2|) = 2.

    A2 = (|4-3 + 1-2|) = 0.

    A1-A2 = 2 = 2*(1) = 2*k!

    One more example, n = 4, k = 2. I will just give the answer. It is based on the explanation above.

    Answer : 8 7 6 5 3 4 1 2.

    Notice that two pairs (2, 1) and (4, 3) have been flipped.

    General solution: Just form a permutation sorted in descending order and flip 'k' pairs as illustrated above.

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

      Sorry for such a long post. Just wanted to be clear in what I wanted to convey)

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

      Hi, Can you please elabroate on

      Now, 2*k is always even. It means that there are 'k' terms which are being added to A1, and 'k' terms which are being subtracted in A2

      Regards, Nitin

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

        One way of achieving a 2*k difference in (A1-A2) is to have 'k' terms of value '1' in A1 which are being added, and the same 'k' terms subtracted in A2.

        Flipping the pairs of numbers helps in doing this.

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

I dont know why my problem C isnt working. Hope the editorial comes in fast. Is there a way to see the entire testcase, I mean when I see the test case on which my soln failed it shows — finite numbers and then "..."

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

Д — чуть ли не первая задача, где автор все-таки заставил юзать sprase table, за что ему отдельное спасибо)

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

what would be the ans for prob C for this test case

2 6 3 3

and why???? please explain me .............

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

    6 is not a prime :) so invalid

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

    even i wasted a lot of time thinking that a factor of x could reduce the denominator and hence would have to be accounted for. then i reread the problem and saw that x must be prime. started coding the solution immediately after that! :)

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

Is tutorial coming?

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

Is O( 2*N (lg N)^2 ) solution passes for problem D??? N=3*10^5 .

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

    Depending on how well written it is, it would be possible for it to pass, but my O(40N) takes 0.35s, so it might just TLE.

    EDIT: Mine is . I forgot about GCD working in . So yeah, it should pass.

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

    i think my solution is O(N * lg n ^ 2) in best form and O(N * lg N ^ 3) in worst form. (but im not sure!) it get accepted in 1300ms. i Think Your Solution will be accept too! here is my solution : 4967080

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

http://mirror.codeforces.com/contest/359/submission/4979724

This is my submission for D. I picked a number and guessed it as my current gcd. then I did a binary search on my pre-computed segment tree. By this i tried to find a L and R for each position i so that gcd(L to R) = arr[i]. I think it takes O((lgN)^2) and the outer loop of N makes the overall complexity O( 2*N (lg N)^2 ). But it is getting TLE on case 10 where N=3*10^5. Is it a problem with my implementation.

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

    That's just what I was talking about above, that a well-written solution would pass. In this case, there's an additional factor of to the complexity, so a segment tree, which has a large constant compared to some other approaches (sparse table for example), can get TLE.

    Seeing as it takes 1.5s on case 9 with N = 2·105, it probably just needs some small optimization to pass.

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

      Thanx a lot Xellos & MiRZA(I don't know how to tag a nick:( )for your gr8 help. Finally Got AC! Same code just replaced the Segment tree portion with sparse Table. Totally new experience for DS beginner like me. Time Limit was 1341 ms, and i am happy with it. Thanx again.

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

        "Tagging a nick": When you write a comment, there's an icon on the top panel (yellow, blue and red stripes). Click on "User" there.

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

        Your Welcome ;)

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

Wow! All problems by one person!