Can you explain a little bit how the maximum number of distinct values is sqrt(n)?

Can you explain a little bit about how the maximum distinct value of a[i]/i will be less than 2000 always. Did you get this value 2000 by checking for some big test cases,or, is it some intuition based. Please tell me what I am missing.

Thanks

Thanks a lot.

Yes, but still my code got AC.I think while checking our code, they have corrected it.

How to solve P6.I was thinking like some sort of bitmask dp but couldn't go too much.

Can anyone please check why my this solution for problem E using dijkstra gets TLE on test case 8.I have not used negative edges and used dijkstra for each row separately.

Link to my submission:- https://codeforces.me/contest/1627/submission/144133636

Take a break for 2-3days.Do nothing just explore your true self. Maybe watch some different type of content. Try to find the meaning of your life. It helps. Always remember that one day all of us will die. So, there is no point in being depressed for something you wanted. Instead be grateful for what you have and do thing you enjoy.

Thanks.

You can see my solution:-> https://codeforces.me/contest/1625/submission/142628388 I have provided necessary comments to make it easy to understand.

What I did was that I separated the elements into two groups. Group 1:- contains those elements which don't have their mannequins and they are also not part of someone else's mannequin. Group 2:- Contains those elements which don't have their mannequins but are part of someone else's mannequin.

For example for this testcase:- 3 6 1 0 0 0 Grp 1:-
4 5(mannequin)
4 5(element)

Grp2:- 2(mannequin) 6(element)

Now, let's say there are i elements in total who don't have their mannequins. And same elemets which belong to grp 1 and diff(i-same) elements which belong to group 2.->refer to my code .

le's define dp[i][same]->answer in which there are i elements who dont have mannequins out of which same elements belong to grp1. now,we can make transitions like dp[i][same]=dp[i-1][same-2]*(same-1)(case in which an element of grp 1 is paired with an element of grp1 only)+dp[i-1[same-1]*(diff or (i-same))(case in which an element of grp 1 is paired with an element of grp2). There are some minor implementation details(for handling edge cases). You can refer to gfg blog finding derrangements using dp for better understanding. Link:- https://www.geeksforgeeks.org/count-derangements-permutation-such-that-no-element-appears-in-its-original-position/

I solved the problem Hopscotch using dp. If anyone is interested, you can refer to my submission:- Link:- https://www.codechef.com/viewsolution/55287667

Any hints for Rain the pain problem?

Problem D is pretty amazing. Loved to upsolve it.

Thanks bro. Got it.

Thanks bro!.

Can anyone explain/give a proof of the formula for the number of ways to distribute <=n identical numbers into r groups in the editorial of Magic Weed. During contest, I was not able to figure this formula and was only able to solve it in O(n^2)(tle's). Formula:-C(n+r,r).

Can anyone tell how to get rid of MLE in test 4 in problem F. Link to my submission:- https://codeforces.me/contest/1607/submission/134177362

I used Kosaraju's algorithm and then did dp in the condensed graph.

How to solve C?

Any similar problems like problem G? I really liked the idea.

In problem G ,we are maintaining the relative position of the start with respect to the left and right boundaries, not the actual position of start. So, if in any case we are going to cross the leftmost boundary of our segment, we would be assuming that leftmost point(<0) as the new leftmost boundary and start also.
That's why we are always maintaining 0 as the leftmost boundary and never crossing that. You can watch galen_colin's stream to get a better understanding. Link:- https://www.youtube.com/watch?v=JRuAgCCwi0M

In the dfs function, what I am doing is that I am going to each node of the trie. Now, this node represents a banned prefix. Now for this banned prefix I will choose the maximum value for the next index such that the sequence doesn't become banned(in my code it is done using the x variable inside dfs function). For the remaining indices ,I am just taking the maximum (stored in the suff vector).The now vector stores the current prefix(banned obviously). Hope it helps.

Basically ,what I am trying to do is that go to every prefix which is banned. Now let's assume till index x-1 you have taken the banned prefix. Now, for the index x, you will choose the largest possible value which can be taken for that particular index, such that that the prefix upto index x is not banned. Once you have taken that, for the remaining indices, from x+1 to n,you can just take the maximum value among all possible values for each of the indices (x+1 to n).

My solution to problem D using trie data structure. First of all construct a trie of the banned combinations. Now we will be iterating over each banned prefix(using a dfs on the trie) and take the remaining values the maximum possible. Here is my submission. Hope it helps someone. Submission:- https://codeforces.me/contest/1574/submission/129429122

Same here.

I have a little better solution of B, which is less guessy and more easy to come up with.

1) Firstly if there is 1,4,6,8,9-> then you already got your answer.

2)Now, your string consists of 2,3,5,7 only. Now, if your string contains repeating characters, we are done since 22,33,55,77->all of them are divisible by 11.

3)Now since there are no repeating characters up till now, the maximum length of your string can be at most 4.(since contains only 2,3,5 and 7).So you can brute force to check all possible combinations in 2^4=16 steps.

4) I think this solution is better if there can be cases in the problem in which the answer doesn't exists.

GuessForces

Auto comment: topic has been updated by Fearless_cod (previous revision, new revision, compare).

Auto comment: topic has been updated by Fearless_cod (previous revision, new revision, compare).

Is problem E related to counting inversions? I think I was close to the idea but couldn't implement it on time xd.

Got it. Thanks for the reply.