rachitiitr's blog

Introduction to my Blog
By rachitiitr, history, 7 years ago, In English

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!

  • Vote: I like it
  • +70
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thank you !! it will be very useful

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, that will work too. Good work!

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      for i = 1 to n:
  height[i] = height[i-1] + 1 if a[i] > height[i-1]
  height[i] = min( a[i], height[i-1] ) if a[i] <= height[i-1]

      Now with 2 pointers technique:

      i=j=1;
while(j<n):
  while( height[j] > height[j-1] )j++
  ans[i++] = height[j-1]
while(i<n)
  ans[i] = ans[i-1]-1
  i++
      → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Great initiative and it will be very helpful.

→ Reply
»
7 years ago, # |
  Vote: I like it -11 Vote: I do not like it

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

→ Reply