Автор awoo, история, 4 года назад, По-русски

Привет, Codeforces!

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

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

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

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

Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

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

Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:

Внимание, Codeforces,

Harbour.Space University предлагает уникальную возможность учиться в Барселоне для тех, кто заинтересован в присоединении к нашей молодой и динамично развивающейся команде по спортивному программированию. Мы принимаем медалистов и лучших участников IOI, IMO, ICPC, а также участников с рейтингом на Codeforces выше 2000.

Codeforces and Harbour.Space

Harbour.Space имеет единственное ключевое требование: быть замотивированным учиться и/или работать в области спортивного программирования в долгосрочной перспективе. Даже если вы уже исчерпали все свои попытки участия в ICPC, вам все равно рады.

Присоединяйтесь к нам, чтобы помочь построить комплексную систему подготовки к IOI и ICPC для следующих поколений участников! Мы считаем, что если у вас есть талант и решимость добиться успеха, у вас все получится. Мы хотим помочь вам в этом.

В дополнение к курсам, проводимым некоторыми из ведущих мировых экспертов в своих областях, Harbour.Space предлагает следующие преимущества после принятия на эту стипендию:

  • Полное освобождение от платы за обучение (бакалавр и магистр)
  • Студенческая виза
  • Частное медицинское страхование
  • Ежемесячное пособие*

Codeforces and Harbour.Space

В свою очередь, мы требуем самоотверженности в обучении и самосовершенствовании:

Обучение три часа в день
Непрерывная подготовка к ICPC, если вы все еще имеете право на участие
Стажировка четыре часа в день

Готовы официально подать заявление? Пожалуйста зарегистрируйтесь на нашем сайте, приложите свое самое "свежее" резюме и внесите невозвращаемый сбор за подачу заявления в размере 125 евро. Плата гарантирует, что мы сможем обработать каждое отдельное заявление справедливо и своевременно,а так же поддерживать самые высокие стандарты оценки.

Зарегистрироваться→

Наш процесс приема — это целостный анализ способностей, достижений и потенциала каждого кандидата создать что-то исключительное.

Вы можете выбрать обучение по следующим специальностям:

  1. Компьютерные науки
  2. Наука о данных
  3. Кибербезопасность
  4. Фронтенд разработка

Codeforces and Harbour.Space

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

*Точный размер пособия в течение всего периода обучения зависит от результатов, достигнутых в ходе собеседования, и от общих результатов. Он находится в пределах 500-1500 евро.

Команда Harbour.Space University

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

Место Участник Задач решено Штраф
1 risujiroh 7 233
2 Maksim1744 7 243
3 noimi 7 253
4 fastmath 7 278
5 mango_lassi 7 288

Было сделано 145 успешных и 1221 неудачных взломов.

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

Задача Участник Штраф
A Maksim1744 0:01
B SSRS_ 0:03
C BrunoFMUFC 0:06
D SSRS_ 0:10
E AmShZ 0:08
F SSRS_ 0:51
G Potassium 0:45

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

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

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

In return, we demand dedication to learning and improving yourselves:

— Study three hours per day

— Train continuously for ICPC, if you are still eligible for participation

— Intern four hours per day

Is this a hard and fast rule or can be slack. As the above three activites consumes around 10 hours of day. Where is life?

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

Three contest in a row in consecutive days. This is really awesome! That's why codeforces is best.

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

    So you're going to say the opposite thing when there is no contest in 3 consecutive days?

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

    Actually, while this is generous of CodeForces, I think it would be ideal if contests were spread out a little more evenly. I had prior commitments for the weekend and Monday and will miss 3 contests (that would typically be spread over 2-3 weeks instead of 3 days).

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

      So you're saying that there should be less contests so you compete in more contests? I don't get your point.

      5 contests over 2 weeks is worse than 3 contests over 3 weeks?

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

        Nope, that's not what I'm saying. Rather than have 3 back-to-back contests over a single weekend, and then wait for 10+ days for the next one, it may be better to spread them a little (say over a week) so people who are occupied (over a weekend in this case) don't miss all 3 and have a chance to attend at least 1-2 of them.

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

          Yeah ok but the next contests is in 3 days (a 5-day gap, not 10+) and the one after that is in 2 more days.

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

            It's great that there's some more right around the corner. My suggestion was not to reduce the frequency or number of contests (the more the merrier), but to distribute them in an optimal way.

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

Codeforces rank above 2000.

I think you mean rating, not rank

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

Let's hope the test cases will be strong enough so that less participants will be hacked!!!

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

Do you do dynamic programming in the dynamic competitive programming team?

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

hope I remain expert after the contest :(

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

A humble request, just try to recheck the problem statement before uploading the question, for example, the last line of the first problem ( which was rectified later ) was incorrect and made the whole problem statement wrong. I was planning to give the contest but was confused reading the last line and by the time it was rectified over 6000 people had already solved it.

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

    Yes, it was a typo in the notes, but it was fixed just about 5 minutes into the contest. We are sorry for that issue, but sometimes typos happen, and we almost always fix them quickly.

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

How to solve D ?

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

Any idea how to fix WA on test-10 for problem D?

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

How to solve D ?

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

Solved problem G in $$$O(nq)$$$ with auto-vectorization. My worst test works in 4305 ms. Solution 112850106. Hope that it will stay strong during next 12 hours and later.

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

Can someone suggest approach for B and D?

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

    I have not given the contest. But just saw B. I think you can have many possible answers . One possible answer can be like this :

    X = 100...000(a-1 zeroes) Y = 77...7000...00( (b-c+1) 7s & c-1 zeroes).

    This will always give you gcd as 10..00(c-1 zeroes)

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

    For B, I decided to assign a unique prime factor to each of a (2), b (3) and c (7).
    As all the numbers (2, 3, 4) are lesser than 10, there will always be a power of {2, 3 and 7} whose decimal representation is of any given number of decimal digits.
    First of all, I find c by multiplying it with 7 till I get the required number of digits.
    Then, I multiply both a and b by c so that their GCD becomes c.
    Finally, I multiply a and b with their respective prime factors till their representations reach the required number of digits.
    Eg: 2, 2, 1
    Output: 14 (2 * 7), 21 (3 * 7), 7

    My Submission

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

how to solve E?

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

    OEIS

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

      can u plz tell what is OEIS?? i have heard it a lot(at cf itself) in pattern related questions.

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

      Which sequence? How did you get there? I think I'm just really bad at looking on OEIS.

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

        What is OEIS?

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

        I generated the results for 1D patterns like "o", "oo", "ooo" and so on, got an oeis sequence with these numbers, then for each vertical / horizontal contiguous pattern, I added "formula(lengthContiguous)*2^(nbWhites-lengthContiguous)"

        Formula was weird, couldnt understand (I suck at combinatorics), something like "((3*n+1)*2^n-(-1)^n))/9"

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

      logic.?

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

      Whenever there is a combinatorics problem in one dimension, it is often the case it's formula or some related information will be available on OEIS. So find the answer for small terms and search these terms in oeis.org and you will get the formula for it.

      To solve E ,

      Step 1 : Try to reduce a problem to find the answer for only 1 row having N white color cells.

      Step 2 : Write bruteforce and search OEIS.

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

        Actually we can do it without OEIS using contribution technique,but yea for that too we need to come up with the observation on small single rows.... If l is the length of row,c is total white places,so the answer is sum of

        2^(c-2)+2^(c-2)........l-1 times...

        -2^(c-3)-2^(c-3)........l-2 times...

        2^(c-4)+2^(c-4)........l-3 times...

        .........till this converges.
      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 3   Проголосовать: нравится +36 Проголосовать: не нравится

        Step 2 (alternative) by Combinatorics: Problem E 1511E - Colorings and Dominoes

        Let's denote the answer for N contiguous white color cells by f(n) and try to compute for f(n+1).
        
        If (n+1)th character is 'b' then we simply have 'value' as f(n).
        
        If (n+1)th character is 'w' then:
              If nth character is 'b' (.......bw) 
                    Then we have f(n-1)
              If nth character is 'w' (.......ww)
                    Then we can put a domino on these ww. 
                    The number of such cases is 2^(n-1).
                    Also, we need to add f(n-1) for the 'value' of the n-1 elements.
        
        so f(n+1) = f(n) + f(n-1) + 2^(n-1) + f(n-1)
        

        Solution: 112869725

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

    I just used dynamic programming (didn't even know there is such thing as OEIS) to find the sequence of the 1D o's and the equation I found was f(k) = f(k-1) + 2f(k-2)+ 2^(k-2) where f(k) denotes the total sum of the maximum tiling for a length k vertical or horizontal row of o's, and then multiplied that by 2^(nbtotal_white-k)

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

    another way to solve for some n is to iterate on len of the consecutive blocks which have same color this solves for some n in O(N). my submission

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

      Can you please explain your solution?

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

        Ok Ill try to explain in detail, I hope you get the fact that we want to calculate answer for only a string of length N consisting of 'o' only. where 'o' can be red or blue ,so for some arbitrary painting we consider all consecutive segments of red . Now we iterate on length of this segment (you can see solve function in my code). this contributes to floor of (len/2) and we simply count how many times it occurs and add it to the answer. You can see some article on contribution technique which is what I used here.

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

Can someone please help in suggesting an approach for another version of problem C wherein the colours of cards and query colours can be up to 3e5?

Thank you in advance!

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

D is so much harder than E for me. How to solve it?

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

    D could be solved by the pattern like a+ab+ac+b+bc+c for k=3 , and then just repeat it until you reach n . Can you tell how to solve E

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

    first of all given condition is nothing but checking substrings of length two which are repeated how many times.If you are able to observe it then your task is simply to minimize the Cost which can be minimized if two length substrings are repeated minimum times hence try to make all distinct possible two length substrings which wont be repeated if you add it to end your resulting string continue this and make your resulting string

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

    This Video might help you. Video Explanation

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

How to solve E?

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

$$$O(nq)$$$ solution for problem G, using vectorization: 112850202.

A completely straightforward $$$O(nq)$$$: 112827572.

I understand that the my submission might be impossible to fail, but how in the world did the setters allow the second submission to pass?

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

    Second solution is not straightforward $$$O(nq)$$$. It is auto-vectorized with GCC and has same logic as your. See assembly here. Click on cycle for and click on "reveal linked code".

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

      Yeah, sorry. When I was writing my code GCC didn't optimize it for some reason.

      Also they have similar worst case performance, it's just that pretests are weak.

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

    I tried several variations of your code and only a few of them passed, you can check my submission history. I guess it's easy to miss that gcc might optimize this particular problem.

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

Worked like half an hour on C with fancy algos, segment tree and things...before noticing that super simple simulation works fine :/

Edit: And needed some time in B to realize that the order of the two output values matters. That felt fairly uncommon for that problem.

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

    How can we do C problem if color of cards is of order 10^5(instead of 50)?

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

    Fairly SImple way to do C.

    cin>>n>>k;
        vector<ll> mp(51,-1),m1(51);
        for(ll i=0;i<n;i++) {
            cin>> a[i];
            if(mp[a[i]]==-1)
                mp[a[i]]=i;
        }
        ll tot=0;
        for(ll i=0;i<k;i++) {
            ll j;
            cin>>j;
            cout<<mp[j]+1<<" ";
            for(ll i=1;i<=50;i++) {
                if(mp[i]!=-1 && mp[i]<mp[j]) {
                    mp[i]++;
                }
            }
            mp[j]=0;
        }
        cout<<endl;
    
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why is my rate in offical the same in unoffical?

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

I resubmitted my problem E but the initial time of submission is shown in the standings. Which will be considered, if both of them pass?

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

Why is my rate in offical the same in unoffical?

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

G O(NQ)

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

Well, Contest was really a good one B and D were really good problems but one thing which I observed is that in previous three contests there were overall three problems which were googleable which is a bit weird on platform like codeforces which is known for its originality.A lot of People copied code of linked list in C problem today which makes it somewhat unfair.

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

I think my D is different from all Please hack it. 112846805

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

in question B the order of output matters , that's wrong , it costed too much

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

    yeah , i got the idea and implemented it. It shows wrong answer i spend approx 10 min to find that order matters.

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

can anyone tell me how to approach A in today's contest?

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

    Just put all the 1st and 3rd type no. in one server and 2nd type no.s in another server

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

14th test for D TLEd me, although on the PC it takes 0.4 sec. How is it even possible?

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

awoo why this 112845193 code is giving TLE in python3.

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

(Problem-B), Can anyone tell me why my code is giving Wrong answer? Thanks. Here's the link to my code https://codeforces.me/contest/1511/submission/112825682 (Test case 228)

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

How to solve problem C ?

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

    You just care about the minimum index for each number from 1 to 50

    Create an array of size 51 (i call it idx), idx[i] = minimum index for i in the input

    when he ask for t, you put idx[t] = 1 but before changing it shift all other elements in array "idx" by 1 in case they were less than idx[t].

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

    if you know stl it will be easy for you

    • at first you need to store your value in deque
    • then for each query find the expected value
    • print it's position
    • erase that that position's value from deque
    • push expected value in the front of the deque

    you are all done ^_^

    you can see my submission here

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

    This Video Explanation Might Help you. Video Explanation

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

Problem C:
Python3 gets accepted, the same code on PyPy3 gets TLE :D
I listened to your advice and submitted PyPy and ended up with egg on my face
https://codeforces.me/contest/1511/submission/112854945
https://codeforces.me/contest/1511/submission/112860623

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

Masters and above are in the official standings for some weird reason.

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

Today's contest https://codeforces.me/contest/1511/submission/112852064 https://codeforces.me/contest/1511/submission/112830325 https://codeforces.me/contest/1511/submission/112812516

Yesterday's contest https://codeforces.me/contest/1513/submission/112706259

This is how k_Rishav bypasses Plagiarism testing. He has done this today and yesterday both, and I am sure he must have done it multiple times before as well. People like k_Rishav are spoiling the sport. I don't understand where would cheating take them in life. They will never get anywhere in life but always remain what they are i.e cheater. He should be banned from the platform as soon as possible.

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

How to solve $$$C$$$ if distinct no of color of cards may be of order $$$O(n)$$$ ?

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

112861635 TLE

112862682 AC

can anybody explain this !! why using LL gives tle in B??

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

    It might be that a>b, then the 32 bit integers somewhere overflow and the loop terminates, but the ll do not overflow.

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

Someone hack my solution for C, it should give RTE verdict

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

i forgot to use fast i/o in problem C. now i'm wondering if i'm gonna get tle

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

How to prove correctness for the approach used in D?

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

    So the cost of the string is the sum over $$${occ[ij] \choose 2}$$$ where $$$i$$$ and $$$j$$$ are characters from $$$a$$$ to $$$z$$$ and $$$occ[t]$$$ is the number of substring $$$t$$$ in the given string $$$s$$$.

    You can prove that if $$$x \geq y+2 $$$ then $$${x \choose 2} + {y \choose 2}$$$ is greater than $$${x -1 \choose 2}+{y+1 \choose 2}$$$. Then consider an optimal string. The difference in the occurrence of the maximum and minimum should not exceed $$$1$$$. With this information and the value of $$$n$$$, we can uniquely determine the maximum and the minimum number of occurrence over all substrings. This paves way for a simple cyclic construction.

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

      I understand that we want to spread occurrences of each of the k * k substrings as evenly as possible, in that case, the string of maximum and minimum occurence will differ at max by 1. But how to construct it? Some answers said that we can take an Euler tour over the complete graph, but I don't see why it works? Can you explain that?

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

        oh the construction is pretty simple. No need for euler tour. Let's say consider first f letters. You can consider this pattern:

        faabacadaeafbbcbdbebfccdcecfddefeef

        you can cyclically iterate through this string, as you know that the difference between the max and min will be not more than 1 at any time, when you cycle through this pattern.

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

Can C be optimised brute forced? I don't see the complexity going beyond O(50*q)

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

I tried to hack my solution on problem D using the test case "2000005 26" and it got hacked but same test case was there in pretest as well test case number 36

https://codeforces.me/contest/1511/submission/112856095 (Hacked) https://codeforces.me/contest/1511/submission/112870279 (Accepted)

I resubmitted my solution it got accepted can anyone explain to me why? thanks in advance

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

    MikeMirzayanov please look into this .. My code is hacked by a test case that was already there in pre-tests as well and same code if I submit now is giving AC verdict :(

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

Problem D, you can search the zero-cost string by testing if the current chosen letter will make an existing pair using set(notice that you also do not want to make the next position no choice, so check if the next pair is possible). 112873007

This string is $$$k*k+1$$$ long and costs 0. If $$$n>(k*k+1)$$$, we make it repeat. The reason is that every two repeated zero-cost string has exactly $$$k*k$$$ cost(every adjoint two letters have a collision). Also, observe that the zero-cost string starts with $$$aa$$$ ends with $$$a$$$, we do not want $$$aaa$$$ since it results in more appearances of pair $$$aa$$$, so we delete the last $$$a$$$ of the zero-cost string.

However, I forgot the deletion during the contest. Not clever :<

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

Why people are getting tle in problem C?

is it because we use map?

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

submission (Hacked)

submission (Accepted)

I resubmitted my hacked solution and it got accepted! Please have a look!

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

    Your Accepted solution can be hacked again. All submissions will be rejudged after the open hacking phase is finished.

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

    Now it's hacked :)

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

      see my submission it got hacked by a test case that was there in pretests

      200000 26

      https://codeforces.me/contest/1511/submission/112856095

      do you know whats the reason for this? and now when I again doing it is giving unsuccessful hack

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

        Sometimes you notice that if you resubmit your code it runs in different speed, This thing from CodeForces itself sometimes it differ in a little milliseconds

        So always try to keep at least 100ms (depends on the problem) between your code run time and the time limit

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

          But i am again trying to hack my solution with samr test case it is giving unsuccessful hack. I want to know are hacked submission also rejudged during final system testing. Is there any chance that verdict will change to accepted from hacked because its running within time limits specified

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

I couldn't prove/hack my solution for D, tried to make distribution uniform, maintained a $$$next[$$$ $$$]$$$ char array of size $$$k$$$ where $$$next[c] = c$$$ initially, started with $$$'a'$$$ and appended $$$next[prev$$$_$$$char]$$$ char and incremented it cyclically. For $$$n = 10, k = 3$$$ the resulting string is $$$'aabbccacba'$$$. Did anyone try this approach and proved it?

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

https://codeforces.me/contest/1511/submission/112834165 failed on 7 https://codeforces.me/contest/1511/submission/112843558 failed on 13

Could someone help me to explain what's wrong with these approaches for question D?

Just using greedy to get the next digits that have the lowest frequency.

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

Why the brute force can pass G?

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

My $$$O(1)$$$ solution for B. Felt weird but works.

First i take $$$z$$$ as $$$10^{c-1}$$$ . Now $$$z$$$ has $$$c$$$ digits. I want add $$$a-c$$$ digits for $$$x$$$ and $$$b-c$$$ digits for $$$y$$$. To keep $$$z$$$ as a factor i have to achieve this by a multiplication of sum number (with $$$a-c+1$$$ digits and $$$b-c+1$$$ digits). But to keep $$$z$$$ as the GCD, two numbers used to multiply for $$$x$$$ and $$$y$$$ must not have common factors. aka coprime. But all prime numbers are coprime. Therefore i just have to find two prime numbers with required lengths. For that i precalculated these two arrays. Having two numbers for each length is sufficient.

int p1[] = {3,11,101,1009,10007,100003,1000003,10000019,100000007,1000000009};
int p2[] = {5,13,103,1013,10009,100019,1000033,10000079,100000037,1000000007};

Now answer can be calculated as,

$$$x=10^{c-1}*p1_{a-c}$$$

$$$y=10^{c-1}*p2_{b-c}$$$

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

    Or you could notice that $$$10^n$$$ and $$$10^m+1$$$ are coprime for all $$$n$$$ and $$$m$$$. So you could do:

    $$$x = 10^{a-1}$$$

    $$$y = (10^{b-c} + 1) \cdot 10^{c-1}$$$

    And the expression for $$$y$$$ simplifies to:

    $$$y = 10^{b-1} + 10^{c-1}$$$

    Which I think is a pretty neat answer!

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

Can anybody tell at which test case my C is hacked? thanks

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

    Your code is slow

    some cases with high constraints and a specific way to arrange the elements will hack it

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

why does this solution pass and no one can hack it? 112850106

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

Where is the Tutorial? : )

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

The system is accusing me of cheating when I didn't cheat. It says that my problem D coincides with some other person's problem D, I think because both of us had the same idea and the implementation code is really short.

My Solution

Other guy's solution

MikeMirzayanov Can you please look into this?

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

For problem C:

Can anybody tell me why these Python3/Pypy3 solutions giving TLE.

But Exact same implementation with C++ giving AC?

Is my implementation is wrong somewhere, or is it a Judge (Or Language) issue?

TIA.

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

    Quit using python if there is no bignum related problem. It is just a slow language.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    1. Both solutions are bad.
    2. C++ solution works because C++ is faster.
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks. I realize this now, it is a bad solution indeed. I should have thought more optimized approach than this.

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

Is there a way to get full testcase 7 of problem C
There is a performance regression in PyPy project and they need it to investigate, here is the link to the issue https://foss.heptapod.net/pypy/pypy/-/issues/3437#note_157645

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

When ratings will get updated??

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

In problem D. Instead of thinking so much complex i have a simple logic...and by using this i got ac.

I though there are limited pairs of two alphabet so after some length whatever we choose this much have occurred previously. and lets say the count of any pair is X. so if any new occurence of that pair will cost x+1; So i have to minimize this X. it is inly possible if we distribute the occurence of pair symmetrically. Means first form all the pair by A then same with B,C,D...Z. until its length becomes N.

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

In problem D. Instead of thinking so much complex i have a simple logic...and by using this i got ac.

I though there are limited pairs of two alphabet so after some length whatever we choose this much have occurred previously. and lets say the count of any pair is X. so if any new occurence of that pair will cost x+1; So i have to minimize this X. it is inly possible if we distribute the occurence of pair symmetrically. Means first form all the pair by A then same with B,C,D...Z. until its length becomes N.

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

Why ratings are not updated yet ??

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

It seems that many O(n^2) solutions pass problem G . Maybe 4e10 "xor" operations is very fast QwQ.

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

Why the title of this contest in the rating graph says the contest is unrated?

Rating Graph

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

waiting for rating change

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

Why the ratings don't change ?

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

why the ratings haven't changed?

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

Where's the beef? Why hasn't my rating changed? I stayed up late to participate in the contest!

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

During contest I misread Problem A Review Site. I thought type 3 person will downvote if there are more upvotes than downvotes, otherwise they will upvote.

Can anyone guide me how I can solve this version of the problem.

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

    I think it would be optimal to send type 1 guy to the first server and types 2 and 3 to second server, and then just loop through the types.

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

      I thought the same but it actually fails for this test case -

      2
      3 3
      

      Your answer would be 1 but correct answer is 2.

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

        As the statement mentioned : "type 3: a reviewer hasn't watched the movie — they look at the current number of upvotes and downvotes of the movie on the server they are in and decide what button to press. If there are more downvotes than upvotes, then a reviewer downvotes the movie. Otherwise, they upvote the movie.", you can easily put all of the people from type 1 and type 3 in server 1 and the rest of them in the second server, So the answer is the number of '1's and '3's in the input array.

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

          Please read the original comment one more time.

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

            In your version of problem you should send the Type 1 person to the first server and Type 2 and Type 3 person to the second person and just keep a track of number of downvotes the second server has and accordingly add on to the upvotes (if number of upvotes<=downvotes and current type is 3, then the upvotes increase, if type is 3 then downvotes increase, else if upvotes > downvotes, then for each type downvotes will increase), I guess this should do it

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

finally after 2000 years rating changed

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

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

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

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

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

As a first AC, you are late AC.