Following

Why don't u visit ur recent contests and upsolve the easiest unsolved problems? :-)

yes. I agree brother. This is a very good way to keep busy. Happy Coding. :D

Obviously, what could be a better way to spend time ? ;)

Why ? be greedy ... I want at least 7 contests per weak ... (in the rest of the day Ill upsolve the contest)

In the resulting scoreboard, participants are compared first by the number of solved problems, then by the total penalty time — for every solved problem, it is the time taken to solve it (in minutes) and 10 minutes for every unsuccessful submission on it.

Why don't you ask him? How would others know his configuration?

have a look at the other people's dotfiles (.vimrc to be specific) in github

I found that even orginal 1500 rating is hard to reach.:(

CSP...

we ain't got nothing to do

You could always practice previous contests...

(That's very dangerous! Keep yourself safe and don't get killed during this contest)

https://codeforces.net/blog/entry/65477

Maybe you are expected to be an expert

Improve your spelling and everyone will expect you to be an expert

such a bold statement

Not for the ones who don't get to take it.

Because all are home quarantine and love coding.

YUP

It was dp, and I really liked the problem; something unique. I don't think I can explain more, since my own solution was very messy. Hope the pretests were strong.

I tried to do it using LCA, but my solution gave WA on test 56.

Yes.

The observation is that all the parents of the nodes in a query has to be in the same path.

So find the parent of each node in a query and check if they are in the same path from root using LCA.

I used LCA, and passed it.

I only consider 4 situations:

1. all elements are the same : (1 color)1 1 1...

2. the length of the elements is even : (2 colors)1 2 1 2...

and now we just need to think situations where the length of the elements is odd

if t[1]==t[n] then: 1. (2 colors)1 2 1 2...

else if t[1]!=t[n] and at the same time there exist one i(1<=i<=n-1) where t[i]==t[i+1] then:

1. (2 colors)1 2 1 2...

2. otherwise: (3 colors)1 2 1 2 ... 3

Think greedily. Try to use minimum number of colors to color figure 1 upto n-1(you can color these n-1 figures maintaining all constraints using 2 colors only) and then think is you can color figure n with a color already used. If not then give it a new color!!!

Try using m1.codeforces.com next time, I sent all my submissions from there with no problem (while I couldn't submit sometimes from www.codeforces.com)

If you like graphs you can see it is a coloring problem. Your vertices are the different animals and there is an edge between them if they are of a different type and adjacent. Now you want to color this graph, such that all adjacent vertices have different colors. This gives you three cases: 1. If the graph has no edges (ie only one type) you only need one color

1. The graph is not a cycle, then you need two colors, since you can just color any path as 1212...

2. The graph is a cycle, then it is important whether it has an odd or a even length (if you are interested how this generalises look up bipartite graphs)

If the length of the cycle is even, then you can't color it in a 1212...1 fashion, since the first and the last edge would have the same color. Therefore you need three colors and can color it like 1212...23

If the length of the cycle is odd than you only need two colors and can color it like 1212...2

I hope that is understandable :)

If there is only $$$1$$$ type of animal, then the answer is $$$1$$$ color. We can simply print $$$1$$$ $$$n$$$ times.

If $$$n$$$ is even then the answer is $$$2$$$. We simply print alternating $$$1 2 1 2 . . .$$$

So, we are left with the case when $$$n$$$ is odd. If we can find any $$$i$$$ such that $$$type[i]=type[i-1]$$$(cycle included, i.e. $$$type[0]=type[n-1]$$$) then the answer is $$$2$$$, as the parity can be switched. Otherwise, the answer is $$$3$$$.

To print the colors with answer $$$2$$$, you can alternate $$$1$$$ and $$$2$$$ with the exception of $$$i$$$ where $$$type[i]=type[i-1]$$$. Put that as the same color. This changes the parity.

If all elements are same, answer is 1 If all elements are distinct and number of elements is odd, answer is 3 otherwise answer is 2

if all are distinct, simply print 1 2 1 2 ... like this otherwise take every segment containing distinct elements and fill it by 1 2 1 2... those are left, give any colour to them

By observation it can be seen max distinct color required will be 3. Now if n is even 1212.. pattern will work if there are more than one number. For all same obvious 1 color will be required. Now for odd n, consider if there are at least 2 contiguous same number in cyclic array in that case color required will be 2 otherwise 3

You can solve D without graphs as well. It can be solved greedily.

1. If n is even, just print "1 2" n/2 times

2. If n is odd but a[0] == a[n-1] print "1 2" n/2 times with an extra "1" in the end

3. If n is odd but there is a point where arr[i] == arr[i-1], then from 0 to i-1 print "1 2" and from i to n-1, print "2 1"

4. If none is true, print "1 2" n/2 times with an extra "3" in the end

Corner Case (it was for me): If all are same print "1" n times.

It was very unique; I loved it. I solved it using dp, but it was very messy.

thanks it was helpful

please can you tell me why using library sorting I am getting TLE but with radix sort it passes my_sub constrain is just n= 2*10^5 so O(nlogn) is fine right the why?

my account is getting logged out without my intervention!!

m3 worked fine

m3 worked for me, I submitted at 1:57

m2 worked fine as well.

I submitted from m2 in the last 3 minutes

It seems, then, that it was m1 which I was unhappy with: I tried both main site and one of m1/m2/m3 (not sure which one).

P.S. Now it's not a big deal :) for me
(managed to submit in practice mode, my solution is wrong).

I used dp as I didn't need to worry about handling all corner cases explicitly XD (P.S. I couldn't think of any corner cases).

Ok, reading j_peters comment above I just found what I was missing. It was a narrow miss and just because I'm dumb >D My fault

1 2 2 3 Ans 2 colours Check this

Why do you believe it is considered wrong?

For those under 1600, like me, yes

Use the lightweight mirror sites. Such errors are to be expected in contests with a large number of participants. After all CF isn't a for-profit company, and can't buy up a large amount of servers unless really necessary.

I had the code for D wrttien with 15 mins to go, but couldn't submit at all. I was finally able to submit in the last minute and it gave wrong answer :(

The mirror sites worked just fine.

Hi, sorry about it. I'm working on performance improvements. But am I right that m1/m2/m3 worked well most time? I explicitly suggested to use them in case of any technical issues, right?

Instead of iterating to find kTH ancestor, precompute LCA(using binary lifting) and rest is same what you are doing.

What I understood in your solution that you're trying to get the depth of every node in the tree, then what else? cause I didn't get the idea of the second part of the code after the BFS call

Actually one can evade writing full-fledged LCA at all. To do this, just notice that you are only interested in parents of the marked vertices. Checking whether one node is an ancestor of the other can easily be done if you use time when DFS enters and leaves the node (tin / tout). AFAIK, there were absolutely no problems with TL with this approach.

Consider position of the left 'b', let that pos be $$$n-p$$$ Then there exist $$$p-1$$$ strings with left 'b' at that position, because you can place the right 'b' at $$$p-1$$$ positions.

Implement a loop counting the number of these strings with increasing $$$p$$$.

for problem D, my solution was this

let the continuous elements form a grp,

if #grps == 1 then all same color

else if #grps is even then only 2 colors (alternate colors) else if #grps is odd and #grps == n then 3 colors

else if #grps is odd and #grps < n then we can do with 2 colors only , we just have to color the last element of a continuous grp (of sz > 1) with a color diff from that of the members of the same grp and continue alternating

but this gave WA on TC2, dont know why