Hello, Codeforces!
Riblji_Keksic and I are glad to invite you to Codeforces Round 911 (Div. 2), which will start on Nov/26/2023 17:35 (Moscow time). You will be given 6 problems and 2 hours to solve them.
The round will be rated for participants of Division 2 with a rating lower than 2100. Division 1 participants can participate unofficially.
All problems are invented and prepared by Riblji_Keksic and me.
Special thanks go to n0sk1ll and TimDee for their great work during the testing process of the round.
And of course, I would love to thank the people who made this round possible:
pashka for his great coordination of the round!
IgorI for helping host the round!
Alexdat2000 for helping translate the round!
prvocislo, wxhtzdy, cadmiumky, satyam343, n0sk1ll, TimDee, wuhudsm, AlphaMale06, Blagoj, priyanshu.p, Acanikolic73, gubica, ognjentesic, VeljkoGalovic and repmann for testing the round and providing valuable feedback!
KAN for his contribution towards the round!
MikeMirzayanov and the team for the codeforces and polygon platforms!
You for participating!
We hope that you will participate and enjoy the round!
Update 1: The score distribution is 500 — 1000 — 1250 — 2000 — 2250 — 3000
Update 2: Congratulations to the winners:
Div. 2:
All participants:
First solvers:
A. people_plus_plus in 0:01
B. A_G in 0:04
C. WLZ in 0:04
D. A_G in 0:12
E. Grindforces123 in 0:17
F. turmax in 0:26
Update 3: Editorial
Codeforces Round 911 whats your emergency?
My Rating is dead.
I got stuck o B, please help!!
When you think of the parity of numbers, there are three distinct situations that can be easily proven.
1) If all three numbers are either odd or even, then the answer will be 1 1 1.
2) If two of the numbers are even and the other one is odd, then the answer will be the odd number.
3) If two of the numbers are odd and the other one is even, then the answer will be the even number.
for a = 1, b = 3, c = 7 can you tell stepwise how can I achieve all numbers as 1
Erase 2 and 3 three times and write 1 each time. Then you have 4 1s, no 2s, and 4 3s. Now use the following procedure: erase 1 and 3, writing 2. Then erase 2 and 3, and write 1. This decreases the number of 3s by 2, and doesn't change the number of 1s. Do this twice, and you have 4 1s and nothing else.
1,3,7 notice that if the other two of the numbers are the same you can always get the answer for A 1 3 7 -> 2 2 6 > 3 1 5 > 2 2 4 > 3 1 3 > 2 2 2
More generally, the strategy is to alternate increasing the the one we are picking and the minimum of the other 2 numbers until the third number decreases and reaches the other number. So if we are picking A and b < c, we alternate between A and B until b=c.
Since, 1^2^3 = 0, after any operation you cannot change the xor. So if xor != 0, then only xor can be achieved, it can be achieved by doing n-1 operations. Otherwise, all can be achieved by the following operations, let's say you want xor to be 1, then if 2 and 3 exists then do operation on them, otherwise do it on 1 and other existing number. This will ensure that at least one 1 exists in array after any operations.
my laptop is on fire send the firefighters
Just a small thing, sir!
Definitely a round I enjoyed testing! NemanjaSo2005 Riblji_Keksic orz
Canon round.
become specialist in this one, canon event
let's see who becomes specialist first
challenge accepted!
You won! 😅, wanna race to Expert now?
As a tester,the problemset is dramatic.Hope you enjoy it :)
Thanks, But i think is about how dramatic is => how enjoyable the contest ARE?
Yet another Serbian round?
orz
Hope I can reach the specialist again in this round.
THE BESTEST IN THE WORLD EVER 100% SERBIAN ROUND
Back to back div2s every day let's go
As a tester, the problems are exciting!
It is the first time for that guy to prepare a contest, I am a little worried ...
You can talk when you become master.
It is the first time for that guy to prepare a contest, I am a little worried ...
It is the first time for that guy to prepare a contest, I am a little worried ...
Jokes aside, yes, it is the first contest for both of us. We don't have much experience, so round will definitely have some flaws. But please provide us feedback after the contest so that we can improve in the future.
My comment was directed towards TimDee, bullying someone based on rating.
I hope everything goes well with the round. Don't worry about it.
Yeah, I got that. The point of my comment was to say that even I am a bit nervous about the round, but yeah, hopefully everything will go good.
Does being master guarantee being a good problem setter?
When did Nemanja or I gain the reputation of being "that guy"?
Good luck for everyone! ;)
As a tester, NemanjaSo2005 Riblji_Keksic orz for preparing amazing problemset!
As a tester, NemanjaSo2005 Riblji_Keksic orz for being Serbian!
I love this contest marathon we've ended up having! ;)
3 rounds in 3 days wrooom!!!
Contestants with aot profile pictures have +200% chance to have positive delta on the rounds I author.
what about clowns?
It has been proven to be true! rating++
Another serb round???
Good luck everyone ^_^
A 911 contest on 26/11 ? The numbers are too heavy to be considered a coincidence
Hoping to reach pupil today
30000 score problem, nice!
Yeah, it is actually NP hard, so if you solve it you prove P=NP.
am i seeing it correctly, or the score distribution for problem F really is 30,000(bang).
Thanks for pointing it out. I corrected it.
NemanjaSo2005 best problem setter!!
Fun fact : $$$\text{E + F} \gt \text{A + B + C + D}$$$.
rainboy round :(
Seems like F > A + B + C + D + E
Такое хорошее настроение было и его просто испортили 5-м примером из условия задачи A...
Почему
Потому что невозможно сразу понять, что переливание происходит в любую клетку, а не только в соседнюю. Также по примерам нарисовано, что они переливают в соседние клетки. То есть, на картинках в условии только в соседние переливание. Запутали окончательно. Ну а мозг человека помнит только три последних прочитанных абзаца. Надо нормальные примеры делать (на которых переливание в любую клетку), чтобы это контрилось, тем более это задача A. Судя по тому, что было общее уведомление по этой задаче, у многих такая же проблема.
Обычно авторы задачи "живут" в своей задаче, делая её много часов, поэтому для них это очевидно, а для тех, кто только что прочёл, это просто ужасная ловушка и потеря времени и настроения... Такое фиксится во время тестирования раунда, а не на самом контесте.
Позиция платформы такая, что задачи делаются для сообщества, то есть, для тех, кто будет их решать. Значит, можно убрать двоякое понимание задачи на этапе подготовки, чтобы любой прочитавший задачу понял её в такой постановке, как задумывали авторы, и никак иначе, тогда он сможет приступить к решению задачи, в соответствии с главной идеей платформы, а не тратить время, решая не ту задачу.
Поверь мне, ты не видел изначальную версию условия задачи) Как раз там и было то самое двоякое понимание условия о которым ты говоришь)
В нынешнем варианте условия лично не вижу никаких проблем (да, задача сама по себе не лучшая, но это было сказано и авторам и координаторам, всё же я думаю что им лучше решать, каким раунду быть)
Да я просто ушёл с контеста после того, как на три моих вопроса по задаче A ответили "без комментариев".
На 34-й минуте контеста, в итоге, появилась массовая рассылка:
Если бы этот абзац написали в качестве ответа, я был бы счастлив, или если бы это было в примечаниях к примерам было, был бы ещё более счастливым.
Ну, уж к ответам на вопросы я не как не могу отнестись (
Возможно, абзац про перенос в любую клетку был в версии когда я тестил. После "упрощения" условия его убрали, увы вычитать условие (особенно на русском) заново лично у меня уже времени не было) Да и вспомни, что условия переводят не авторы, а координаторы (обычно), и они тоже порой могут ошибаться)
Ну а чтоб не тратить время можно было начать решать с задачи Б ;)
Ведь задача платформы (отчасти) — обучение, а не рейтинг! =)
Обучение? Я все равно в Б написал дп, вместо того, чтобы думать
А если я скажу что цель платформы — развлечение, ты скажешь что писать ДП в Бшке тебя развлекло?)
Нет, я напишу что это меня не развлекало
Было бы неплохо поставить в ограничении <= 1e9
Согл, но может авторы и хотели оставить возможность написать тупое дп)
Мне очень понравилось этим заниматься
Can someone tell me whats the job of testers, if you need to correct the problem statement, text case explanation by a big margin in contest time? This is disgusting.
We made just small changes to make problem more understandable. If you knew what problem A was originally you would understand what testers are for.
Keksic left on seen ......
Me: Us bro us
If I knew more algorithms/ theory about Number theory could have got D, the main idea is so obvious
In which way exactly it is obvious for you if you do not know the theory? Can you please explain the "obvious main idea?"
GCD convolution. A similar problem was asked a few time ago: https://codeforces.me/contest/1884/problem/D
Sure, the trick involved is similar. Note that the problem (and solution) isn't similar, you can't call two problems using same trick or algorithm or data structure similar. (By the same logic, every binary search problem is simillr?) Also note that problem doesn't require you to brainlessly find number of pairs having GCD equal to i, also maybe look up the author solution and see that it's different as well (but yes, problem can be reduced to 1884D trick, that's how I solved it during testing, still that knowledge only helped me to know how to find number of pairs with fixed gcd, not to solve the problem.)
In sfarsit, vreau sa spun ca Nila Ucsepop m-a dezamagit cu faptul ca nu a luat aur la Stelele Matematicii.
Is there any specific name of this trick ? I want to learn , just curious.
Not sure about exact name, but it's one of ways to do PIE here so read about it.
Actually I found nothing on google about PIE.. Is there any full form of PIE.
Inclusion-Exclusion Principle
queueueuueueueueueueforces
SpeedForces
QUEUE!!! ANY TIME EXTENDED?
I will keep trying to solve div2 problems :) I hope one day I will overcome the obstacles
Problem B is a nice application of the classical puzzle:
Problem C is a gentle introduction to Tree DP (although arguably you could remove the DP array and deal directly with DFS return value instead).
How is b related to that puzzle?
If you have $$$(x, \ y, \ target)$$$, assuming $$$x \leq y$$$, then you could first convert it to $$$(0, \ y - x, \ target + x)$$$. Then, for each $$$(y - x)/2$$$ chocolate of the middle kind, you utilize one chocolate from the end to convert it to $$$(1, \ y - x - 1, \ target + x - 1)$$$.
Hence, we need at least $$$(y - x)/2$$$ chocolates of the third kind for this to be possible.
The catch (in this problem, as well as in the puzzle) is that you don't have to directly check $$$(y - x)/2 \gt target + x$$$, since chocolates/wrappers are generated on the fly, so you could utilize the generated ones as well.
Submission
For this question it is always possible if the other 2 have the same parity. The logic for that is you can keep going back and forth until the other 2 are the same value.
D is too hard for me :(
This is almost the same as B
How to solve D?
Why my this solution for problem C is giving TLE — https://ideone.com/uV3iX5
can someone pls help
Per-leaf approaches can die vs. trees shaped like long-handled brooms. Your early-out will only work if the earlier answers are better than the ones that come afterwards. Otherwise, it's possible to get stuck traversing the treetrunk/broomhandle repeatedly as you improve your overall answer for each leaf.
To avoid this, you can use the return/post portion of a dfs, or you can do a full topological sort. Basically you want to avoid repeatedly processing vertices, but you also want to make sure a vertex is processed after all of its children.
How to solve D?
i liked problem C and was very satisfied by solving it.
How to solve B?
i got stuck on this for a whole hour lol ;-;
Bassically, first get the mod 2 of them, if they are all equal the answer is "1 1 1", else, the answer is the number with a different mod of the other two.
sorry for bad english.
why this works? i don't now, proved by AC
Note that 1 1 2 -> 1 3 -> 2. So you can always decrease the number of 1/2/3s by two.
And when you can't decrease anymore you are at most one step away from the answer: https://codeforces.me/contest/1900/submission/234491758
i don't know if it an intended solution but u can solve it with dp: https://codeforces.me/contest/1900/submission/234459457
Could someone please tell why I'm getting TLE? 234480936
Isn't my solution at most works in O(2 * (10 ^ 7))? Shouldn't it fit in the time limit?
Seems like the solution is OK, but implementation is brr...Maybe i am not correct, but "vector < vector <vector < int > > >b(100001);", " while (pow(j, 2) <= a[i])" can make your program slow.
How can 3d vector and squaring slow the program? I mean like why?
easily! I am pretty sure, that if you change pow to "while (i * i < j)" it become faster.
Ok, thanks, i'll try that
I wonder what is the solution for D... There are a couple of thoughts on factorization, but nothing seems to fit in time limits.
B > C ;)
It took me ages to even understand C :/.
you just have to know how to use DFS
Could anyone tell me what is wrong with my implementation? I got the wrong answer in pretest 2. I used dfs + dp. https://codeforces.me/contest/1900/submission/234485614
It looks like dp[] for internal nodes updated multiple times when started from different leaves.
Dfs is usually walking from top to leaves calculating something along the way: https://codeforces.me/contest/1900/submission/234501347
not saying it was a bad contest at all, but problem D was very similar to problem 645F(https://codeforces.me/contest/645/problem/F) such that it was the case of k=2 for that problem.
I just read it and it doesn't seem in any way similar, unless I don't know actual solution. However, i don't think that comparing the trick used in solution/solution itself is best way to describe similarity of two problems.
Still, I may miss something, so could you please elaborate about what exactly they're similar in? =)
say you have the solution of the problem for k=2.
you can solve D like this:
n=1 q=n-1, k=2 sort the array and give the elements of it in each query. the sum of all querys except the last one is the answer.
Hm, right, it makes sense. Though i still don't agree that "solution to this problem can also solve this problem" makes those two similar (sometimes it can, but here it's not the case, since problems ask for different things (I mean, 645F should be heavily simplifies to arrive to today's D, like, limit K to 2, sort array, do queries adding sorted array elements ...))
Anyway, thanks for your problemsetting I really enjoyed your contest.
(I wasn't setter, I was tester, but still thanks for feedback :D) so I ping NemanjaSo2005 for good contest
Cool problems, Thanks!!
Is answer in D smaller than long long max?
Yes, I think N choose 3 < long long max
$$$\binom{80\,000}{3}\cdot100\,000\approx8.5\cdot10^{18}$$$
$$$2^{63}-1\approx9.2\cdot10^{18}$$$
Yeah, that makes sence, Thank you. I was too nervous during contest and didn't come up with this
Is $$$E$$$ following? Build condensation of graph (find strongly connected components and make them 1 vertice, the graph becomes acyclic). And then just dp on DAG to find path with greatest number of vertices (sum not the vertices in condensation, but for each vertice in condensation number of original vertices in it). (Why do we have to minimize some cost then? It doesn't change the problem)
I thought of this too. There can be multiple longest paths in a DAG
This method is correct, at least I have temporarily passed it
1->2 1->3 2->4 3->4 There are two logest paths in a DAG 1->2->4 and 1->3->4
The graph may not necessarily be connected, therefore there might be multiple paths with the same longest length but different weights.
Yes. Then you can store dp as pair {length, sum} and update it as the statement requires it.
Кстати, стоимость просят минимизировать т.к. у тебя может быть более одного множества вершин формирующих путь максимальной длины и соответственно на этом и строится задача, хотя ограничение довольно искусственное, но без него задача была бы слишком стандартной наверное)
It is still very standard
After you observe that you must condensate the graph, yes. It's not too trivial to arrive to that observation.
Any hints for F?
i think its something along the lines of:
UPD: you will also have to add O(logn) elements to the front and the back of the array that you are maintaining in the query while simulating the operations(because some elements from the begining and the end of your query interval could have been deleted by the rest of your array)
Is D mobius?
I saw someone solve it with mobius, although i know nothing about it. Do I really need to know mobius to reach expert, I solved ABC in 19 minutes?
Not really it's rare, i would recommend focusing on more common topics first
I solved it without mobius (hopefully :)
Hint: iterate over all possible GCDs
aren't there O(n^2) gcds?
gcd is bounded by 10^5.
I'm willing to bet money that problem A was inspired by Minecraft.
Minecraft water logic in A, nice
I enjoyed thinking about problems ABCD,Thanks you for the contest. by the way any hints for optimizing (n ^ 2) solution of problem D
Please tell me what topics I need to solve problems like D and E (also to become expert: in general) thankyou so much :3
problem D was a combination of number theory(gcd), combinatorics and inclusion-exclusion principle
problem E was a combination of graph theory(for SCC compression) and simple DP on DAG(to calculate maximum length of a path and its smallest value)
Was too rusty on my Möbius reduction to solve D in time sadly :c. ABC were good, as well as E, which wasn't straight up untouchable while still proving hard!
Did you end up solving it using mobius?
what is mobius?
https://codeforces.me/blog/entry/53925
In the end no, but it simplifies down to calculating this: (then subtract a thing, divide by 2 and multiply by $$$n$$$, more or less)
Which should be very similar to the last example in this blog post, but for gcd instead of lca. I couldn't wrap my head around those last transitions though.
can you explain more please i did get to o(n ^ 2) solution but i can't understand how can i optimize it using mobius
I doubt I can really explain it better than the blog post I linked. There is this function $$$\mu$$$ which is multiplicative and you can use the linear sieve to calculate its values quickly, and it has this interesting property which... yeah I'll just refer to the blog post.
There is (n-j) term here i think for instead of multiplying by n
The first thing is you sort the array in descending order. Then if I'm not mistaken: \begin{equation} \Sigma^n_{i=1} \Sigma^n_{j=i+1} \Sigma^n_{k=j+1} f(a_i,a_j,a_k) \end{equation} \begin{equation} = \Sigma^n_{i=1} \Sigma^n_{j=i+1} \Sigma^n_{k=j+1} \gcd(a_j,a_k) \end{equation} \begin{equation} = n \cdot \Sigma^n_{j=2} \Sigma^n_{k=j+1} \gcd(a_i, a_j) \end{equation} \begin{equation} = n \cdot \frac{\Sigma^n_{j=2} \Sigma^n_{k=2} \gcd(a_i, a_j) — \Sigma^n_{i=2} \gcd(a_i,a_i)}{2} \end{equation}
Sike, I am mistaken. You are right, line two $$$\ne$$$ line three.
BRUHHHHHHH
Do you really need that for D?
Judging by the comments here no, some people solved the problem without it
Problem A is basically minecraft infinite water source.
please quickly upload the editorial, so that I can understand problem D
Calculating the sum of (gcd) of the two smallest numbers in all three-member subsets of a given set.
thank you for the reply, but I meant that I want to understand the solution. My bad :(
D is very interestring problem... i like it
freaking hard D
Problem D is pretty like to this 1884D - Counting Rhyme problem. There we should use a trick with inclusion-exclusion in dp for calculating all pairs of integers, that have fixed gcd. But these two problems are different from classical problem and we should modificate this dp.
The inclusion-exclusion principle is relatively hard for D. It took me roughly an 1.5 hour to come up with it because I forgot this idea.
Unluck :(
I was stucked on problem B :)))))))
May be you didn't solve too many problems with different tricks(I automatically recognized this trick when I have seen the problem)
In problem C, why my code is TLE when I use dfs by recursion, and I AC when I use dfs by Stack ?
Code TLE: https://codeforces.me/contest/1900/submission/234465423
Code AC: https://codeforces.me/contest/1900/submission/234469294
Besides: My other Code use O(nlog(n)) but it's TLE : https://codeforces.me/contest/1900/submission/234458841
Pass the string s in dfs() by reference too. Solution Accepted
I'm so careless, tks! And What about my O(nlog(n)) code?
I think you got a bit unlucky, pass the string by reference in dfs and you should get AC. Creating a linear copy of string in each dfs call made it $$$O(n^2)$$$.
I'm so careless, tks! And What about my O(nlog(n)) code?
The height of the tree is not guaranteed to be $$$log(n)$$$, so worst case is again $$$O(n^2)$$$
In the case height of tree is n then Leave of tree is one so it's O(n), and in the case max Leave of tree is n/2 then height of tree is log(n) so it's O(nlog(n))
I found case my code is O(n^2):
Feedback: In my opinion, B and C were a little too easy, and D was a little too hard. Maybe not, but the jump in difficulty from C to D was really huge for sure. Either: 1) make B,C harder or 2) make D easier (or a little bit of both). Other than that, that was a great contest, especially given that it's your guys' first time setting, good job!
Agreed
Thanks for the authors for this round ! Here is my advice about the problems (uncorrelated to my performance)
One of the best div2 A I solved ! Simple statement, simple solution, there is an idea but it's not "random math problem with gcd in it". Btw, is it inspired from minecraft ?
Very cool problem about invariants. It is maybe a bit standardish but I think that considering the target audience of div2 B it is a great problem !
I feel sorry for saying this but this problem is way too easy/standard in my opinion. It is an interesting educative problem but I think it's way too standard (it would probably have been fine if it was the only standard problem in the round).
I liked this problem a lot. I wanted to bash with things like mobius inversion but ended up coming up with a cool dp sol (which is apparently standard according to other comments).
Fun fact: I opened the round a bit late, I wasn't planning of competing. I read E and implemented it on the spot. This problem is a very cool problem to practice strongly connected components, however I believe it might be way too standard. Again, it would've been fine if it was the only standardish problem in the round but I think that the CDE combo is not perfect :/
Congratulation to the authors though, the problems were still of good quality and I appreciate the fact that AB were not left behind !!
Looking forward to another round of yours :))
Can you please explain your solution to D or maybe add comments in your code?
I explained it here. I hope it's clear enough
can you tell me why this solution won't work:
https://codeforces.me/contest/1900/submission/234481346
Expain your DP on D
First I considered the easier problem of finding the sum of $$$gcd(a_i,a_j)$$$.
Let $$$dp[d]$$$ be the number of pairs having their gcd equals to $$$d$$$. Once you know all rhe $$$dp[d]$$$, the answer is just $$$\displaystyle\sum_d dp[d] \cdot d$$$.
Let $$$M$$$ be the maximal value of $$$a_i$$$ (here $$$M = 10^5$$$). Notice $$$dp[M]$$$ is the number of pairs of elements that are divisible by $$$M$$$.
Let's compute $$$dp[d]$$$ Assume $$$dp[k]$$$ is known for all $$$k \gt d$$$. We know $$$dp[d]$$$ is at most the number of pairs of elements that are both divisible by $$$d$$$. However, among these pairs, we need to remove the ones whose gcd is not $$$d$$$. Such pairs will have gcd $$$2 \cdot d$$$ or $$$3 \cdot d$$$ etc.
You can use the exact same approach to solve the problem (except you are counting triplets so you should sort the array first to know how many elements are larger)
Code 234513315
Thank you, I'll study this method.
My solution during round was working with complexity $$$O(M \cdot uv)$$$ where $$$u$$$ is $$$M^{\frac{1}{3}}$$$ and $$$v$$$ unknown for me, but it gladly AC.
Your solution is working $$$O(M \cdot M^{\frac{1}{3}})$$$ I guess.
bruh 911 contest on 26/11. it cant be a coincidence bro. https://en.wikipedia.org/wiki/2008_Mumbai_attacks https://en.wikipedia.org/wiki/September_11_attacks
Solving Backwards D-C-B-A, hope I will reach CM one day, By the way very nice problem D, and glad that I solved it in the contest itself.
Can you please explain your approach for Problem D?
Sort the array,
Now for every element ai push the index i in map of the factors of ai. After completing this step for all elements, for each key in map you will get the indexes where the elements present are divisible by this particular key.
Now gcd will be some number inside our keys in map.
Iterate from highest keys to lowest keys , as answer for any key will also depend upon the answer for multiples of that key.
=> Remember map[i][j] represents and index b/w 0-n , such that element at that index is divisible by i, formally a[map[i][j]]%i=0
Particularly, dp[i] += i*j*(n-map[i][j]-1)
(because for jth element in map[i], you can select any 1 element from 0 to j-1 , jth element and any 1 among n-1-map[i][j], as these 3 numbers will give you a valid tuples (ap1,ap2,ap3) whose gcd = gcd(ap1,ap2) = i.
Also you have to subtract the contribution of multiples of i, as if i divides 2 numbers then it doesn't necessarily mean i will be the gcd of these 2 numbers.
Hence, dp[i] -= dp[i*j]/j for all j
This is fucking amazing. Thank you for this. Edit: I paraphrased above answer a bit with better formatting.
Actually, compexity is $$$O(n \cdot A^{\frac{1}{3}})$$$
Huh? How? Iterate factor until sqrt(A) takes $$$\sqrt{A}$$$ time, no?
We only interested in factors of number $$$A$$$, so we will iterate not in all number from $$$1$$$ to $$$\sqrt{A}$$$, but iterate in vector of factors $$$S$$$ of nubmer $$$A$$$, then $$$|S| \approx A^{\frac{1}{3}}$$$
Also check this, solution with compexity $$$O(A \cdot \log{A})$$$ https://codeforces.me/blog/entry/122677?#comment-1088299
Thanks a lot. Just one more thing: In the last line, "$$$dp(i) -= dp(i*j)/j$$$ for all j," j is in range 2 to $$$\frac{\text{highestKey}}{i}$$$, right?
Yeah because after that , all the states will be zero.
And actually for higher keys we will subtract for the factors of that higher key, and will add for them afterwardss when our loop will arrive eventually to them.
Yeah. I felt that the problem was a bit difficult to be Div2D.
Yeah maybe, it is 2000 rated as per clist.
Shouldn't have solved backwards, you're sacrificing a lot of free delta from A and B
I know, but I want to get myself accustomed to solve D in live contest, as after solving A,B,C either there isn't much time left for me or my brain becomes fucked up to think for D calmly.
damn bro, how are you improving so fast!! ;)
Thanks!
Can someone who was able to solve E can explain why this won't work for E, or report any points i missed:
You need to consider strongly connected components. Currently you are running a dp on a graph that has cycles (well sometimes you can use dp even when you have cycles)...
If you are still not convinced, try thinking about why you think your solution is correct
For problem D,any particular reason we are not required to output the answer mod some prime. In the current form, the maximal answer can $$$nC3*max(a[i])$$$ which if not calculated carefully (finding the ncr part and then multiplying) can overflow.
https://codeforces.me/blog/entry/122643?#comment-1088003
I agree with that. However if we are not careful and in the worst case where n= $$$ 8* 10^4$$$ with all array values as $$$ 10^5 $$$, if we are not careful and write the code as
ans=ans+(i*freq*(freq-1)*(freq-2))/6ll;ans=ans+i*(freq*(freq-1)*(freq-2))/6ll;It can overflow. I know this is mostly my fault but still I feel that mod would have been a better option here
I got FST in the last test case due to this... Also, it would have been cool if these overflow test cases were included as pre-tests.
I feel like problems today were more educational than usually, you just should know the main approach for problems like these and then they're easy, otherwise really hard to come up with
Nice contest. Problems were well designed and fun to solve. Thanks for the round NemanjaSo2005 Riblji_Keksic and all testers.
Yo it was a great contest!
There was a long queue in last 10-15 minutes. Then still it's considered as rated round. Disappointed :(
There is no queue lol
I submitted my last solution 11 minutes earlier of the deadline but still didn't get verdicts till the end
good contest
Please tell me how you think about problem D and what is the breakthrough point?
+1
How to improve number theory with dp?
I didn't know how to solve it with dp, but I passed it during contest.
Idea is following:
let $$$x$$$ be divisor of $$$a[i]$$$ ($$$a[i] \mod{x} = 0$$$). Let's $$$q[v]$$$ is the number of such $$$a[j] (j \lt i)$$$ that $$$v$$$ is divisor of $$$a[j]$$$. Let's iterate over all divisors $$$x$$$ of $$$a[i]$$$ and sum over $$$q[x]$$$ is the answer.
orz fallleaves07
How did people_plus_plus solve a problem in 1 second???
I am friend of authors, they told be problem A for sure
Can someone Please explain why I am getting a TLE in this solution for problem C 234510811
You are passing the entire string for each dfs call, which makes it O(N^2)
I got message from the system that my solution of C is same as other coder. my code: https://codeforces.me/contest/1900/submission/234467535 other's code: https://codeforces.me/contest/1900/submission/234459009
i didnt copied anyone's code, the solution is very straightforward. Easy codes can look similar. Please remove this penalty
I got a message from the system that my solution of C coincides with another code:
my solution: https://codeforces.me/contest/1900/submission/234456967
other code: https://codeforces.me/contest/1900/submission/234468345
Just see the difference between the coding style between those two codes.
I have no idea how did this happen. I wrote a very simple solution just using BFS. i think it is normal that easy codes look similar to each other.
Please reconsider this and remove my penalty.
Hey @MikeMirzayanov i have received this System mail yesterday
Attention! Your solution 234440272 for the problem 1900C significantly coincides with solutions KatsuKimechi/234437376, anikethend1234/234440272. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I know violation of rules of contest is not good. But i fact i have not done any kind of such thing.But yesterday i notice that the guy you talking about had used my CP template and code before this contest also. He used my CP template i the same contest also(you can check my previously solved solutions for reference).I think I have not done any kind of voilation of rules. Please check into the matter once.
Does anyone have any idea why this dfs fails pretest 6?
Please refer to the solve() function. https://codeforces.me/contest/1900/submission/238214972
probably it overflows or something
For C what is worong ``` ll ans = 1e8, n;string s; ll l[maxn], r[maxn];
void dfs(ll v, ll op = 0){ if (l[v] == -1 && r[v] == -1) ans = min(ans, op); if (l[v] != -1) dfs(l[v], op + (s[v] != 'L')); if (r[v] != -1) dfs(r[v], op + (s[v] != 'R')); }
void run(){ cin >> n >> s; for (int i = 0 ; i < n ; i ++){ cin >> l[i] >> r[i]; l[i]--;r[i]--; } dfs(0); cout << ans << nl; }
```