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(N2 / 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) :)