techgig0's blog

By techgig0, 4 weeks 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

»
4 weeks 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")

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There must be a bug. The contest has ended 1 hour ago.

»
4 weeks 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 .

  • »
    »
    4 weeks 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))$$$

  • »
    »
    4 weeks 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?

    • »
      »
      »
      4 weeks 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.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +30 Vote: I do not like it

this problem is identical to Subsequence Reversal

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone please share the approach for the 1st problem?

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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?

      • »
        »
        »
        »
        4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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.

          • »
            »
            »
            »
            »
            »
            4 weeks 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).

            • »
              »
              »
              »
              »
              »
              »
              4 weeks 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$$$?

            • »
              »
              »
              »
              »
              »
              »
              4 weeks 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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

please! answer the subsequence reverse problem . i am not able to get the solution

»
4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    can anyone explain me the approach.thanks! in advance.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      for the subsequence reversal problem Approach?