- Educational Codeforces Round 155 (Rated for Div. 2)
- Educational Codeforces Round 154 (Rated for Div. 2)
- Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)
- Educational Codeforces Round 153 (Rated for Div. 2)
- Educational Codeforces Round 152 (Rated for Div. 2)
- Educational Codeforces Round 151 (Rated for Div. 2)
- Educational Codeforces Round 150 (Rated for Div. 2)
- Educational Codeforces Round 149 (Rated for Div. 2)
- Educational Codeforces Round 148 (Rated for Div. 2)
- Educational Codeforces Round 147 (Rated for Div. 2)
- Educational Codeforces Round 146 (Rated for Div. 2)
- Educational Codeforces Round 145 (Rated for Div. 2)
- Educational Codeforces Round 144 (Rated for Div. 2)
- Educational Codeforces Round 143 (Rated for Div. 2)
- Educational Codeforces Round 142 (Rated for Div. 2)
- Educational Codeforces Round 141 (Rated for Div. 2)
- Educational Codeforces Round 140 (Rated for Div. 2)
- Educational Codeforces Round 139 (Rated for Div. 2)
- Educational Codeforces Round 138 (Rated for Div. 2)
- Educational Codeforces Round 137 (Rated for Div. 2)
- Educational Codeforces Round 136 (Rated for Div. 2)
- Educational Codeforces Round 135 (Rated for Div. 2)
- Educational Codeforces Round 134 (Rated for Div. 2)
- Educational Codeforces Round 133 (Rated for Div. 2)
- Educational Codeforces Round 132 (Rated for Div. 2)
- Educational Codeforces Round 131 (Rated for Div. 2)
- Educational Codeforces Round 130 (Rated for Div. 2)
- Educational Codeforces Round 129 (Rated for Div. 2)
- Educational Codeforces Round 128 (Rated for Div. 2)
- Educational Codeforces Round 127 (Rated for Div. 2)
- Educational Codeforces Round 126 (Rated for Div. 2)
- Educational Codeforces Round 125 (Rated for Div. 2)
- Educational Codeforces Round 124 (Rated for Div. 2)
- Educational Codeforces Round 123 (Rated for Div. 2)
- Educational Codeforces Round 122 (Rated for Div. 2)
- Educational Codeforces Round 121 (Rated for Div. 2)
- Educational Codeforces Round 120 (Rated for Div. 2)
- Educational Codeforces Round 119 (Rated for Div. 2)
- Educational Codeforces Round 118 (Rated for Div. 2)
- Educational Codeforces Round 117 (Rated for Div. 2)
- Educational Codeforces Round 116 (Rated for Div. 2)
- Educational Codeforces Round 115 (Rated for Div. 2)
- Educational Codeforces Round 114 (Rated for Div. 2)
- Educational Codeforces Round 113 (Rated for Div. 2)
- Educational Codeforces Round 112 (Rated for Div. 2)
- Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2)
- Educational Codeforces Round 111 (Rated for Div. 2)
- Educational Codeforces Round 110 (Rated for Div. 2)
- Educational Codeforces Round 109 (Rated for Div. 2)
- Educational Codeforces Round 108 (Rated for Div. 2)
- Educational Codeforces Round 107 (Rated for Div. 2)
- Educational Codeforces Round 106 (Rated for Div. 2)
- Educational Codeforces Round 105 (Rated for Div. 2)
- Educational Codeforces Round 104 (Rated for Div. 2)
- Educational Codeforces Round 103 (Rated for Div. 2)
- Educational Codeforces Round 102 (Rated for Div. 2)
- Educational Codeforces Round 101 (Rated for Div. 2)
- Educational Codeforces Round 100 (Rated for Div. 2)
- Educational Codeforces Round 99 (Rated for Div. 2)
- Educational Codeforces Round 98 (Rated for Div. 2)
- Educational Codeforces Round 97 (Rated for Div. 2)
- Educational Codeforces Round 96 (Rated for Div. 2)
- Educational Codeforces Round 95 (Rated for Div. 2)
- Educational Codeforces Round 94 (Rated for Div. 2)
- Educational Codeforces Round 93 (Rated for Div. 2)
- Educational Codeforces Round 92 (Rated for Div. 2)
- Educational Codeforces Round 91 (Rated for Div. 2)
- Educational Codeforces Round 90 (Rated for Div. 2)
- Educational Codeforces Round 89 (Rated for Div. 2)
- Educational Codeforces Round 88 (Rated for Div. 2)
- Educational Codeforces Round 87 (Rated for Div. 2)
- Educational Codeforces Round 86 (Rated for Div. 2)
- Educational Codeforces Round 85 (Rated for Div. 2)
- Educational Codeforces Round 84 (Rated for Div. 2)
- Educational Codeforces Round 83 (Rated for Div. 2)
- Educational Codeforces Round 82 (Rated for Div. 2)
- Educational Codeforces Round 81 (Rated for Div. 2)
- Educational Codeforces Round 80 (Rated for Div. 2)
- Educational Codeforces Round 79 (Rated for Div. 2)
- Educational Codeforces Round 78 (Rated for Div. 2)
- Educational Codeforces Round 77 (Rated for Div. 2)
- Educational Codeforces Round 76 (Rated for Div. 2)
- Educational Codeforces Round 75 (Rated for Div. 2)
- Educational Codeforces Round 74 (Rated for Div. 2)
- Educational Codeforces Round 73 (Rated for Div. 2)
- Educational Codeforces Round 72 (Rated for Div. 2)
- Educational Codeforces Round 71 (Rated for Div. 2)
- Educational Codeforces Round 70 (Rated for Div. 2)
- Educational Codeforces Round 69 (Rated for Div. 2)
- Educational Codeforces Round 68 (Rated for Div. 2)
- Educational Codeforces Round 67 (Rated for Div. 2)
- Educational Codeforces Round 66 (Rated for Div. 2)
- Educational Codeforces Round 65 (Rated for Div. 2)
- Educational Codeforces Round 64 (Rated for Div. 2)
- Educational Codeforces Round 63 (Rated for Div. 2)
- Educational Codeforces Round 62 (Rated for Div. 2)
- Educational Codeforces Round 61 (Rated for Div. 2)
- Educational Codeforces Round 60 (Rated for Div. 2)
- Educational Codeforces Round 59 (Rated for Div. 2)
- Educational Codeforces Round 58 (Rated for Div. 2)
- Educational Codeforces Round 57 (Rated for Div. 2)
- Educational Codeforces Round 56 (Rated for Div. 2)
- Educational Codeforces Round 55 (Rated for Div. 2)
- Educational Codeforces Round 54 (Rated for Div. 2)
- Educational Codeforces Round 53 (Rated for Div. 2)
- Educational Codeforces Round 52 (Rated for Div. 2)
- Educational Codeforces Round 51 (Rated for Div. 2)
- Educational Codeforces Round 50 (Rated for Div. 2)
- Educational Codeforces Round 49 (Rated for Div. 2)
- Educational Codeforces Round 48 (Rated for Div. 2)
- Educational Codeforces Round 47 (Rated for Div. 2)
- Educational Codeforces Round 46 (Rated for Div. 2)
- Educational Codeforces Round 45 (Rated for Div. 2)
- Educational Codeforces Round 44 (Rated for Div. 2)
- Educational Codeforces Round 43 (Rated for Div. 2)
- Educational Codeforces Round 42 (Rated for Div. 2)
- Educational Codeforces Round 41 (Rated for Div. 2)
- Educational Codeforces Round 40 (Rated for Div. 2)
- Educational Codeforces Round 39 (Rated for Div. 2)
- Educational Codeforces Round 38 (Rated for Div. 2)
- Educational Codeforces Round 37 (Rated for Div. 2)
- Educational Codeforces Round 36 (Rated for Div. 2)
- Educational Codeforces Round 35 (Rated for Div. 2)
- Educational Codeforces Round 34 (Rated for Div. 2)
- Educational Codeforces Round 33 (Rated for Div. 2)
- Educational Codeforces Round 32
- Educational Codeforces Round 31
- Educational Codeforces Round 30
- Educational Codeforces Round 29
- Educational Codeforces Round 28
- Educational Codeforces Round 27
- Educational Codeforces Round 26
- Educational Codeforces Round 25
- Educational Codeforces Round 24
- Educational Codeforces Round 23
- Educational Codeforces Round 22
- Educational Codeforces Round 21
- Educational Codeforces Round 20
- Educational Codeforces Round 19
- Educational Codeforces Round 18

Recent actions

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

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

0
Someone should add the link to the contest page. |

0
Thankss |

0
Congrats on Specialist mate!! |

Created or updated the text |

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

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

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

0
Became Pupil, Let's Gooooo |

0
Yup, I get it now. Thanks a lot. |

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

0
I love C <3 |

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

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 |

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

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

+5
That make sense, thank you ^^ |

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

0
Can you please explain a little in problem D about why it is sufficient/correct to just focus on calculating the double-sum |

0
dude exactly same question. |

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

-10
Indeed |

+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? |

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

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

0
. |

+1
Why Was My Submission Skipped Despite Submitting First |

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

0
yes :") |

0
yup it is little bit confusing :) |

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

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

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

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

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

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

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

0
thanks for help. |

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

0
Thanks Brother <3 !! |

0
Congrats! |

0
Plag check going on ? After these many weeks Ratings are rolled back deyumn. I got |

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

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 |

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

+8
Video Editorial for Problem A,B,C,D |

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

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 |

+5
Solve the problem with ones and zeros. |

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

-30
very bad contest |

0
Got it, thx |

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

0
Please explain how to do D in brief. |

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

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

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

+1
So many successful hacks on A :o |

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

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

0
So many successful hacks |

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

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

-15
good contest |

0
Yeah :( |

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

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

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

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

0
total positions we have to remove is
initially ans = 1 first we have to select any one out of k positions to remove so,
next we have to select any one out k — 1 postions to remove so,
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 |

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

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

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

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

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

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

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

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

0
Same goes for me to .. |

0
Thanks for clarification bro. <3 |

0
Can someone tell why 224965252 gives WA for problem D? |

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

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

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

0
do you know the reason behind doing that? |

+4
Let's split the string into (maximal) contiguous blocks of equal 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 |

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 |

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

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

0
oh lol, thanks Bro!. |

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

0
for the second part of problem you have to consider
instead of
even I did same mistake :( |

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

0
Many thanks! |

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

+7
can you explain problem D more? |

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

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

+4
You still have Also, if you want to paste code into comments, add |

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/30/2023 16:38:46 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|