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

Автор awoo, история, 5 лет назад, По-русски

Привет, Codeforces!

В 11.01.2019 17:35 (Московское время) состоится Educational Codeforces Round 58 (рейтинговый для Див. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Григорий vintage_Vlad_Makeev Резников.

Удачи в раунде! Успешных решений!

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

Место Участник Задач решено Штраф
1 krijgertje 7 182
2 dreamoon_love_AA 7 191
3 KrK 7 196
4 palayutm 7 217
5 TadijaSebez 7 217

Поздравляем лучших взломщиков:

Место Участник Число взломов
1 _bacali 457:-133
2 MarcosK 252:-6
3 nikit523 129:-6
4 greencis 139:-29
5 djm03178 68:-3
Было сделано 1967 успешных и 1152 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
A bazsi700 0:00
B sorry_stefdasca_snsdsux 0:04
C bazsi700 0:07
D ngfam 0:17
E Alif01 0:03
F krijgertje 0:48
G RUSH_D_CAT 0:11

UPD: Разбор опубликован

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

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

Uhh, can't wait til BledDest, Roms and vovuh finally get rid of their new year colors!

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

Уже 11 января, почему магия ещё работает??

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

awoo has been problem settler over 50 contest, it's even more than number of contests I've ever participated. Where those problems come from?

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

    All of them are from the other members of our team. I prepared lots of problems, however, I only own like 5 ideas of all those contests. The truth hurts!)

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

      Well, not all of these problems are ours. Sometimes participants send their ideas about problems, and we prepare them. There are also some problems that are taken from training camps and slightly modified (or even not modified); it was a bit common in some earlier rounds, but now we are trying to avoid such problems (it is not always possible, though).

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

      Any way thank you for Educational rounds. ;)

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

    Google)

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

Ctrl A Ctrl C Ctrl V Compile Activated

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

Is PikMike MikeMirzayanov, since PikMike didn't thank him?

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

The worst educational round ever!

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

Так классно давать задачу D, которую сами же давали 7 месяцев назад. Даже условие не изменили толком. https://codeforces.com/contest/990/problem/G

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

    Можешь попробовать отправить решение из разбора, если хочешь.

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

      А я свое по сути старое решение и отправил, я же писал тот раунд. Думаю не один я. Смысл тогда делать этот раунд рейтинговым ? Он показывает уровень скилла ?

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

        У этой задачи есть и другие решения, которые пишутся/модифицируются куда проще центроида.

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

        Если поискать, наверняка можно найти полно задач уровня Div2A-Div2C, которые можно "решить", взяв код какой-нибудь другой задачи уровня Div1C-Div1E и удалив/поменяв его часть. Все раунды с такими задачами должны быть нерейтинговыми?

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

Weak pretests, my solutions passed >:(

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

it's weird if E is that easy :P maybe that's new year gift from santa PikMike or something

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

Almost spent an hour implementing segment trees for E, because I thought "an E-graded problem can't be easier than that, right?". Yes, I'm newer around here.

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

    I though the same but after seeing the number of submissions,figured it was probably easy.

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

    In problem C, I had done sorting of pairs in asscending order and then checking it belongs to which group gives WA on test 3. like this:

    for(int i = 1; i < n; i++){

    if(v[i].fi > v[i-1].sec){
    
                ans[i] = 1-ans[i-1];  // swapping grp from 1 to 0 or 0 to 1.
            }
            else{
                ans[i] = ans[i-1];  //keeping it same.
            }
        }

    can someone tell me the correct approach for it?

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

So how do you solve F if binary search + greedy is too slow?

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

How to solve problem G? I could only figure out that the answer must be less than 30.

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

    This is some of my ideas for problem G (I hope it wasn't totally correct because I did not finish coding it :( ) :

    1, Calculate the prefix sum array fi

    2, Represent each fi as a binary vector.

    3, Calculate the dimension of the vector space spanned by the vectors that I found in Step 2. If the dimension is 0, print out -1, otherwise print that dimension.

    We also need to check if fn is an element of some basis.

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

      check if f[n] is an element of some basis is just checking that f[n] != 0, right?

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

        Yes

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

        Yeah.

        I'm interested in the proof that checking all prefixes is sufficient, though. I couldn't prove it. :/

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

          Let's say you have 3 values

          b[1], b[2], b[3]

          Also, c[1] = b[1], c[2] = b[1] ^ b[2], c[3] = b[1] ^ b[2] ^ b[3]

          Every possible subset of c's correspond to a unique subset of b's (and vice-versa) so it's the same thing if you take the xor of segments or prefix xor until the end of the segments.

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

            Thanks!

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

            Won't finding basis using gaussian elimination take O(32*32*N) time? but it still runs fast, I have just learned about Gaussian elimination so I am curious why it runs fast?! Also , it seems intuitively true that answer will be basis, but how can we prove it?!

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

              32 * N because you can use bitwise operations (xor). If the numbers are all linearly independent, then there's no subset that xors to 0 so this is the necessary and sufficient condition to be a valid set of segments. Also, every number different from 0 can appear in the answer (just start adding it first). The prefix xor stuff I explained above.

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

                If we are asked to give one such division of max number of segments, then we will make division at the positions where we get prefix xor as a new basis element.If ever a segment has xor zero, we need to add some elements from its right or left.. Is it correct..?

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

                  First part is correct. Second part is useless since when you add a 0 it won't be added as new element. The only detail is that you'd need to add elements from right to left to make sure that the last element is in the answer.

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

                  Got it.. Thanks..!!

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

Is it just me? I got TLE in Problem E, this is my solution. https://codeforces.com/contest/1101/submission/48246073

After scratching my head for some minutes, I added

ios_base::sync_with_stdio(false);
cin.tie(NULL);

And voila, it passed.

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

I brainfarted so hard this contest and i am really disappointed of myself... Solved A in 2 minutes then nothing... I didn't know how to solve B even though i think it's really easy (even tried to implement a DP solution) and i thought for one hour and a half that C was asking something else... RIP my rating

F for prayers

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

    F

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

      I literally thought i had to print the number of characters i eliminated.

      Kill me

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

        NO — SUFFEЯ

        UPD: well, we all have blunders, which are especially humiliating if you slip while reading the task spe. I've just had the same experience with A (I misunderstood it two times, hence spent 15 minutes instead of 3 or maybe 5)... so yes, I am SUFFEЯing here with you, haha

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

        ohhh, so that's why, after trying so hard with the B and didn't know wtf is going on, you saved my day m8 :x

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

Does greedy with binary search work for F? I got a TLE on 23rd test.

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

    Binary-search can't pass timelimit!

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

    shuffle the array randomly first

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

      Can you elaborate on which array to shuffle? We need to maintain contiguity in cities right?

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

        The Trucks Array should be shuffled randomly,and while doing binary search on each truck you should maintain the highest fuel size found,if this fuel size is good enough for the current truck, you shouldn't do binary search

        shuffling just increase the chance of getting the highest fuel quickly.

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

awoo https://codeforces.com/contest/1101/submission/48242640 https://codeforces.com/contest/1101/submission/48241968 the only difference is fast input line i dont think thats how you decide the outcome of a question

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

what can be the test case 4 of problem C ?

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

Well, idk if I was tired or whatever, but B seemed really hard to me, maybe one of the hardest B's ever imo.

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

    Think of it simply and greedy, you will figure out that we should find first "[...:" and last ":...]" of the string which satisfy two ':' are different, then just choose all '|' between two ':'.

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

I had to spend more than an hour solving problem C. That is a very annoying type of problem. I finally solved problem C, but Spending too much time is the cause of trouble. I couldn't submit the Accepted code by a few seconds, so I couldn't solve problem E in the competition. :(

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

How to solve C?

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

    I solved it by finding the non intersecting segments in the union of all the given segments. After that just put the first segment in one of the group and all others in the second group.

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

    Sort segments by L. Put segment 0 in group 1 (set t[0] = 1). Also, let r = R[0] (right border of segment 0). Now, for segments 1 to n-1: if L[i] <= r, we must put it in group 1 (t[i] = 1), also r = max(r, R[i]), as we are continuing the group. Otherwise (L[i] > r), put it and all others to its right into group 2.

    Note: for simplicity's sake I wrote t[0], t[1] etc, but since you sort the segments this won't work. There is a simple workaround to this, though.

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

Ugh, I saw that F was solved by almost no one so I only decided to read it 10 minutes before the end of the contest, realized that it was really easy and ACed it 5 minutes after contest... RIP rating

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

That moment when E has more AC than C

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

Can anyone help me understand what i did wrong for question c. what i basically did was a brute force approach,checked if a number(point) is occurring in other segments if not i am marking that index and then printing 2 for other segments and 1 for the marked index. my sol is here

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

    I think you misunderstood the problem.

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

      can you give me any test cases?? The test case for which my code went wrong is not being shown.

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

        The "segments" the problem is referring to contains all integers from l to r. For example, for this case:

        2
        1 3
        2 4
        

        The two segments intersect, therefore the answer should be -1.

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

      Thought about the intersection part and understood my mistake!!!

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

        That's great. But also, you should not expect an O(n^2) solution to pass anyways.

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

          Given the time limit and due to my misunderstanding i tried the O(n^2) approach.i mostly code on codechef and a 2 sec time limit generally implies a brute force will pass..

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

            No. Never does so. It depends on constraints. If n <  = 103 then only it passes on codechef. If constraints are as big as 105 on codechef then O(nlogn) solution may pass.

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

A better version of problem E would be to find the number of bills inside the wallet for each query.

Solution: Click here

Time Complexiy: O(Nlog^2N)

Space Complexity: O(NlogN).

Any better solution?

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

How to solve D?

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

    For each prime p find vertices that p | a[i], and find max path in every component of graph consisting of vertices you found.

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

      Can you please elaborate? After finding the vertices that divide a particular prime what do we do? What is the component that you are talking about?

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

        I mean if you only take the vertices from graph that can be divided by p, graph will get divided into some components, take max path from each component.

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

          Alright I understand the logic thanks a lot!

          Can you still explain how did you implement it? I mean how did you divide the graph into only the components with these vertices.

          After getting the above I'll be able to solve it with DFS

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

      Will it fit in time limit?

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

        There can be only 7 unique primes that divide every number, so it's O(N).

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

        I think so. The sum of all sizes of the graphs will be O(n log n), because each vertex has at most O(log n) prime divisors.

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

Why are there so many problems for which the query is given?

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

C condition is very strenge,i have solved the problem where it is asked to divide the set of segments into two sets such that each set does not have overlaps

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

Why does my submission for C fail in tc1 using g++ 11/17 48256069&& gets AC with clang 48258190 ?

Edit : I figured it out i wrote the fast io thing after doing the first cin

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

Problem D Code Can someone please tell what's wrong in this code?

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

Good contest!

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

awoo MikeMirzayanov заметил, что с телефона не могу посмотреть посылки в таблице результатов. В обычных раундах могу, а в educational cf rounds и вроде тренировках не могу(acm style контесты). Update. Как вставить ссылку на профиль. Через значок кодфорсес -> юзер не то добавляется.upd2. Понял. пробелы надо делать.

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

In Problem C, I first Sort the interval according to x and then y. Then I traversed and check while(arr[i].y >= arr[j].x) j++. I put them into same set.Here is my implementation (Link) why it is giving WA??? can anyone give me by giving a useful test case.

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

What are the prerequisites to solve G? And please can anyone suggest relevant resources for the same?

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

а взломы дают очки?

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

I don't see any issue with the amount of the input data in E. It is totally fine to remind you to use faster i/o operations once in a while. My solution works in 300ms and I set TL for 3s. That is so generous that you can even get AC in Python (if you know how to read data fast there).

There is no difference between getting TL because of slow i/o and because of unoptimal solution. And you shouldn't blame author for failing slow solutions.

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

    Is there any reason for setting that problem as problem E though? There is a fastio trap, but that should not raise the problem difficulty that much.

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

thank for good contest. but why c is difficult than e

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

thanks for good contest .I was surprised to see problem e is easier than b and c.

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

Cheaters Odin- , timo14z On all Problems : D

A: 48219687 , 48218791

B: 48223299 , 48224656

C: 48234891 , 48232754

D: 48239659 , 48241851

E: 48227416 , 48230879

I hope you look into it awoo.

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

How to optimize this solution for F. I used randomization but I have TLE on test 23

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

after doing E got the importance of
ios_base::sync_with_stdio(false);

cin.tie(NULL);

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

What's going on with the hacks on E? Is the hack making the solution TLE because of the slow input?

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

How to solve G

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

please help!!! why my code is showing TLE https://codeforces.com/contest/1101/submission/48260807

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

Do hacks give points??

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

    Not in educational or Div3. But gaining top position in Hackers Table is prestigious.

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

      Besides, if you make more hacks, you can get a higher ranking since others drop.

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

I solved E faster than B.. :/

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

How to solve C?

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

    Sort all the queries wrt left limit li. Then traverse keeping track of the max of right limit ri, let us assume rmax. If u ever get l(i+1) > rmax at ith iteration, u can divide it into two groups.

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

Hi everyone! Could someone help me? I tried to solve problem C, but it gives me TLE and my computer runs the first test case in 31 ms. :( This is my submission.

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

    As there are many test case, try to clean vectors only if they are less than or equal n, not maxn.

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

Here's a spoiler for my 60 hacks on E: As already mentioned above, the amount of input is quite large. Though some solutions using endl or alternating cin and cout still passed, reaching ALMOST 3s.

There was also a test where 499999 queries are '?' queries so it was an 'almost-worst case' for such solutions. But it wasn't 'THE worst' case.

I made a generator where the first query is + 1000000000 1000000000 and the rest 499999 queries are ? 1000000000 1000000000. This input not only consists maximum number of characters possible, but also requires maximum number of characters in the output. Then I just went through every AC submissions with time > 2900ms and it worked for all of the 'slow-I/O' codes.

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

Little overkill I made on problem D .. :) I used Centroid Decomposition!!

https://codeforces.com/contest/1101/submission/48257605

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

Im GENIUS!!! Im hacked all people, who solved problem B on PascalABC... INCLUDE ME..IM SUPER GENIUS...!!

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

haha so glad i skipped this one see the people getting hacked off:))))))))))))))=)))))))))

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

Cheaters (Hacks) Mohammad.H915, NeverSee On problem A:

48264141 48264121 and many others

I hope you look into it awoo.

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

How to solve problem D

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

    for all prime numbers less or equal to n find the graph g that all vertices of it are dividable by n (it may not be connected) and find the longest path on it and then the maximum of these values is the answer. this is of course O(n*logn).

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

      How is complexity O(nlogn)?

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

      I can't figure out why just pick up prime numbers, can you explain me please?

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

        suppose we have the answer it should be a path with gcd more than 1 so all the vertices in the path are dividable by a number(the gcd)though that number is also dividable by some prime numbers. thus all of the vertices are dividable by some prime numbers so picking all prime numbers we can obtain the longest path.

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

    You can solve it using modified dfs.
    How?
    Let us iterate i from 2 to sqrt(200000),
     For each i, lets perform dfs:
      We try to reach as much depth as possible which is divisible by i, from the current root (let's say j);
      Let the top 2 maximum depths reached (using 'j' as root) be f and s;
      Thus the longest path can possibly be f+s+1 ( starting from one depth, turning at the root and ending in the other depth).
      So we take the maximum out of all of the above mentioned paths for all roots, for all i.

    Also we need to once run the same dfs given above for each i = a[j]; (where a is given value array and 'j' is the current root).
    This will cover the case in which every number is a prime.
    Thus, the final maximum of length of all the paths will give us the answer.
    Complexity: O(n*sqrt(n))
    Check my submission for more clarity.
    UPD: Thaid Thanks for the hack. Was able to find out the error in my method :). Its updated now .

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

      Consider this test:

      3
      1 7207 7207
      1 2
      1 3
      

      I'm sorry for a hack

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

      It can be done in O(N log N + complexity of prime factorizations) if we consider all prime factors among prime factorizations of values of all vertices. We will create a mapping prime factor -> list of vertices that contain this factor in the prime factorization of their value. Now we iterate over the map and for each prime factor we enable these vertices. Next we iterate over these vertices one more time and if the vertex has not been marked as seen for the current prime before we find the diameter in the tree of currently enabled vertices, rooted at this vertex. The answer is the maximum diameter of a tree we have found in the end. As each vertex only has a maximum of log N prime factors in its factorization, each node is only visited a maximum of log N times.

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

Codeforces should reduce the time for hacking phase.

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

MarcosK is on fire!!! Hacking people like anything!

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

Anyone else solved G greedily and has absolutely no clue why it works?

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

Why there are a lot of hacking in problem A and B?

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

    For, B: Weak pretests, I think.
    I did a very silly (wrong) assumption that the characters [, ], : and | are always present in the given string. (I didn't notice this part (1≤|s| ). And unfortunately, all the pretests had all these [, ], : and | characters. There was not a single pretest with |s| < 4.

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

    For A: some people submitted a brute force O(n) complexity algorithm and got TLE. Instead O(1) solution was possible

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

Is it possible to solve problem D by rooting the tree at 1?

I am actually clueless. I am wondering if it is possible or not?

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

    it is ... I mean I did that and it got accepted and another clue : think about the prime numbers :)

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

    Usually, for trees problems, if not having any specific requirements, rooting from any vertices will always result in one desired value if your ideas/implementation is correct ;)

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

      Can you describe something more for "any specific requirements".

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

        That one is just a criterion given in statements.

        Like, if the tree is stated to be rooted at 1, and has clear descriptions of its nodes' ascendant-descendant relationship, you have to choose 1 as the root regardless. Otherwise, choosing any vertices as the root doesn't matter.

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

          I meant by asking that under which condition I cannot root my tree to any specific node if not specified in the question.

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

            AFAIK, if the problem statements do not give any details about the specified node to be rooted, you can freely choose your root to start traversing.
            At least that applies to all DFS/BFS-based traverse.

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

SomeOne, please update Ratings.

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

So when can the editorial be released?(And also rating changes?)

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

Why can't rating changes be updated automatically?

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

Why my same solution of B is being accepted now, when it was hacked earlier??

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

Will there be another system test later or it's already finished?

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

how to slove problem C?

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

    sort the segments by L

    iterate over the segments and store the max R . when you find a segment which has L bigger than the current maximum R put it in the other group with all the remaining segments.

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

Where is the rating?

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

Got Problem F Accepted with a small randomization trick + Binary Search.

First of all, I assumed the direct Binary Search would not pass the worst case.

What if we can binary search on each truck and find it's minimum required volume and use that result as low of next truck? Also, I did a check before running the binary search if the previous result can already satisfy the current truck.

A little improvement but now the question arises, would it still pass on some specific type of ordering of the dataset? Surely not and it didn't.

So, I reordered the input order of trucks randomly and ran the same solution which got accepted with pretty fast runtime.

TLE Solution without random ordering

Accepted Solution with random ordering

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

Not using fastio in E causes TLE. I think it should be mentioned in the problem statement to use fastio.

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

    No, it shouldn't.

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

      What should have already happened is system testing. How long more we'll be waiting?

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

      I thought that the TLE verdict is used to imply that your solution does not adhere to the intended time complexity. It doesn't make any sense if the solution adheres to the intended time complexity but still gets TLE because of just fast IO. After all these are algorithmic contests.

      Anyways a learning to always use fast IO on CF! :)

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

        I would be very excited to see competitive programming problems and contests that test only the correctness and complexity of your solution. But, unfortunately, in reality things are just not like that. There are lots of problems where constant optimizations — fast i/o, bit hacks, replacing % with some subtractions/additions in modular arithmetics — really matter. If we don't cover this in our rounds, then participants would not be prepared to use these optimizations on some real contests.

        The reason why we don't mention the requirements on fast i/o in the statements is the same: they are rarely mentioned on official competitions, so participants should be able to determine whether they need to use constant optimizations or not by themselves.

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

          doesnt that defeat the purpose of educationals vs regular rounds

          i mean these are for 'The goal is rather to practice and to educate, than to compete'(as said by MikeMirzayanov), also these are oriented towards second division and newer coders,

          so i think mentioning it in the question would me more motivating for the newer folk rather than them finding out that they had been doing the correct thing from the beginning but just got TLE bcoz of some damned fastio

          btw thanks for replying rationally rather than just some arrogant, "No, it shouldn't."

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

            The education contest was originally designed to make the coder more adapt the regular contest. so through this contest, I think you will definitely pay attention to it later.

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

      Well, may I ask why ? In a comment above, you've mentioned "It is totally fine to remind you to use faster i/o operations once in a while". Surely mentioning it in the problem statement is another way to remind ?

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

        well if using fastio can change the verdict of the exact same code then i think it is necessary to mention that

        because fastio is not a differentiating factor when comparing a person who has the right algo, right code, right implementation... with someone with neither of these

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

          "...fastio is not a differentiating factor...".

          I disagree with such proposition. Usually, fastIO is a mistake of newcomers. That's why, it shows your experience in the same way as knowing standart library, math, data structures and other.

          I can replace "fastIO" with "random bug" in your statement and it will sound the same. And that's because solving the problem is not just having idea, but a complex task, and if you fail at least in one part, you will look the same as "someone with neither of these".

          And final thought, if you've got TLE because of slowIO, it means that your implementation is not right. And you can only blame yourself.

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

            imagine this case you are new to programming, you give this question a try, you get the logic and are able to write the code correctly now you submit it and get TLE, you are confused and think that maybe there is some problem with logic and u think and think but couldnt find aany, you get very frustrated and after the contest you realise that a simple fastio line could have gotten you AC you were right all along from the beginning

            how would you feel, would you be excited that you learned about fastio or angry about some fastio ruining your verdict, would this incident be motivating for you to pursue coding further

            what i suggest something like "fastio recommended" in the question of "educational round" and this new programmer learns about it and as well implements it in the first time and gets his code accepted, wont this be more motivating for him

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

              Frustrating is common feeling, everyone in this community felt it many times, and, if newcomer can't deal with it, then it's his personal problem (moreover, frustrating is caused by his own mistakes).

              What he has to do is to get valuable information from it and preform better in the future.

              Ah, and adding "fastio recommended" is bad idea, since almost nobody will learn the lesson. Instead, more people will complain in the future, when they will have to use their own heads.

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

        Meh, learning doesn't work that way. I believe, learning from your mistakes is the most efficient method of learning.

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

          ya, agreed but this is like purposely digging a ditch for someone to fall so that they be careful the next time

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

            Do you think that 500000 queries were just to mess with slow i/o lovers? It was done to guarantee that none of heavily optimized q2 solutions will pass. You can scroll past the previous rounds to see that people were getting n2 AC for n = 105 and some crazy things like that. These low-level compiler optimizations are still black magic to me, so I better ensure it is impossible.

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

            The input has a clear 3 constant, you should be able to recognize this if you're using a slow read method such as cin/cout. Otherwise just go for the printf/scanf. The large input is a consequence of the required constraints of the problem

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

              imagine this case you are new to programming, you give this question a try, you get the logic and are able to write the code correctly now you submit it and get tle, you are confused and think that maybe there is some problem with logic and u think and think but couldnt find aany, you get very frustated and after the contest you realise that a simple fastio line could have gotten you AC you were right all along from the beginning

              how would you feel, would you be excited that you learned about fastio or angry about some fastio ruining your verdict, would this incident be motivating for you to pursue coding further

              what i suggest something like "fastio recommended" in the question of "educational round" and this new programmer learns about it and as well implements it in the first time and gets his code accepted, wont this be more motivating for him

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

                Seems like a good oportunity to get educated enough about fast io to the point where it's unlikely you'll ever forget again

                The suggestion is okay, it's even present from time to time, but it's way different to say suggestion and, textually, "digging a ditch for someone to fall". No, it isn't wrong or required, you're just triggered.

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

      Maybe is shouldn't but it does. Check it out https://codeforces.com/contest/1101/submission/48266295 https://codeforces.com/contest/1101/submission/48234518 2978 ms and 327. Of course second solution got hacked.

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

when will the rating changes come out?

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

include

include <math.h>

using namespace std; typedef long long ll; int main() { int n,i; cin>>n; int maxx=0,maxy=0; for(i=0;i<n;i++) { char c; cin>>c; //cout<<c<<endl; if(c=='+') { int x,y; cin>>x>>y; if(max(x,y)> max(maxx,maxy)) maxx=max(x,y); if(min(x,y)> min(maxx,maxy)) maxy=min(x,y); } if(c=='?') { int h,w; cin>>h>>w; if((h>=maxx&&w>=maxy)||(h>=maxy&&w>=maxx)) cout<<"YES"<<endl; else cout<<"NO"<<endl; } } return 0; }

This is the code of question E, but TLE at test case 7, can anyone explain why TLE is coming?

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

    just add this line before taking input in main()

    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

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

So I've a miraculous solution for G, which I've no idea how it passed. First, I've misread segments into sets, so I thought the elements order does not matter. Second, I couldn't come up with a solution for that version too, but hey, the contest end is so close, so what do we try to do in these cases? Just try out anything without caring a bit about correctness, i.e. think of some greedy/randomized algorithm. I coded a randomized solution, and to my surprise, it passed!

After the contest while discussing the idea with a friend who maybe thought I'm sort of alien to think of a solution like this, I only thought he was surprised due to the randomized solution, but then I was shocked when he asked me, how even the answer for dividing into contiguous segments is the same as the answer for dividing into sets?

I'm still shocked since then, can anyone help me why is this submission AC?! At least is really the answer for dividing into subarrays the same as dividing into segments? Are they not necessarily but most probably the same? And even so, why is randomized solution getting the correct answer with high probability? To be even more shocking, in the randomized solution I just assumed that the difference between the sizes of the largest and smallest piles is at most 1 xD

Anyway, here's a conclusion: never give up on any problem till the last 20 minutes, for that random stupidness can turn out to be equivalent to ultimate intelligence.

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

    never give up on any problem till the last 10 minutes)))
    original (I think) solution of problem G is just coding gauss algorithm in 2-6 minutes
    so keep thinking and generating ideas such as another interpretation of problem at any time of the contest

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

i think system testing will be too slow!

there are about 600!!! tests for problem B

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

500 tests for problem B

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

Can anyone tell me when will the rating be add to my profile? The contest and open hacking have ended, yet the rating has not been added in my profile.

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

    This is because final rating is calculated after system testing... and after that it is added to your profile. So wait for system testing to end. After that it won't take much time

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

When tester got no chill! :p

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

Longest system testing I've ever seen. 600 tests in B lol.

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

Why can't I see all of my submitted codes on My Submission tab

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

Есть кто нибудь у кого B упала на 580+ тесте? =)

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

Question B has highest number of hacks I have seen till date. Thus it also has 600 test cases XD

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

I got TLE on C because i didn't use Fast IO :(( These tests are not ok!

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

    Same bro. I feel your pain! The bigger problem is when you don't know what to do after that TLE :<

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

What is hack for B?

I can't understand why some greedy solutions get WA. All solutions a kind of let's find the first "[" and the first ": ". Afterwards let's find the last "]" and the last ": " before the last "]". And finally let's calculate number of "|" between ": ". The answer is the number of "|" + 4

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

So sad, the magic already gone :(. I missed my chance to hack "Legendary Grandmaster" :((

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

I don't know how bad luck this is.

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

Post the editorial please.

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

The round of hacks and test cases!

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

With one pass solution, small (500000) constraint and 3 Sec TL why this -https://codeforces.com/contest/1101/submission/48293304) gets TLE without using Fastio.

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

Why this greedy solution for problem G is correct ?This one

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

Hey anyone, can you help me with D? I used a DFS call from current node and the trailing recursion and passed them separate visited arrays, can't get the prime number solution some people are suggesting, any elaborations please? :'(

Here is my code

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

Can somebody find mistake in my code in problem D, please?

https://codeforces.com/contest/1101/submission/48296920

Or can you tell me what is the test 4 in this problem?

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Can someone please explain to me why I got TLE in this submission and when I submitted the same code but after replacing the array of long long "ll ans[200005];" with the array of int "int ans[200005];" in this submission I got Accepted ? It happened to me during the contest and I got hacked on my submission with long long because it got TLE!

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

    Memset works at byte-level, meaning that your memset() now takes twice the time with long long. You shouldn't do this memset here to begin with (with good constraints it would also TLE with int), you should use the fact that the sum of all N is 1e5 and so just zero only the first N elements of ans[] for each testcase.

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

And I thought I was going to be one of the top hackers with 12 hacks. :P

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

About problem E, is a truly fact that in complexity a solution with or without fast i/o has the same complexity, but this is a programming competition where if you take a look is about problems that has a different behaviour in their running time, is not the same the complexity and the running time, is not the same theory and practice. Programming contest is the practice side.

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

How could guys like _bacali hack so many solutions? I mean, 'top-hackers' need to have special scripts to look through anti-patterns in participants solutions, don`t they?

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

    Yeah, that's true, all that I have to do is to prepare a correct solution of the problem, a test generator which can generate small random test cases, a checker using the "testlib.h" which is used to prepare Codeforces's problems checkers and a well-written script which downloads all the correct submitted codes, compile and run them and compare their result with the output of the correct solution, and when the submission fails on some test it has to be submitted automatically. You can find this script on my Github, so anyone can test it by himself. And it's a good way to warm up your room with your pc xD.

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

_bacali(the best hacker) told me that he write a script to hack.I think its a useful way to find some codes are not right while they passed pretests.I think system should use this to add more tests in main test and find the wrong code which passed the pretests. Sorry for my poor English and poor rating.

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

How the ans for second test case in 2 in Problem D...? Can someone show the path that creates distance 2?
shouldn't the path is 1-3 (2,4) ?
Testcase 2:
3
2 3 4
1 3
2 3

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

Can anyone tell me why my submission for B. Accordion is TLE even though it runs in O(n)? https://codeforces.com/contest/1101/submission/48231331