Hi CF Community,

Here is my blog rachitiitr.blogspot.in.

I have started to write about the interesting problems I encounter during contests. Interesting means really interesting, the problems that kept me thinking for hours or those having beautiful solution worth mentioning.

After explaining the underlying concept and solution, I usually also attach the code at the end of post.

So if you are bored and need a place where you can find good problems, see how they were solved, learn something new, you should check out the posts I make on the blog.

I suggest to read one post everyday before going to bed. Also people in DIV2 can certainly learn a lot by reading the posts. I have **5** posts as for now:

1. A Hard Combinatorics Problem

2. A Longest SubArray Problem

3. A Greedy, Math Problem

4. A Connectivity Problem on Directed Graph

5. A Hard Problem on Bit Logic **(NEW)**

I will try to be as active as possible.

Cheers!

Thank you !! it will be very useful

I'm curious about the 3rd problem. What if I write 1 'a' times, 2 'b' times, and so on. I will binary search on 'a' so it's <= N, and as the number of subsequences = aC2 + aC4 + ...., therefore, a can be very small, I mean 'a' can be as small as 30 to take up almost 10^12 subsequences. Once I've found the maximum 'a', I go to 'b' and so on. We see that a sequence like 111112223 will never have good subsequences involving more than one label, ie: 1122 is not good.

Is my approach wrong somehow?

Yes, that will work too. Good work!

I feel problem 2 has similarities with Snackdown 2017 snake temple problem.

Now with 2 pointers technique:

In "A connectivity problem on directed graph", you can use bitarray (not bitset) — 64bit integer array that contains all true/false element in binary notation. You can express 64 true/false value in one 64bit integer.

So this problem can solve in

O(N^{2}/ 64). My solution of City Construction is here, and it passed in 0.14s.Great initiative and it will be very helpful.

go on, i'm hungry and want to eat DP(good and unique ones) :)