techgig0's blog

CodersBit 2019 Finale Discussion
By techgig0, 5 years ago, In English

Since the problems of the contest were pretty good, I think it needs a dedicated blog for post contest discussions. Please share the problems in comments as I haven't read all the problems(or provide screenshots).

One of the most interesting problem was: Given an array of $$$A$$$ of size $$$n$$$, you are allowed to reverse a subsequence atmost one time. You have to output maximum non-decreasing subsequence in the final array.

Constraints : $$$1 \leq n, A[i] \leq 50$$$

Sample Input Sample Output
5
45 28 45 3 48		 5

LeaderBoard

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

Comments Comments (20)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

did the contest end ? (it's written in scoreboard "It's ongoing contest")

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

Any hints for P3 , the tires problem ? I am thinking it to be dp but cannot think of the states .

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

    I did like, $$$dp[i][j]$$$ means starting from $$$i$$$ and covering $$$j$$$ holes continuously what is the minimum length I need. Try to think about it this way. My solution Time complexity was $$$O(n^2mlog(n))$$$

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

    I have used the same logic for 3. You can check out the code here.

    How to solve 2?

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

      For 2 I use disjoint sets union. Rather than removing the nodes from graph build the graph from last.

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +30 Vote: I do not like it

this problem is identical to Subsequence Reversal

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

Interviewbit has one of the shittiest coding environment, also I have seen their most contests have questions picked from different contests over the internet. Nothing good about them.

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

Anyone please share the approach for the 1st problem?

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

    AFAIK, It was the last problem from the last year's codersbit, which no one managed to solve last year. But people did manage to get partial points, using Markov Chains or something.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I came up with an observation that the paths of length more than 25 will not contribute much to the answer because the accuracy required is $$$1e-5$$$. Now we can use dp to get the probability of a particular recruiter to reach a cell after some x (<= 25) steps. But I didn't manage to debug this code. Does this seem right?

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

        I left the contest after solving 1 problem. So, I have no idea whether anyone solved it this year or not. But last year, no one solved it completely and the editorials weren't released either.

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

          No one solved it completely this year also. But many managed to get some partial points using some logic. It would be nice if someone can share the logic of their partial points.

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

            I solved using dp to get partial points... dp[i][j][k] is probability to reach (i,j) after k steps from a recruiter.. Just did k upto 300, it gets tle after that

            The intended solution is using markov chain(some gauss elimination).

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

              Every path of length k will have a probability of $$$\frac{1}{4^{k}}$$$ isn't it? If so, why is length up to 200 even required when the required accuracy is only $$$1e-5$$$?

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

              What is the intended solution? You can't have n*m number of variables i guess. Can you share the complete approach.

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

      LOL. So, why they gave this year as well ;P

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

        Because no one solved it completely last year xD. And considering no one solved it this year as well. They will probably give it next year too xD. But, I think that should've provided advantage to the people who got high partial scores on it the last time.

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

          Exactly! It should be removed I guess. Actually, it doesn't matter xD

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

you can look for the code to a similar USACO problem here.

Problem

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

Solution for Subsequence Reversal: http://www.usaco.org/current/data/sol_subrev_platinum_jan17.html

→ Reply