Incorrect plagiarism in Question D: The approach to the question used by many people is quite similar due to the structure of the question: just 3 DP matrices, and because of this, the structure of the code of a lot of the submissions is similar. Please look into this.

If you are up-solving D and have a hard time to understand the code written by other folks like me, here is a commented code that might save you a couple of hours.

PS: I commented and wrote it like this cause I was not able to understand the logic.

Editorial

Someone should add the link to the contest page.

Thankss

Congrats on Specialist mate!!

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

check 225001296, it has a naive and a proper solution for bools and ints

I still didn't get. Can you explain more?

Became Pupil, Let's Gooooo

Yup, I get it now. Thanks a lot.

Dang,that's so neat. Thankyou so much. Makes sense now, the way you put it.

I love C <3

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

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

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

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

That make sense, thank you ^^

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

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 ?

dude exactly same question.

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

Indeed

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?

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

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

.

Why Was My Submission Skipped Despite Submitting First

https://mirror.codeforces.com/blog/entry/120756

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

https://mirror.codeforces.com/contest/1879/submission/224996088

https://mirror.codeforces.com/contest/1879/submission/224996243

yes :")

yup it is little bit confusing :)

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

just search sum of xor of all subarrays and you'll find it on gfg. Link

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

can you give the similary problem link or cf id ? thanks!

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.

Oh, thanks for the help man! Your explanation made it very clear!

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.

thanks for help.

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

Thanks Brother <3 !!

Congrats!

Plag check going on ? After these many weeks Ratings are rolled back deyumn.

I got -1 when I was at 1599 Rating, now I hope I get +1 to 1600 and become Expert :)

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

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

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

Video Editorial for Problem A,B,C,D

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://mirror.codeforces.com/contest/1879/submission/224939377

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.

Solve the problem with ones and zeros.

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

very bad contest

Got it, thx

2 problems in my first div 2 is pretty decent I would say

Please explain how to do D in brief.

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.

Thanks bro!! I did the same mistake and got WA 5 times. I thought I didnt take mod correctly and got so much penalty Sadge

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

So many successful hacks on A :o

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?

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

So many successful hacks

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

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.

good contest

Yeah :(

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.

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

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.

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.

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

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.

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.

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

can you explain how did you made your MLE 7 to a TLE 7 , the only difference seems like you delete check[i] after using it. I did the same for my code but it didnt affected the memory. Can you explain how that works ?

submission without deleting : https://mirror.codeforces.com/contest/1879/submission/224985475

submission with deleting : https://mirror.codeforces.com/contest/1879/submission/224985830

i forgot to calculate ways to remove elements from section. Thanks for the explanation

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.

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.

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)

Same goes for me to ..

Thanks for clarification bro. <3

Can someone tell why 224965252 gives WA for problem D?

sample is two week, problem setter need eat some turtles.

tourist

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

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

do you know the reason behind doing that?

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.

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

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?

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.

oh lol, thanks Bro!.

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)

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

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

Many thanks!

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

can you explain problem D more?

Yeah, I got the logic but messed up in somewhat complex application, which was really bad.

how should i mulitply in case of 1100 like 2*2 or what? mine is giving 4 in that case.

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.