Codeforces Round #722

Hi Codeforces!

Dio, Keshi, Tet, alireza_kaviani, Davoth, AliShahali1382 and I are delighted to invite you to participate in Codeforces Round 722 (Div. 1) and Codeforces Round 722 (Div. 2), which will be held at Monday, May 24, 2021 at 14:35UTC. Each division will have 6 problems and 2 hours and 15 minutes to solve them.

The curse has finally been lifted! We are proud to announce that antontrygubO_o didn't reject even a single task from the Div. 1 part!

Huge thanks to the following people:

• antontrygubO_o for being an outstanding coordinator; This round wouldn't have happened if it weren't for him.

• Our ever-growing army of testers gamegame, Amoo_Safar, Atreus, dorijanlendvaj, aarr, Monogon, EnEm, N.N_2004, AaParsa, _Seyed37_, Roham, Clix, Narut, SinaSahabi, sinamhdv, arvindr9, shokouf, munghatekartik, Ali_Tavakoli, vodacbaoan, Shahraaz, -Suto-, coderz189, kassutta, the_borono, saarang, iANikzad, Etherite and -this-is-obd- for testing the round and providing invaluable feedback.

• MikeMirzayanov for the amazing platforms Codeforces and Polygon!

• Last but not least, to all the participants of this round!

For the sake of having short statements, this round does not have a theme. The characters featured in the statements are: Soroush (Tet), Sifid (Davoth), Parsa (Dio), Nima (N.N_2004), AaParsa (AaParsa), Haj Davood (davooddkareshki), Kavi (alireza_kaviani), Keshi (Keshi), Mashtali (AliShahali1382) and AmShZ (AmShZ).

Please read all of the problems and their notes, enjoy your time and solve as many as you can! Good luck have fun to everyone!

The scoring distributions will be announced later.

UPD: Here are the scoring distributions:

• Div. 1: 750 1000 1750 2000 2750 3000

• Div. 2: 500 1250 1750 2000 2750 3000

UPD: Editorial is out!

• 2 years ago, # ^ | Thank you for your contribution.

• 2 years ago, # ^ | "Tet" is Vietnamese traditional new year holiday. :D See you, I think about Tet :D

• 2 years ago, # ^ | what is orz ?

  • 2 years ago, # ^ | ← Rev. 2 →   +40 imagine O as the head of the man bowing , r as his hands , z as the rest of his body . Its used for giving ovation

    • 2 years ago, # ^ | woahhhh. thanks man

• • 2 years ago, # ^ | Not in this contest :(

    • 2 years ago, # ^ | But its_Atrap

• 2 years ago, # ^ | ← Rev. 3 →   +102 As a tester, I agree with vodacbaoan!

  • 2 years ago, # ^ | As a participant, I agree with you guys:)

• 2 years ago, # ^ | How to be a tester?

  • 2 years ago, # ^ | You should either be friends with setters or have a history of being a setter.

    • 2 years ago, # ^ | It's too hard for me

• 2 years ago, # ^ | Sir, How can I be a tester? :P

• 2 years ago, # ^ | vodacbaoan is the official wife of Monogon. Upvote if u want them to marry.

  • 2 years ago, # ^ | so you have downvote hell. Enjoy

    • 2 years ago, # ^ | Do u have a crush on vodac ?? xD

• 2 years ago, # ^ | Many times I see people commenting it's an Indian round, it's a Chinese round.. etc and now you are saying it's an Iranian round. What difference does it make? I don't think there is some pattern in the problem set associated with the region or something like that.

  • 2 years ago, # ^ | We respect to our compatriots ! :)

  • 2 years ago, # ^ | It's just that participants get excited because they have the same nationality as the authors. Not sure if it's true for Iran, but I guess that some countries have a few problem-setting-eligible users and those users are well-known among the people of that country. Wouldn't it excite you to see an acquaintance of yours set a round?

    • 2 years ago, # ^ | ← Rev. 2 →   0 Agree with you

    • 2 years ago, # ^ | ← Rev. 2 →   +35 I definitely would, but expressing it in that way looks inappropriate. Mentioning country looks like drawing borders to me. Maybe I'm over reacting. Btw thanks for the contest.

      • 2 years ago, # ^ | Nah I feel the exact same way as you. But then again, different people have different opinions and beliefs, so I dont mind it.

      • 2 years ago, # ^ | ← Rev. 4 →   +19 Chinese round: Maths, implementaion,data structure Russian round: constructive, observational Iranian rounds: balanced perfectly Indeed it was balanced perfectly.

  • 2 years ago, # ^ | i will add something about your comment after the contest

    • 2 years ago, # ^ | Hello, what is it?

  • 2 years ago, # ^ | ok as i said there are some few things you can find out when the contest is made by irainian: 1) there are always some graph problem and most of the graph problems are either shortest path or tree problmes 2) there are lots of dp problems 3) there is no complicated greedy problems because most of irainians hates greedy 4) they also hate geometry so you 99% can be sure there is no geometry 5) there are usually hard combinatorics & DS problems these are the things that ive learned because im either student / classmate / friend with them : )

    • 2 years ago, # ^ | "There is no complicated greedy problems because most of Irainians hate greedy" =(

      • 2 years ago, # ^ | there is no complicated greedy problems because most of irainians hates greedy I dont know who likes greedy, atleast no one I know.

        • 2 years ago, # ^ | i like greedy

          • 2 years ago, # ^ | atleast no one I know. I dont know you. :/

            • 2 years ago, # ^ | i still like greedy

        • 2 years ago, # ^ | I love greedy.

• 2 years ago, # ^ | as a no one , sik tir :)))

• 2 years ago, # ^ | as a Participant, I have given you contribution

2 years ago, # | me seeing the contest announcement

• 2 years ago, # ^ | ← Rev. 2 →   0 Frankly, you shouldn't count it as a ghaazzz round. And this way we can still expect a real ghaazzz round.

  • 2 years ago, # ^ | agree.we can't count it as a ghaaazzz round,but as a ghaazzz round.

• 2 years ago, # ^ | Thank you boii.

• 2 years ago, # ^ | Whenever you give a 2hr contest and submit one of those messy problems in the last minute and get WA on pretest 2 and then wish you had only 10-15 minutes more. These are those 15 minutes.

• 2 years ago, # ^ | dblark Google Kickstart(which on Sunday) may be the reason.

• 2 years ago, # ^ | We don't have editing rights yet, it'll be fixed soon.

• 2 years ago, # ^ | None of the them :P

  • 2 years ago, # ^ | ← Rev. 2 →   -33 Which one won the game Div 1? 1) Benq 2) Tourist 3) Radewoosh Guess?

    • 2 years ago, # ^ | He used a very high level technique called "guessing"

• 2 years ago, # ^ | Though codeforces is kinda better, but you can also participate in other online contests. Such as atcoder, codechef and even yukicoder. These websites combined you'll have at least one contest every other day(maybe everyday).

  • 2 years ago, # ^ | Ya , but the happiness of increase in rating on codeforces is of different level. :)

    • 2 years ago, # ^ | ← Rev. 2 →   +3 I agree. The same is true for atcoder, but still not as much as codeforces. Besides, competing is great itself.

• 2 years ago, # ^ | IT WAS ME DIO

  • 2 years ago, # ^ | i dont think so...

• 2 years ago, # ^ | I agree with you

• 2 years ago, # ^ | We are still discussing it :( I'll post them the instant we agree on something ...

• 2 years ago, # ^ | Best of luck! :)

• 2 years ago, # ^ | You have solved 393 problems in 3 months!! Great work bro. All the best!

  • 2 years ago, # ^ | Thanks a lot :)

• 2 years ago, # ^ | It gives you an idea about the level of the problem. Though it is not always accurate but most of the times it is. For example B problem might be a bit hard today as compared to other div-2's B problem but again it might be easy too. You can never tell you can only guess.

• 2 years ago, # ^ | what algorithm did u use to find that out

• 2 years ago, # ^ | you should never skip

• 2 years ago, # ^ | dp on trees, and only $$$l_{i}$$$ and $$$r_{i}$$$ are important in the range.

  • 2 years ago, # ^ | I did exactly the same, still I'm getting TLE!! :(

• 2 years ago, # ^ | ← Rev. 2 →   +3 can solve by dfs. just handle parent and child relation and add every child value with parent then answer is root value. Spoiler

• 2 years ago, # ^ | For those who solved Div2C / Div1A, could you guide why DFS is needed (as opposed to BFS)?

  • 2 years ago, # ^ | Any traversal technique works ig. I solved using dfs though xD

    • 2 years ago, # ^ | Actually I had used BFS, which was incorrect. I think I now understand why. DFS is a must here since the max value of the root node (you can pick any node as root) depends on the max values of its children, which in turn depend on their children, etc. So once it's clear that you have to pick either L or R for each vertex (and no value in between), then it's a matter of solving subproblems first — recursion with DP does that effectively.

      • 2 years ago, # ^ | Yeah, it doesn't I overlooked it. Basically it's like we should find the answer for all nodes in the last level and then the previous level and so on. So we can somehow store answers for higher levels first and then for lower levels using BFS. But we have to store the nodes which are at a particular level and it is implementation heavy. So I think BFS is something like top-down traversal so it's better to use DFS as it's a bottom-up traversal in such cases.

• 2 years ago, # ^ | No its not

  • • 2 years ago, # ^ | Use fast IO in C++ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    • 2 years ago, # ^ | I think the large input gives you TLE. Try using ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); this at the begining.

      • 2 years ago, # ^ | You mean to say the reason it's TLE has got nothing to do with the logic?? It was due to slow I/O?? I'll cry the whole night today :(

        • 2 years ago, # ^ | Yeah but all of us got TLE on some problem before this and learned from that to use this "trick". At the end of the day you learned something new so is a good day!

• 2 years ago, # ^ | Because it has O($$$n^2$$$) time complexity

• 2 years ago, # ^ | It happened to me too. Simple O(n) recursive dp. TLE on test 4. I have absolutely no idea why.

• 2 years ago, # ^ | I don't think the first submission even gets run on system tests, so you will still get the penalty.

  • 2 years ago, # ^ | I like meethi lassi and chole bhature.

  • 2 years ago, # ^ | Oh ok, sad

• 2 years ago, # ^ | Only the last submission will be judged against systests. (The first one is given a verdict of 'Skipped' after systests.) You will still get penalty.

• 2 years ago, # ^ | I used dp. categorized the length of pair (L) into two parts: for each n, define f(L) as: if L <= n, only those n % (L-1) == 0 will contribute. I count the frequency of each prime factor of n (p_i) and do a product of (p_i + 1). if L > n, it will be a fully covering case, and the inner part will be dp[L-n-1]. Those can be calculated use prefix sum. so each dp[n] = sum_{L=2}^{2n} f(L). I'm not sure if this is good for system test, and sorry for the brevity of the description

• 2 years ago, # ^ | ← Rev. 2 →   +9 Very hard to demonstrate without paper. [...] [...] Suppose those two arches have the same length. Then we know nothing can belong inside of both of them, as each subarch isn't inside of the other (place inside of the left, not inside of the right), etc. And because the subarch must be smaller, then neither condition can be satisfied. Now, we know that must be a be a thick arch. Like for example, an arch of "thickness" 2 cross weaves 2 archs, if you know what I mean. And now you can place subarchs inside, this gives a relation dp[i] = sum of all j <i dp[j]. Since there is only one unique way to place this thick arch (otherwise it because multiple archs of varying sizes, but you just want that 1 thick arch). This thick arch can be anywhere from 1 thickness to the entire rest of the length so that's why we go for all j<i. The tricky thing is to handle the no-archs case, where all lengths are equal and you can place them wherever. The answer turns out to be the number of divisors of the number, though I have no idea why (I saw the potential pattern but no proof as to why it works), but proof by AC I guess. So add on the number of divisors at the end of every precalculation DP. And because it's prefix sums just keep a running prefix to add on every time.

• 2 years ago, # ^ | Hints on problem C, please.

  • 2 years ago, # ^ | I used DP actually. Try to solve the problem (maximum sum) for each subtree. And for each node u, you can calculate what the result will be if you use the left or the right. The transition for one node using its left value will be dp[u][L] = max(|l[u] — l[v]| + dp[v][L], |l[u] — r[v]| + dp[v][R]) Let me know if you need more spoilers

    • 2 years ago, # ^ | I'll try. Thanks!

    • 2 years ago, # ^ | ← Rev. 2 →   0 Solved it! Also learned a new way to implement DFS from your submission. Thanks a ton. Edit: Will this implementation work on any graph or is it exclusive for trees?

      • 2 years ago, # ^ | Hi there I learned this from https://cp-algorithms.com/graph/depth-first-search.html :) I think the one I submitted only works for trees since it only checks whether the parent has been visited or not. You may an extra visited flag to work with general graph.

• 2 years ago, # ^ | The second one is scored.

  • 2 years ago, # ^ | I understand the rule right now but I wanna know the rationale behind this rule. Why don't it count the first correct submission that able to pass the system testing.

    • 2 years ago, # ^ | If you want the first to count, then there is no need to submit the second. So, you decide.

      • 2 years ago, # ^ | It's just because I didn't know this rule before this contest. I would definitely not do it again in the future contest. Btw I resubmitted it just because the second one has a higher chance to pass the system testing.

        • 2 years ago, # ^ | Then isn't that a valid a reason to not consider your first submission ? As you were not confident that the first one would pass the final test cases and modified it to pass the system cases. I think its kinda synonymous to getting a WA and then debugging and resubmitting the correct solution .

• 2 years ago, # ^ | In case of multiple correct submissions (for same question), only latest one is considered. All previous submissions get skipped and don't appear in system testing.

• 2 years ago, # ^ | DP and number theory is enough.

• 2 years ago, # ^ | It took me more than 1 hour to solve D, whereas less than 10 mins to solve C...

• 2 years ago, # ^ | I guess you also thought that subsequence must be continuous.

  • 2 years ago, # ^ | No, I think I understood the promblem correctly. But there seems to be some more or less obvious observation needed that is invisible to me. From other submission it seems that we can use all negative numbers (ok, understood), and then all positives up to the first bigger than the smallest diff so far. But why, why cannot be there ohter solution? Or did I get it wrong?

    • 2 years ago, # ^ | ← Rev. 2 →   0 Have you considered the case when any element <=0 is repeating twice? This has caused me 5 wa and 40 minutes.

    • 2 years ago, # ^ | Note that the difference between two positive numbers is strictly smaller than the larger of the two numbers, so any solution can have at most one positive number. On the other hand, we can take as many non-positive numbers as we like. So the question really only is about whether we can take a positive number in addition to the non-positive ones, which is possible iff a positive number at most as large as any difference between the non-positive numbers exists.

      • 2 years ago, # ^ | "...so any solution can have at most one positive number." Ok, thanks, that is the missing observation. What a stupid problem :/

        • 2 years ago, # ^ | Indeed, it was stupid.

        • 2 years ago, # ^ | I found B to be hard to understand, not from the language, but from the definition of the promblem itself. I had to read the definition of a strange seq at least a dozen times, and actually now I am hardly able to tell from head (just did read it again some seconds ago). So, basically that problem is "somehow get that wiered definition into your head, then you will quickly see the solution." I am ok with a complecated, or strange definition if it is a complecated problem. But a very simple problem with a complecated definition is a bad problem.

    • 2 years ago, # ^ | You can see that there can be at most one positive integer and all others are 0/negative and their minimum abs difference must be greater than the positive number so we choose least positive number. If that number is still greater than minimum abs difference we remove that number. Since we are taking all nonpositive integers there can't be another solution. If we remove some negative integer to increase difference, ans will be less than number of nonpositive integers.

    • 2 years ago, # ^ | Problem Div2B was constructive at best, it felt like you cater to the observation required and it should work. I am also curious about other approaches as well :)

• 2 years ago, # ^ | You can prove that there can be at most 1 positive number. Then it's easy. Take all negative + zero numbers or take the smallest positive number also. For the second choice check whether it is possible.

• 2 years ago, # ^ | ← Rev. 2 →   0 i tried with 5 case and take the maximum. 1. all zero and all negative. 2. only one zero and only one positive 3. only one positive 4. all negative and one positive (for taking positive and negative at a time check minimum of positive >= max difference of any 2 negative numbers) 5. all negative and one zero and one positive (And taking all pos, neg and zero checked minimum of abs(negative value) >= min positive value and must checked 4 condition also) And taking all pos, neg and zero checked minimum of highest negative value >= min pos value and

• 2 years ago, # ^ | ← Rev. 2 →   0 Very easy solution: SPOILERS

• 2 years ago, # ^ | Was your code $$$\mathcal{O}(nm)$$$? Because even $$$\mathcal{O}(nm \log n)$$$ passes in less than a second: 117224037

  • 2 years ago, # ^ | 117252128 mango_lassi I think it is O(N^3) or O(NM) if you like, I will take a look again.

    • 2 years ago, # ^ | Looks like $$$\mathcal{O}(N^3)$$$, so I guess the constants are just too high. Kinda sad if they were trying to cut $$$\mathcal{O}(nm \log n)$$$ and this happens :(

• 2 years ago, # ^ | It doesn't, consider this code : Link

  • 2 years ago, # ^ | I guess I am just unfortunate.

    • 2 years ago, # ^ | ← Rev. 2 →   +5 I think you can avoid re-computation using deque by doing it before only and storing it?

      • 2 years ago, # ^ | ← Rev. 2 →   0 Yep you are right. But you wrote in the smart way (avoid recomputing) and still took almost two seconds, which suggests that the deque solution probably has a large constant factor. Considering that most people's submissions ran in 1~2s, I think there is a good reason that I avoid unnecessary deque next time. Still, thank you very much for your suggestions.

• 2 years ago, # ^ | mango_lassi 117254437 Didn't use deque and simply passed, but still used more than one second though.

  • 2 years ago, # ^ | Wrong submission? That's a solution to div2A

    • 2 years ago, # ^ | ← Rev. 2 →   0 Oh sorry, this one 117255437

    • 2 years ago, # ^ | ← Rev. 2 →   0 I will take a look at your solution... less than one second is interesting.

• 2 years ago, # ^ | You can do it by iterating for each number from 1...n by its multiples. 1,2,3,4,.... 2,4,6,8..... 3,6,9,12... . . k, 2k, 3k... . . n it's very similar to sieve. This has complexity NlogN

  • 2 years ago, # ^ | Yeah, very stupid of me being unable to find such simple algorithm given that I had used this before more than once

• 2 years ago, # ^ | Can you explain the basic idea of how to solve D.

  • 2 years ago, # ^ | @dhruv7888 It can be solve by DP. Ex, N = 3: dp[3] = dp[2] + dp[1] + dp[0] + number of diviors of 3 Because when you know all the good pairs of N = 2, to form good pair with N = 3, you can add a pair bound all pairs with N = 2, similarly add 2 outside pair to N = 1 ...

• 2 years ago, # ^ | If you have factorisation in form $$$n = \prod p_i^{a_i}$$$ then number of divisors is equal to $$$\prod (a_i + 1)$$$. Factorisation can be done pretty quickly by precomputing all primes, or just using linear sieve.

  • 2 years ago, # ^ | Thank you, the factorisation is really good idea, I have leant new thing. What the time complexity of the factorisation? Does Linear sieve mean that iterating for each number from 1...n by its multiples? And it will take O(NlogN)?

    • 2 years ago, # ^ | ← Rev. 3 →   +1 https://cp-algorithms.com/algebra/prime-sieve-linear.html What the time complexity of the factorisation? Either $$$O(primes < \sqrt{n})$$$ or O(prime factors of n) depending on what you use. Both should pass pretty comfortably.

• 2 years ago, # ^ | for (int i=1; i<=n; i++) { for (int j=i; j<=n; j+=i) { factor[j]+=1; } }

• 2 years ago, # ^ | Yes. I used dp[i] = pref[i — 1] + number of Divisors of i.

• 2 years ago, # ^ | My B failed (-_-)

  • 2 years ago, # ^ | but congo on solving C and D :)

• 2 years ago, # ^ | Observe that foreach vertex it is allways optimal to use either l[i] or r[i], never some value in between. Root the tree somewhere, do a dfs. Result of the dfs is foreach vertex the max value we can get if we used l[i] or r[i] for that vertex. To find the two values for the current vertex, find the values for all adj vertex, then try both values and record the max value possible.

  • 2 years ago, # ^ | can u explain more?

    • 2 years ago, # ^ | Can you give feedback in a way that I have sufficient information to write an answer fitting your needs?

• 2 years ago, # ^ | Use map<> instead of unordered_map

  • 2 years ago, # ^ | still getting TLE

    • 2 years ago, # ^ | Actually it's caused by read large amount of data by "cin", in other words, you get TLE because you spend too much time on I/O

      • 2 years ago, # ^ | It means I should use scanf instead of cin, right?

• 2 years ago, # ^ | ← Rev. 2 →   -14 removed

  • 2 years ago, # ^ | Not knowing C++ grammar very well, but: dfs(vector<int> graph[],... is O(1), while: dfs(vector<int> &graph[],... gives CE on my computer.

    • 2 years ago, # ^ | You are right, arrays work like pointers, nothing is copied. So it might be undefined behaviour caused by negative value of parameter p which is used as array index.

    • 2 years ago, # ^ | Can you help me to findout why I am getting TLE ?

• 2 years ago, # ^ | ← Rev. 2 →   0 deleted

• 2 years ago, # ^ | I hate it how cf will timeout even with the correct time complexity. I gave up the problem after 2 submissions knowing the time complexity is correct for my solution and I just need to define my variables globally I gave a google interview and the interviewer asked me not to declare variables globally but pass it by reference

  • 2 years ago, # ^ | Defining your variables globally is not the issue; you TLE because your IO is too slow. Adding cin.tie(0)->sync_with_stdio(0); to your code gets AC (scanf/printf would probably also pass).

• 2 years ago, # ^ | observe observe observe.

• 2 years ago, # ^ | ← Rev. 2 →   +1 define int long long gang

  • 2 years ago, # ^ | sometimes it will cost a TLE :)))

• 2 years ago, # ^ | Lol man, exactly what happened to me. First time I solved DP problem in a contest, first time I solved C in division 2. Lesson learned man, I changed my template to replace ints with long longs by default now. I do not want this to happen again, feels really bad

  • 2 years ago, # ^ | Lol same, first time dp, first time problem C!

• 2 years ago, # ^ | the simplest solution I found is take all -ve and all 0, then try to take as many +ve as possible

  • 2 years ago, # ^ | You can take atmost one positive

• 2 years ago, # ^ | Simple solution is to take all the non-negative numbers. After that, it is pretty easy to observe that we can take almost one positive number. So start by finding the minimum difference in the non-negative elements already selected and try to pick a positive number greater than or equal to the minimum difference. I observed this after solving a few cases on paper.

• 2 years ago, # ^ | I used a binary indexed tree to check if a given vertex has any marked descendants, and a link cut tree to find the deepest marked ancestor of a given vertex. 117214561

• 2 years ago, # ^ | I used just a set. If you run a euler tour on the second tree and map each vertex to a segment, it's equivalent to finding the longest subsequence of vertices on the first tree such that none of their segments intersect, and the subsequence is part of a path from the root to some vertex in the first tree. Basically you store a set of all the segments that you take from the root to a parent of a vertex; when scanning the vertex in, check if a segment intersects it in the set. If it does, remove that (because it's never optimal to take a larger over smaller segment if both intersect, and if two segments intersect, one must completely overlap the other since it's from a euler tree). Then, add the segment belonging to the current vertex in the set. The answer is the maximum size of the set at any time.

• 2 years ago, # ^ | ← Rev. 2 →   +3 The only data structure I used was a set. If you record the in and out times using DFS in the second tree, we have each node in the first tree is labeled with an interval $$$[in, out]$$$. We want to consider all intervals on a path from the root to a leaf, and try to find the largest set of nonintersecting intervals. But since the $$$[in, out]$$$ intervals either don't intersect or contain each other, we can simply use a set to do this. Submission

• 2 years ago, # ^ | ← Rev. 2 →   +5 Say you choose some value a such that l < a < r, and you've already chosen some value b for another node. If a ≥ b, then adding 1 to a will increase |a - b|. Otherwise, subtracting 1 will increase it. You can keep adding/subtracting until you get to l or r, and get a max value.

• 2 years ago, # ^ | Consider $$$v[i]=l[i]+1$$$ to be a better solution than $$$v[i]=l[i]$$$ Then this is because there are more adj vertex with $$$v[adj]<v[i]$$$ than there are with $$$v[adj]>v[i]$$$ If this is so, then $$$v[i]=max(l[i],r[i])=r[i]$$$ is true, by induction.

• 2 years ago, # ^ | ← Rev. 2 →   -15 I think vector is not as fast as array for n > 1e5 :)

• 2 years ago, # ^ | C is a cool problem, but for me, D is just a very straight-forward problem as it is just a very simple shortest-path problem.

• 2 years ago, # ^ | Nah, you are correct, E is just a counting problem where zero computer science is involved. Not sure if that is the case for F, but really, 3 counting problems in a single round?

  • 2 years ago, # ^ | thats fine, did you notice there were 4 graph problems and 3 of which were trees!

    • 2 years ago, # ^ | Are you counting E as a graph problem? I wouldn't. C was a nice problem though :)

• 2 years ago, # ^ | thanks mike

• 2 years ago, # ^ | ← Rev. 3 →   +1 thanks mike

• 2 years ago, # ^ | Weak test cases on problem div2 B, solutions are getting Wrong answer on:

• 2 years ago, # ^ | Come on! Let me become purple it's just a single point! :"( My curve does have limit in 1899!!!. Wish to become candidate for the first time after removing cheaters :)

  • 2 years ago, # ^ | wish to see you in red babe ツ

• 2 years ago, # ^ | Foreach group of i pairs we can build "packs" of size k if k divides i. So, that number contributes to the solution. Also, we can pair the 2,4,6,... outermost points in combination with the previously calculated result for the i-2, i-4, i-6,... inner points (see third picture of examples). So we need to add up these prefix sums. 117249412

• 2 years ago, # ^ | ← Rev. 2 →   +5 the approach for this problem is bottom-up, which means that you need to solve DP for the leaf nodes, then accumulate to the root node I think it's more convenient and makes more sense, and DFS is often used for DP-on-tree problems

• 2 years ago, # ^ | You should do a bottom-up dp which can be done with either dfs or bfs, but dfs is easier to implement.

• 2 years ago, # ^ | Read Problem And Go To Editorial :)

• 2 years ago, # ^ | You are assigning lr vector inside a loop so overall its N^2 complexity

  • 2 years ago, # ^ | UMM no since its the sum of values of n, which is fixed

    • 2 years ago, # ^ | 117259248 Ur code works with moving the assign out of the loop

      • 2 years ago, # ^ | Oh yeah I'm blind... Thanks

• 2 years ago, # ^ | For reference, here is an example of a DFS solution that fails at the 1 second mark

  • 2 years ago, # ^ | ← Rev. 10 →   0 Honestly even an badly optimized C++ O(n) solution doesn't go through, once I used vectors with assign and once plain arrays and one passed but the other did not: https://codeforces.com/contest/1528/submission/117194884 https://codeforces.com/contest/1528/submission/117196442 EDIT: NVM stupid mistake

    • 2 years ago, # ^ | Yikes. That's unlucky.

      • 2 years ago, # ^ | nvm, I just made a stupid mistake (actually squared complexity lol)

• 2 years ago, # ^ | Number of divisors will be the count of ways to make i segments of equal length. Where length of each segment would be divisor of i.

• 2 years ago, # ^ | You can have at most one positive element in a strange sequence. let a and b be positive integers, then max(a , b) > |a — b|, thus [a , b] is not strange.

  • 2 years ago, # ^ | in this input |1-0| = 1, |0-1| = 1, |1-1| = 0 and the max element is 1..

    • 2 years ago, # ^ | ← Rev. 2 →   0 No, as you've mentioned |1-1| = 0 which is smaller than the maximum element which is equal to 1 so it's not strange ...

• 2 years ago, # ^ | Found the mistake, I always make a stupid mistake when making larger programs ;((((((

• 2 years ago, # ^ | I Give it to you :)

• 2 years ago, # ^ | ← Rev. 2 →   +5 .

  • 2 years ago, # ^ | Sadly king of memes only XD

    • 2 years ago, # ^ | rainboy: Rainfall from Thermosphere. Jhin: Rainfall from Stratosphere. Me: Evaporation still underway. Image for reference :)

• 2 years ago, # ^ | Don't quit.Just keep going

  • 2 years ago, # ^ | I will keep going but not like that I'm done participating in rounds without practicing in other days that's stupid ..

• 2 years ago, # ^ | No, why?! eshag is eshag and it's pronounced as eʃæg.

• 2 years ago, # ^ |

• 2 years ago, # ^ | People usually ask "is it rated?" before the round not after it ... In any case, yes, it is rated.