Привет, Codeforces!
В 24.09.2023 17:35 (Московское время) состоится Educational Codeforces Round 155 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов, Максим Neon Мещеряков и Роман Roms Глазов. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Теперь вам доступна cтипендия для получения степени магистра в области Computer Science и Data Science в кампусе Harbour.Space University в Барселоне!
Кратко о стипендии:
- Полностью финансируемая стипендия (29,900 €/год) для получения степени магистра в области Data Science или Computer Science в течение двух лет
- Кандидаты, успешно сдавшие экзамены, станут частью "резерва талантов" Университета и будут представлены компаниям-спонсорам. В случае, если кандидат выбирается в программу Work&Study от нашего отраслевого партнера, студент начинает стажировку с обязательством изучить 3 часа/день и работать 4 часа/день
Пожалуйста, обратите внимание, что кандидаты, прошедшие отбор, должны будут заплатить невозмещаемый вступительный взнос в размере 85 евро за обучение в Harbour.Space University.
Обязательства кандидата:
За год обучения вы завершите 15 модулей (длительность каждого 3 недели). Ежедневная учебная нагрузка составляет 3 часа, плюс домашнее задание, которое нужно выполнить в свободное время.
Требования к кандидату:
- Степень бакалавра в области математики, статистики, информатики или аналогичных областях
- Владение английским языком
- Расширенные знания и опыт в Python, SQL, Spark/Scala и bash
- Опыт работы с технологиями больших данных: Spark, HDFS, Kafka и т.д.
- Практический опыт работы с технологиями Data Science: конструирование признаков,
- Уверенное знание ML
- Большой опыт разработки программного обеспечения
- Способность решать проблемы
UPD: Разбор опубликован
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
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://codeforces.me/contest/1879/submission/224985475
submission with deleting : https://codeforces.me/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://codeforces.me/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.
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.
Why my E received 1 but wa on 4?
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
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://codeforces.me/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://codeforces.me/contest/1879/submission/224996088
https://codeforces.me/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.
The D question in this game is very similar to our previous game called the Blue Bridge Cup, and the thinking method used is similar. Please return my rating. The relevant websites are as follows: https://blog.csdn.net/Code92007/article/details/130299859?ops_request_misc=&request_id=&biz_id=102&utm_term=%E8%93%9D%E6%A1%A5%E6%9D%AFA%E7%BB%84%E7%9C%81%E8%B5%9B2023&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-130299859.142^v94^chatsearchT3_1&spm=1018.2226.3001.4187 The corresponding question is question H
What is the solution for D
I love codeforces