Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

techgig0's blog

By techgig0, 7 months 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

»
7 months 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")

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

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

»
7 months 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 .

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

  • »
    »
    7 months 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?

    • »
      »
      »
      7 months 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.

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

this problem is identical to Subsequence Reversal

»
7 months 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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone please share the approach for the 1st problem?

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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?

      • »
        »
        »
        »
        7 months 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.

        • »
          »
          »
          »
          »
          7 months 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.

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

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

            • »
              »
              »
              »
              »
              »
              »
              7 months 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.

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

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

      • »
        »
        »
        »
        7 months 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.

        • »
          »
          »
          »
          »
          7 months 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

»
7 months 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

»
7 months 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

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

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

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

      for the subsequence reversal problem Approach?