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:
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
UPD: Editorial is out
Men are Brave.
Why is this so true
Edu rounds seem to give me only ((-1)^n for all n % 2 == 1) Δ)
Hope everyone success! ~
Roger that :)
i'm so excited to join my first educational Round wish me Luck Guys
sunday cf rounds (●'◡'●)
Codeforces >>>>> University Exams
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.
Contest week <3
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.
Yeah. You just said truth.
Thanks for your feedback and take of love.
Wish everyone successfully take part of this round!
CM Time?
i hope so, as well ;)
Not once did I get a good score in EDU :(
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?
the problem you gave does open in pdf Sir.
I've have just started giving contests and my rating is around 600. Should I take part in this ? anyone ?
In my opinion you should take part in every contest. You won't get better by only solving problems you like.
Hope I can learn something new from this round, good luck everyone ^^ (do not downvote me pls??)
3 contests in 3 consecutive days, Amazing!
I'm used to losing my rating in the edu round, come on, there's nothing to be afraid of anymore.(`□′)╯┴┴ ┴—┴
$$$998244353$$$-forces.
Another horribly written Edu round.
Thanks for nice problems. Enjoyed solving D. Good one.
D was pretty good, idk how this many people solved it
Maybe good problems, but with trash samples.
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?
Yeah I use alt because 'rated' gives me more pressure.
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.
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 ?
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).
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
Passed D but failed to debug C T_T
What is the 4th test case of problem E?
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
Why E WA test 4??
try this
I see. Edges right under the root may not in a same color. Anyway thank you.
sample is two week, problem setter need eat some turtles.
tourist
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
How to solve D
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.
The logic for problem B? Thanks in advance.
a[0] and b[0] are the minimum ones of a and b, right?
yess
Had the correct solution for B, but spent literally an hour on a "wrong" answer because I used 0 instead of 0ll. RIP.
what is the approach for D ?
you can calculate contribution from individual bits
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
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
look at 225001296 which has multiple solutions for numbers and for individual bits
I hate C!!!!!!!!!
skill issue(applies to me as well). gotta work on combinatorics seriously.
D was just a modified version of an existing problem with just a few changes needed while implementing it.
can you give the similary problem link or cf id ? thanks!
just search sum of xor of all subarrays and you'll find it on gfg. Link
what was test 4 of E
For example
which can be solved with two colors.
Thanks, which all cases can be solved with 2 colours, then
Anyone else got wrong ans on test case 2 for C?
+1. No idea why. Should skip it earlier.
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).
Yes, I get through this with testcase
Must be
2 8
(because there is (1 2), (1 3), (2, 2), (2, 3), (3, 1), (3, 2), (4, 1), (4, 2))what will be the ans for this test case 000111000 explain a little why if you can.
Let's split the string into (maximal) contiguous blocks of equal bits:
000
,111
and000
. 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
.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)
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 ;)
C seemed pretty easy at first but after getting 3 WA and getting AC finally I realized that I was right
What's wrong with #224889872:
}
Integer overflow.
Thank you. Changed to long long int, but still does not work:
You still have
int suma
andint 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.Many thanks!
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.
you're having an integer overflow. Use 64bit long, and i think you should pass. I made the same mistake in the contest! :(
Sucks to have had the answer to problem E but failed because my outputs didnt flush properly :( edit, nvm test 4 was a coutnerexample
Maybe there are too many details in E :(
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?
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
E is bad
for node 2 it will be ambigious
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.
i gonna say one thing C test 2
Link to the streaming of today's contest solutions anyone?
https://www.youtube.com/watch?v=tODo9BSLSmM
why can't u spare 1024MB for F QAQ.I was suffering with my solution with a memory complexity of $$$O(n\sqrt {n})$$$
I think E is not good, it makes us crazy. My classmates is shouting now.
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.
can you explain problem D more?
for E I also thought of the same solution, but why is n = 100, couldn't n = 10^5 also worked??
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://mirror.codeforces.com/contest/1879/submission/224976624
upd: hacked
There are so many resources about the solution for D on the internet (for example). I doubt if there were any cheaters.
But how do you incorporate the multiplication with length of each of the subarray?
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.
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.
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
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
for the second part of problem you have to consider
instead of
even I did same mistake :(
224975617
do you know the reason behind doing that?
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
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.
editorial when
bruh, wrong answer on test 5 of D because i forgot to mod 998244353 for the n = 1 case...
;-;
problem E is very hard (to me) but very fun!
and the trick 'calc bitwise' is useful on D
overall, i felt well.
Can someone explain the solution to c? my combinatorics are pretty bad
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)
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?
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) .
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.
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.
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$$$
Can someone tell why 224965252 gives WA for problem D?
Anyone else got hacked by misunderstanding problem A, thought you must strictly greater than the weight to lift it?
Yeah :(
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.
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.
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.
The questions are a little classic. I think C, D and E are simpler than usual.
good contest
So many successful hacks
seems like author didn't put much effort for making testcases in 1st problem.
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?
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.
Got it, thx
So many successful hacks on A :o
Please explain how to do D in brief.
Solve the problem with ones and zeros.
thanks, that was very helpful, I couldn't understand how to come up with solutions for such problems
I still didn't get. Can you explain more?
check 225001296, it has a naive and a proper solution for bools and ints
very bad contest
This should be hackable, but I'm too lazy to write a testcase against it.
224983900
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
38th number differs corresponds to 19th tc as each tc outputs 2 numbers. 1100 is the tc for which your code breaks
Video Editorial for Problem A,B,C,D
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
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
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.
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)
towhile (cmd == 0)
and you'll probably get WA instead of TLE.Yes, u were right. There was error in my logic. Luckily I was able to spot it after your comment. Thanks for the help
I'm getting issue while filling for Master's with above link, can anyone help?
Actually I think the description of C should be more clearly, I do not think different blocks can be relevant in the first hour...
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
maybe the intermediate calculation results exceeding the range of long long,you should module after every multiplication
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?
dude exactly same question.
What would be the benefit of larger constraints? Having $$$n = 10^5$$$ would give extra hints and make the problem easier.
That make sense, thank you ^^
large N is a hint that k is always small, cuz it even may cause TLE in IO(If k is large too).
Became Pupil, Let's Gooooo
I want to ask that where is the Editorial? thanks!
Editorial
Someone should add the link to the contest page.
What is the solution for D
I love codeforces