Автор awoo, история, 14 месяцев назад, По-русски

Привет, Codeforces!

В 24.09.2023 17:35 (Московское время) состоится Educational Codeforces Round 155 (Rated for Div. 2).

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

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

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

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

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

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

Harbour.Space
Полная стипендия для получения степени магистра в области Computer Science и Data Science

Теперь вам доступна cтипендия для получения степени магистра в области Computer Science и Data Science в кампусе Harbour.Space University в Барселоне!

Кратко о стипендии:

  • Полностью финансируемая стипендия (29,900 €/год) для получения степени магистра в области Data Science или Computer Science в течение двух лет
  • Кандидаты, успешно сдавшие экзамены, станут частью "резерва талантов" Университета и будут представлены компаниям-спонсорам. В случае, если кандидат выбирается в программу Work&Study от нашего отраслевого партнера, студент начинает стажировку с обязательством изучить 3 часа/день и работать 4 часа/день

Пожалуйста, обратите внимание, что кандидаты, прошедшие отбор, должны будут заплатить невозмещаемый вступительный взнос в размере 85 евро за обучение в Harbour.Space University.

Обязательства кандидата:

За год обучения вы завершите 15 модулей (длительность каждого 3 недели). Ежедневная учебная нагрузка составляет 3 часа, плюс домашнее задание, которое нужно выполнить в свободное время.

Требования к кандидату:

  • Степень бакалавра в области математики, статистики, информатики или аналогичных областях
  • Владение английским языком
  • Расширенные знания и опыт в Python, SQL, Spark/Scala и bash
  • Опыт работы с технологиями больших данных: Spark, HDFS, Kafka и т.д.
  • Практический опыт работы с технологиями Data Science: конструирование признаков,
  • Уверенное знание ML
  • Большой опыт разработки программного обеспечения
  • Способность решать проблемы
Подать заявку →

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

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

»
14 месяцев назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится
:(
»
14 месяцев назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Hope everyone success! ~

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

i'm so excited to join my first educational Round wish me Luck Guys

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

sunday cf rounds (●'◡'●)

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

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

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

      Codeforces >>>>> University Exams

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

      Literally, I also have an exam, but on my priority list, CF is higher than all other things :)

      But I want to overcome, why I am not green yet :)

      If anyone has any suggestions please feel free to give them to me, I will focus on them during my practice.

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

Contest week <3

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

I'm so excited to join this educational Round. Codeforces has been an instrumental platform for honing our coding skills and tackling intriguing algorithmic challenges. Among its diverse range of contests, the educational rounds stand out as a golden opportunity for learners and enthusiasts to delve into the depths of algorithms, data structures, and problem-solving techniques.

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

Wish everyone successfully take part of this round!

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

CM Time?

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

Not once did I get a good score in EDU :(

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

Hi, is it me or is problem 1821E opening in a PDF? Last time I checked, it was opening normally. Problems D and F in the same contest also open normally. Same thing with 1741F. Did something change?

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

I've have just started giving contests and my rating is around 600. Should I take part in this ? anyone ?

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

Hope I can learn something new from this round, good luck everyone ^^ (do not downvote me pls??)

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

3 contests in 3 consecutive days, Amazing!

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

I'm used to losing my rating in the edu round, come on, there's nothing to be afraid of anymore.(`□′)╯┴┴ ┴—┴

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

$$$998244353$$$-forces.

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

Another horribly written Edu round.

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

Thanks for nice problems. Enjoyed solving D. Good one.

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

D was pretty good, idk how this many people solved it

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

D was pretty good, idk how this many people solved it

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

Maybe good problems, but with trash samples.

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

    You didn't submit solutions to any of the problems, so I'm not sure how you've convinced yourself that the sample tests were poorly constructed. Did you compete on an alternate account?

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

      Yeah I use alt because 'rated' gives me more pressure.

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

        Using alternate accounts is not allowed (I had one many years ago that ended up being deactivated) and takes rating away from eligible contestants, so I'd suggest competing on your primary account instead.

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

          Can you please explain a little in problem D about why it is sufficient/correct to just focus on calculating the double-sum bit-by-bit ? Like, what is the high level idea to combine these bit-by-bit answers again ? Why are they independent to begin with ?

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

            Why are they independent to begin with ?

            All bits are independent with XOR.

            More formally, for positive integer $$$x$$$, let $$$x_i$$$ represent the $$$i$$$-th bit (0-indexed from right to left). For example if $$$x = 11_{10} = 1101_{2}$$$, $$$x_0 = 1$$$, $$$x_1 = 0$$$, $$$x_2 = 1$$$, $$$x_3 = 1$$$, $$$x_4 = 0$$$ and so on.

            Now $$$x \oplus y = (x_0 \oplus y_0) \cdot 2^0 + (x_1 \oplus y_1) \cdot 2^1 + (x_2 \oplus y_2) \cdot 2^2 + \dots$$$

            and $$$k \cdot (x \oplus y) = k \cdot ((x_0 \oplus y_0) \cdot 2^0 + (x_1 \oplus y_1) \cdot 2^1 + (x_2 \oplus y_2) \cdot 2^2 + \dots)$$$

            $$$ = k \cdot (x_0 \oplus y_0) \cdot 2^0 + k \cdot (x_1 \oplus y_1) \cdot 2^1 + k \cdot (x_2 \oplus y_2) \cdot 2^2 + \dots$$$

            which means that we can calculate each bit independently. This also applies for XOR of multiple integers (instead of two).

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

            because a*b = sum(a * bit) for each set bit in b

            e.g. if a is 10110 and b is 10101 (set bits 0, 2, 4), then a*b = 10110 << 0 + 10110 << 2 + 10110 << 4

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

Passed D but failed to debug C T_T

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

What is the 4th test case of problem E?

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

    you probably check if we can use 2 colours incorrectly: my mistake was that I forgot we can paint the edges from node 1 in both of two colours, not just one

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

Why E WA test 4??

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

How to solve D

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

    Consider bit i; Create new array b where b[j] is whether ith bit is set or not. Now, you only need to consider subarray which only have odd number 1s.

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

The logic for problem B? Thanks in advance.

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

Had the correct solution for B, but spent literally an hour on a "wrong" answer because I used 0 instead of 0ll. RIP.

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

what is the approach for D ?

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

    you can calculate contribution from individual bits

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

      could explain how you could the transitions for the dp required, I understood that converting the whole array into binary array for every bit makes it much easier, but could not proceed from there

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

        let's calculate the prefix sum of the binary array. Now, we can traverse over $$$r$$$. For the contribution of a given $$$r$$$, if pref[r]=odd, then it will contribute for all $$$l<=r$$$, such that pref[l] is even you can maintain the sum of such l and the number of such l. similar for pref[r]=even

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

        look at 225001296 which has multiple solutions for numbers and for individual bits

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

I hate C!!!!!!!!!

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

    skill issue(applies to me as well). gotta work on combinatorics seriously.

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

D was just a modified version of an existing problem with just a few changes needed while implementing it.

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

what was test 4 of E

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

Anyone else got wrong ans on test case 2 for C?

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

    +1. No idea why. Should skip it earlier.

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

      Oh I see why mine failed. The deletion order can be shuffled across blocks. The sample doesn't have multiple blocks(continuous 1s or 0s).

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

    Yes, I get through this with testcase

    1
    1100
    

    Must be 2 8 (because there is (1 2), (1 3), (2, 2), (2, 3), (3, 1), (3, 2), (4, 1), (4, 2))

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

      what will be the ans for this test case 000111000 explain a little why if you can.

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

        Let's split the string into (maximal) contiguous blocks of equal bits: 000, 111 and 000. From each block, we need to remove everything but a single bit. Since the blocks have $$$3 + 3 + 3$$$ bits, we need to remove $$$(3 - 1) + (3 - 1) + (3 - 1) = 2 + 2 + 2 = 6$$$ bits.

        Let's first consider how many different sets of bits we can choose to remove (we'll look at removal order later). From each block we choose any one of the bits to be not removed and each one of these corresponds to a single set we can choose to remove. Thus, for a block of size $$$k$$$ there are exactly $$$k$$$ different sets of removed bits (in combinatorics terms, this is actually $$$\binom{k}{k-1}$$$). Since our blocks have sizes $$$3$$$, $$$3$$$ and $$$3$$$ and these sets can be chosen independently for each block, we have $$$3 \cdot 3 \cdot 3 = 27$$$ different sets of bits we can remove in total.

        For each of these sets, we chose $$$6$$$ bits to be removed. There are $$$6! = 720$$$ orders to remove $$$6$$$ elements. Thus, there are $$$27 \cdot 720 = 19\,440$$$ removal sequences in total.

        Thus, the answer is 6 19440.

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

      I think 8 ways to do the operations is (1 3),(3 1),(1 4),(4 1),(2 3),(3 2),(2 4),(4 2)

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

        depends on the view. the task itself states that the characters are deleted and thus the id of all succeding characters decrements with every deletion.

        You seem to not change the ids. Turns out that its not important how to view this aspect as the decrementing won't reduce the number of sequences (at least i think so). And i also think that decrementing the ids is just confusing ;)

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

C seemed pretty easy at first but after getting 3 WA and getting AC finally I realized that I was right

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

What's wrong with #224889872:

    int suma=0,sumb=0;
    for (int i=0;i<n;i++) {
        cin >> a[i];
        suma+=a[i];
    }
    for (int i=0;i<n;i++) {
        cin >> b[i];
        sumb+=b[i];
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    cout << min(n*a[0]+sumb,n*b[0]+suma) << endl;
}
return 0;

}

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

    Integer overflow.

    Input:
    1
    2
    1000000000 1000000000
    1000000000 1000000000
    
    Correct Output:
    4000000000
    
    Your Output:
    -294967296
    
    • »
      »
      »
      14 месяцев назад, # ^ |
      Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you. Changed to long long int, but still does not work:


      #define ll long long int int main(){ ll t; cin>>t; while(t--){ ll n; cin >> n; vector<ll> a(n),b(n); int suma=0,sumb=0; for (ll i=0;i<n;i++) { cin >> a[i]; suma+=a[i]; } for (ll i=0;i<n;i++) { cin >> b[i]; sumb+=b[i]; } sort(a.begin(),a.end()); sort(b.begin(),b.end()); cout << min(n*a[0]+sumb,n*b[0]+suma) << endl; } return 0; }
      • »
        »
        »
        »
        14 месяцев назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится
        Input:
        1
        3
        1000000000 1000000000 1000000000
        1000000000 1000000000 1000000000
        
        Correct Output:
        6000000000
        
        Your Output:
        1705032704
        

        You still have int suma and int sumb which will overflow.

        Also, if you want to paste code into comments, add ~~~~~ on an empty line before and after the code for better formatting.

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

          Many thanks!

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

            So I got two questions wrong just because of that. Gosh! How many points is that going to cost me.

            Could have had 3 correct solutions, instead have only one due to stupid int instead of ll.

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

    you're having an integer overflow. Use 64bit long, and i think you should pass. I made the same mistake in the contest! :(

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

Sucks to have had the answer to problem E but failed because my outputs didnt flush properly :( edit, nvm test 4 was a coutnerexample

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

Maybe there are too many details in E :(

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

Any hint on problem F? I did a naive sqrt solution and that TLE'd, Im guessing there's some sort of heuristic involved in cutting some possibilities away?

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

E is bad

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

    for node 2 it will be ambigious

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

    In the second sample, if you color it this way consider the judge putting the chip on node 2. You will answer "1", and the judge will get to pick on which edge colored 1 the chip will move to, so worst case, it will go to node 3.

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

i gonna say one thing C test 2

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

Link to the streaming of today's contest solutions anyone?

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

why can't u spare 1024MB for F QAQ.I was suffering with my solution with a memory complexity of $$$O(n\sqrt {n})$$$

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

I think E is not good, it makes us crazy. My classmates is shouting now.

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

A: If e[i]>=e[1], in order to keep the 1st player to win, we need to set w>=s[i]+1. Therefore, we need to set w=max(i:i>1, e[i]>=e[1])(s[i]+1), and if w>s[1] this value is invalid.

B: We need to choose the cell with minimum cost from every column or from every row. If we choose for rows, the answer is sum(a[i])+n*min(b[i]). If we choose for columns, the answer is sum(b[i])+n*min(a[i]).

C: For each maximal substring with same character of length L, we need to do L-1 operations. So the minimum number of operations is sum(L-1). For each substring we have L choices of the remaining char, and after choosing remaining elements, we have (sum(L-1))! ways to remove other chars. So the answer is prod(L)*(sum(L-1))!.

D: We can calculate the contribution from each bit separately, and now assume a[i]=0 or 1. Therefore, If we let sum[i]=a[1]^a[2]^...^a[i], the answer will be sum(0<=L<R<=n,sum[L]!=sum[R])(R-L), we can get it by simple dp.

E: The maximum number of k is 3. Proof: if we let color[i]=depth[i]%3+1, then for each node, the color of edge to the parent is different from all edges to the childs, and we can identify them by (color[edge to parent]+1)%3=color[edge to child]. Therefore, we only need to check if k<=2. First k==1 is equivalent to parent[i]=1, 2<=i<=n. Otherwise, we can observe that the color of edge to parent must be different from edge to childs, so we have color[parent[i]]=3-color[i] if i>=2. So we can do bipartite coloring for the tree (except node 1), and for i where deg[i]!=2, we can identify the edge to parent (since the count of color[i] will be 1, and the count of 3-color[i] will not be 1). But for i where deg[i]==2, we can't identify edges up and down by just count of colors. So we need to let color[i] be the same for all deg[i]==2. Therefore, we can assume color[i]=1 for them, and find a valid bipartite coloring for each subtree of node 1. If we find someone, we have k<=2.

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

On E, assigning random values to the children of the root enough times passes tests. if anyone wants to hack, should be pretty easy: https://codeforces.me/contest/1879/submission/224976624

upd: hacked

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

There are so many resources about the solution for D on the internet (for example). I doubt if there were any cheaters.

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

    But how do you incorporate the multiplication with length of each of the subarray?

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

      So the answer for the question will be $$$\sum \text{sum of length of subarray} \times 2^i$$$.

      Hint: In the first loop, besides counting the number of indexes such that the numbers of 1s in a[1] to a[i] is odd, you also add have to separately the value of indexes together. This will make calculations in the second loop possible.

      In fact, these type of sum multiply by length often appears in competitive programming, so for many people, coming up with the solution for this question after reading the online examples is not hard.

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

    It is permitted to use code written before the contest. This error is on the organizers who somehow didn't know 99% of the problem is on GFG.

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

What I did wrong in third problem please anyone explain I have done this: first calculated factorial till 2e5 then for each consecutive characters that are same counted them and taken factorial for the same value counted and multiplied this value to original ans which i initialised by 1. Here is the code

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

    you should multiply ans with length of each consecutive characters that are same >1 e.x what's your ans for 1100? it should be 8

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

    for the second part of problem you have to consider

    ans = factorial[n - number of partitions] * product of length of all the partitions
    

    instead of

    for each partition : 
         ans *= factorial[length of partition]
    

    even I did same mistake :(

    224975617

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

      do you know the reason behind doing that?

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

        total positions we have to remove is

        k = n - number of partitions,

        initially ans = 1

        first we have to select any one out of k positions to remove so,

        ans *= k and k reduces by one position so k -= 1

        next we have to select any one out k — 1 postions to remove so,

        ans *= (k - 1) and again k -= 1

        and so on

        so finally we have ans = factorial[k]

        for each partition, suppose of length l and we have to select l — 1 positions out of l positions, and it is l itself. Now we take product of each of these l's and multiply with our final answer.

        ans *= product of length of all the partitions

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

        For each chunk of sequential 0s/1s length N, we need to keep exactly one 0/1, there are N possible ways to do that. By multiplying all chunk lengths, we get the total amount of possible valid end results. Finally, if the total operation count is M, there are M! possible ways to reach each end result.

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

editorial when

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

bruh, wrong answer on test 5 of D because i forgot to mod 998244353 for the n = 1 case...

;-;

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

problem E is very hard (to me) but very fun!
and the trick 'calc bitwise' is useful on D
overall, i felt well.

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

Can someone explain the solution to c? my combinatorics are pretty bad

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

    For every section of ones or zeros which have length L >= 2 you have to remove L — 1 from L, leaving only one bit in that section. So there is C(L, L-1) = L ways to choose different subset of size L-1. Multiply that from every section.

    Then multiply it by fac[r] when r = count of bits we need to remove (permutes it)

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

Why in C the answer is $$$moves! \cdot \prod l$$$ and not something like $$$segments! \cdot \prod l!$$$, where $$$l$$$ — lengths of segments of consecutive repeating characters, and $$$segments$$$ — count of segments with length more than one that contain the same repeating character?

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

    consider each segment as s1, s2 .. sk. (These denotes lengths ) . now among s1 of the ones ( or zeros ) we will select s1 — 1 of them . we can fix in advance which to use . so it will be s1 C (s1 — 1) * s2 C (s2 — 1) * .. * (answer)! . where answer is number of them which we are removing . and this becomes = s1 * s2 * .. (answer)!. Basically for each indices among s1, s2 ..sk we fix , it will contribute answer! (or moves! , as you say ). and number of such selections is s1 C (s1 — 1) * .. sk C (sk — 1) .

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

      What still confuses me is that even though we can fix the characters that will remain (and for each segment there are $$$s_i$$$ ways to do that), since we are counting all permutations where order matters we can also calculate a way to pick $$$s_i - 1$$$ indices from $$$s_i$$$, which is nPr and is equal to $$$s_i!$$$. Still can't see why this approach is incorrect.

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

        once you fix what to remove they are = answer( or moves ) in total . So you just have to arrange these. Don't know why you are arranging amomg segments.

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

          Yeah, I get it now: we are forced to remove $$$s_i - 1$$$ elements from each segment anyway, so two operations would only differ by the remaining characters, therefore if order doesn't matter the total amount of different operations possible is $$$\prod s_i$$$

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

Can someone tell why 224965252 gives WA for problem D?

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

Anyone else got hacked by misunderstanding problem A, thought you must strictly greater than the weight to lift it?

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

About the problem E , I noticed a motivation when working on it: black and white coloring may not be correct, as the first point's son can have different colors. It seems that some people are just WA4.

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

About the problem E , I noticed a motivation when working on it: black and white coloring may not be correct, as the first point's son can have different colors. It seems that some people are just WA4.

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

In contrast to what others have posted, I'm glad the samples for E weren't stronger and I think excluding test 4 from samples made the contest much better. This forced contestants to actually think through the patterns for when using two colors is possible, rather than just guessing the right solution from the sample cases. Kudos to the authors!

On the other hand, I think the time limit for F should have been longer, assuming the intended complexity was $$$O(n \sqrt{n})$$$, to prevent constant factor TLEs. However, I would personally support a smaller memory limit (say, 256MB) to more clearly communicate that $$$O(n \sqrt{n})$$$ memory solutions should be rejected.

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

    Update: Turns out there's an $$$O(n \log n)$$$ solution I missed in contest. That being the case, it seems better to try to cut $$$O(n \sqrt{n})$$$ by setting a lower time limit: for example, I could imagine setting $$$n \le 10^6$$$ and not multitesting, with a time limit of $$$1$$$ second. The $$$n \log n$$$ solution seems significantly nicer and more instructive, so if I was preparing this problem I would probably try to cut $$$O(n \sqrt{n})$$$, but either way I think it's better to make sure $$$O(n \sqrt{n})$$$ clearly passes or clearly fails.

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

The questions are a little classic. I think C, D and E are simpler than usual.

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

Why my E received 1 but wa on 4?

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

good contest

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

So many successful hacks

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

    seems like author didn't put much effort for making testcases in 1st problem.

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

I don't get E statement: "if there are multiple edges with that color incident to the current vertex, the jury gets to choose one of them". If I got to pick the right color i.e. leading to the root then jury is guaranteed to pick the edge that leads to the root?

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

    No, the problem makes no guarantees about the jury's choice. In practice, this means that if you give the jury the option of choosing the wrong edge, your program will fail.

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

So many successful hacks on A :o

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

Please explain how to do D in brief.

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

very bad contest

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

very bad contest

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

This should be hackable, but I'm too lazy to write a testcase against it.
224983900

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

Problem c --> test case 2 --> case 38 Input: 1 10111 Output: 2 8 but the output should be 2 6. Many codes got accepted on same output but my code gave "wrong submission error". please check that. https://codeforces.me/contest/1879/submission/224939377

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

    38th number differs corresponds to 19th tc as each tc outputs 2 numbers. 1100 is the tc for which your code breaks

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

Video Editorial for Problem A,B,C,D

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

How do you get to 36 on problem C test#2#78? (--101111-- 11000 thanks for clearing it up puffinmuffin) My solution gives ans=1(group)!*4! = 24

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

    I was also stuck on the same for a while , but here it is :

    The actual test case you are failing for is : 11000 , as the checker log outputs wrong at 78th number and each test case outputs 2 numbers , so it's failing on test case no #36. :P

    Now coming to the solution of why you may be failing is , note that we must remove ANS (zeros/ones) which is the minimal number of removals we must make. We can arrange these removals in (ANS!) ways. Now all that remains is to find out the number of groups we can make , we just multiply it with (ANS!) to get the total number of possible sequence of moves.

    For this test case : 11000 , we must remove at least one of the two ones , we can pick it in 2c1 ways, this can be further combined with 3c2 ways of removing 2 zeros from 3. This is just multiplication to find the total number of possible groups. So in total we get 2 * 3 = 6 groups. We can rearrange these groups in (ANS!) ways , where ANS = 3 , so (ANS! * 6) = 6*6 = 36. Thus we get the answer.

    Here is my C++ code for it: 225005845

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

225006619 For problem E. I don't know why is the code giving TLE on Test case 5. I have tested on my machine using std::chrono::high_resolution_clock and it takes around 1 ms for the computations before answering queries and all queries are answered in O(1) time. I have applied normal DFS (twice in worst case). The test case is also just 100 nodes. Can't figure out what is wrong here.

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

    There's probably another error in your logic, but your program doesn't exit when you receive -1 to indicate that the answer is wrong. Try changing while (cmd != 1) to while (cmd == 0) and you'll probably get WA instead of TLE.

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

      Yes, u were right. There was error in my logic. Luckily I was able to spot it after your comment. Thanks for the help

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

I'm getting issue while filling for Master's with above link, can anyone help?

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

Actually I think the description of C should be more clearly, I do not think different blocks can be relevant in the first hour...

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

Can anyone please let me know why the first submission is giving WA on test case 6, while the second one passes?

https://codeforces.me/contest/1879/submission/224996088

https://codeforces.me/contest/1879/submission/224996243

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

    maybe the intermediate calculation results exceeding the range of long long,you should module after every multiplication

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

.

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

Problems are so good. In my opinion, the hard part of problem E is the special cases like test case 4.

I have 1 question for E: Why is the constraintso small? I think it can be extend to some larger constraint like 10^5?

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

Became Pupil, Let's Gooooo

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

I want to ask that where is the Editorial? thanks!

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

The D question in this game is very similar to our previous game called the Blue Bridge Cup, and the thinking method used is similar. Please return my rating. The relevant websites are as follows: https://blog.csdn.net/Code92007/article/details/130299859?ops_request_misc=&request_id=&biz_id=102&utm_term=%E8%93%9D%E6%A1%A5%E6%9D%AFA%E7%BB%84%E7%9C%81%E8%B5%9B2023&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-130299859.142^v94^chatsearchT3_1&spm=1018.2226.3001.4187 The corresponding question is question H

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

What is the solution for D

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

I love codeforces