Educational Codeforces Round 155 [Rated for Div. 2]
By awoo, history, 14 months ago, translation, In English

Hello Codeforces!

On Sep/24/2023 17:35 (Moscow time) Educational Codeforces Round 155 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Harbour.Space
FULLY FUNDED SCHOLARSHIPS for Masters in Data Science and Computer Science

Scholarships for Master's students in Computer Science and Data Science are available in Harbour.Space University Barcelona campus!

Scholarship Summary:

  • Fully funded scholarship (29.900 €/year) to study a Master’s degree in Data Science or Computer Science for two years
  • Successful applicants will become part of the University’s “Talent pool” and will be shown to the sponsoring companies. In case the candidate is picked for the Work&Study Program from our industry partner, the student starts an internship with a commitment to study 3 hours/day and work for 4 hour/day

Please note preselected candidates will be requested to pay a non-refundable application fee of 85€ to study at Harbour.Space University.

Candidate’s commitment:

You will complete 15 modules (each three weeks long) in one year. The daily class workload is 3 hours, plus homework to complete in your own time.

Candidate’s requirements:

  • Bachelor's degree in the field of Mathematics, Statistics, Data Science, Computer Science or similar
  • English proficiency
  • Advanced knowledge and experience in Python, SQL, Spark/Scala, and bash
  • Experienced use of Big Data technologies: Spark, HDFS, Kafka, etc.
  • Hands-on experience with Data Science techniques: feature engineering,
  • Strong ML knowledge
  • Strong Software Engineering Background
  • Problem-solving aptitude
Apply here →

UPD: Editorial is out

  • Vote: I like it
  • +245
  • Vote: I do not like it

Comments Comments (162)
| Write comment?
»
14 months ago, # |
  Vote: I like it +46 Vote: I do not like it
:(
→ Reply
»
14 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Hope everyone success! ~

→ Reply
»
14 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it +18 Vote: I do not like it

sunday cf rounds (●'◡'●)

→ Reply
»
14 months ago, # |
  Vote: I like it +32 Vote: I do not like it

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      Codeforces >>>>> University Exams

      → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
»
14 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Contest week <3

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
14 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Wish everyone successfully take part of this round!

→ Reply
»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

CM Time?

→ Reply
»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    In my opinion you should take part in every contest. You won't get better by only solving problems you like.

    → Reply
»
14 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

3 contests in 3 consecutive days, Amazing!

→ Reply
»
14 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it +23 Vote: I do not like it

$$$998244353$$$-forces.

→ Reply
»
14 months ago, # |
  Vote: I like it -43 Vote: I do not like it

Another horribly written Edu round.

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it -69 Vote: I do not like it

Maybe good problems, but with trash samples.

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it -132 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it +32 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 ?

          → Reply
          • »
            »
            »
            »
            »
            »
            14 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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).

            → Reply
          • »
            »
            »
            »
            »
            »
            14 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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

            → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Passed D but failed to debug C T_T

→ Reply
»
14 months ago, # |
  Vote: I like it +11 Vote: I do not like it

What is the 4th test case of problem E?

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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

    → Reply
»
14 months ago, # |
  Vote: I like it +31 Vote: I do not like it

Why E WA test 4??

→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 2   Vote: I like it +84 Vote: I do not like it

    try this

    11
1 1 3 3 5 3 6 6 8 2
    → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    7 1 1 2 3 3 5

    I think its something like this. Your code returns 3, and the correct answer is 2. To solve this, note that we can kinda control the parity of the root's child

    2 2 1 1 2 2 1

    → Reply
»
14 months ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve D

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The logic for problem B? Thanks in advance.

→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
        sort(all(a));
    sort(all(b));
    for(int i=0;i<n;i++)
    {
        c1+=a[0]+b[i];
        c2+=b[0]+a[i];
    }
    ans = min(c1,c2);
    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it +7 Vote: I do not like it

what is the approach for D ?

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can calculate contribution from individual bits

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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

        → Reply
      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what was test 4 of E

→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 3   Vote: I like it +22 Vote: I do not like it

    For example

    7
1 1 2 3 3 5

    which can be solved with two colors.

    Solution:
    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      Thanks, which all cases can be solved with 2 colours, then

      → Reply
»
14 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

      → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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))

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        14 months ago, # ^ |
        ← Rev. 3   Vote: I like it +4 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply
      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 ;)

        → Reply
»
14 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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;

}

→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    Integer overflow.

    Input:
1
2
1000000000 1000000000
1000000000 1000000000

Correct Output:
4000000000

Your Output:
-294967296
    → Reply
    • »
      »
      »
      14 months ago, # ^ |
      ← Rev. 6   Vote: I like it 0 Vote: I do not like it

      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;
}
      → Reply
      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it +4 Vote: I do not like it 
        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.

        → Reply
        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Many thanks!

          → Reply
          • »
            »
            »
            »
            »
            »
            14 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Maybe there are too many details in E :(

→ Reply
»
14 months ago, # |
  Vote: I like it +26 Vote: I do not like it

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?

→ Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it -22 Vote: I do not like it

E is bad

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    for node 2 it will be ambigious

    → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

i gonna say one thing C test 2

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it -26 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it

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.

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    can you explain problem D more?

    → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for E I also thought of the same solution, but why is n = 100, couldn't n = 10^5 also worked??

    → Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it

      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.

      → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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.

    → Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      do you know the reason behind doing that?

      → Reply
      • »
        »
        »
        »
        14 months ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

editorial when

→ Reply
»
14 months ago, # |
  Vote: I like it +21 Vote: I do not like it

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

;-;

→ Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    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) .

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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$$$

          → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell why 224965252 gives WA for problem D?

→ Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
14 months ago, # |
← Rev. 4   Vote: I like it +82 Vote: I do not like it

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.

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +54 Vote: I do not like it

    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.

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it -15 Vote: I do not like it

good contest

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So many successful hacks

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

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

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.

    → Reply
»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

So many successful hacks on A :o

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please explain how to do D in brief.

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Solve the problem with ones and zeros.

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks, that was very helpful, I couldn't understand how to come up with solutions for such problems

      → Reply
»
14 months ago, # |
  Vote: I like it -30 Vote: I do not like it

very bad contest

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Video Editorial for Problem A,B,C,D

→ Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
14 months ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dude exactly same question.

    → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    What would be the benefit of larger constraints? Having $$$n = 10^5$$$ would give extra hints and make the problem easier.

    → Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 3   Vote: I like it +10 Vote: I do not like it

    large N is a hint that k is always small, cuz it even may cause TLE in IO(If k is large too).

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Became Pupil, Let's Gooooo

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What is the solution for D

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I love codeforces

→ Reply