code.degub's blog

CodeAgon 2021 discussion thread
By code.degub, history, 3 years ago, In English

Guys please share your approaches for the problems you solved. How many did you guys solve?

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

Comments Comments (56)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone share the problems?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +22 Vote: I do not like it
    q1
    q2
    q3
    q4
    q5
    q6
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I solved first with Sliding window Maintaining a hashmap of size two for tracking Frequency and checking for additional N/3 minimum Frequency requirement ,

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

        I guess it can be solved by simply checking all substrings of size 3.

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

        It can be solved by checking every substring of length 3 only also, no need to use sliding window.

        Now, question arises why only length 3 , it can be more than that , right?

        So, here is the answer ....

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

          what about abca , you have to check substring of size 5.

          means if there exists two indices(i,j) such that s[i]=s[j] and abs(i-j)<=4 then answer is true(if string size is greater than 3) else answer is false.

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

            NO. abca has 3 different characters in every window so no golden string.

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

              oh yes i forgot this condition.

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

            There is a condition that golden string should contains exactly 2 distinct characters. So, checking only substrings of length 3 will work

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

          It could be also proved by let's say there exists a golden string of length>4 that is golden than it will surely contain {i,i+1} such that si != si+1

          and therfore{i-1,i+1} or {i,i+2} substring will also be golden whichever exists.

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

How to approach the problem with the rocket jumping in powers of two? I tried simulating it with bruteforce but always WA

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

    In that you could easily compute xj array and let dp[i] be the answer for musk rocket to come at i hence the problem reduced to for each i given k disjoint intervals [l_i,r_i] and value of k would be atmost 20(actually less than that too) and if we are at i then just update all the intervals that could be done by segment tree or fenwick tree but could also be done by some ranged update in a query (like updating for [l_i,r_i] by adding dp[i] to it ->dp[l_i]+=dp[i] and dp[r_i+1]-=dp[i] then if we are at i then we no the answer available at i by just summing over values before that or just adding the initials.

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

      Yeah thats pretty obvious and this is what I was doing but my answer was wrong from n >= 6. Maybe I had implementation issues.

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

      As the range update queries will always be to the right of the current index i, we can use a difference array and keep taking its prefix sum while traversing from left to right. The implementation will be much shorter and easier.

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

To solve DP integers: I just applied dp with recursion:

f(a, b) = min{

if (a == 0 and b == 0) return 0;

if (a != b) return f(sqrt(a*b), sqrt(a*b) + 2;

if (a > 0) return f(a/2, b) + 1;

if (b > 0) return f(a, b/2) + 1;

}

To solve Two summations: Used greedy: sorting.

Observation: a_i + b_j dominates b_i + a_j when a_i + b_j > b_i + a_j

Rearrange the equation and apply sort function.

a_i — b_i > a_j — b_j

After sorting, calculate the contribution of each number, since i < j and j will dominate i.

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

Where I can see scoreboard or standings ?

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

I solved 3. A lot of people whom I know solved 4 or more.

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

Can anyone share the approach for the last problem?

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

    did you get 4th question ? I solved it in o(n*n) . Please share the approach! Thanks in advance

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

My friend has received an email stating the test cases of DP integers have changed,before for 0 0,output was given as 2 and I think everyone wrote the solution accordingly,but then after the contest I came to know that it was changed,is there anyone with the same scenario ?

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

This contest was a crap. Wasted 4 hours

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

    why tho? too easy for you?

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

      Absolutely not. You know the test cases issue with the second problem. I still don't understand what we are supposed to do in the third problem. There was an option like see expected output for custom input, for third problem when I gave 9 9 1 as input the output was 1 but according to the sample test cases it should be 0. O(nlogn) doesn't pass for the fourth problem. I had to optimize it to O(n). For fifth problem, the problems statement is somewhat wrong.

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

        What approach did you follow in 4th question?

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

          I don't think we can view our solutions. I initially solved the problem using maps. After I got TLE, I used arrays instead of maps. Hashed negative values to positive indices by adding -min.

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

        I coded 4th in nlogn and it passed.

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

          Maybe my O(nlogn) implementation was a mess.

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

          can you please share the solution?

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

            I calculated number of times ai and bi will occur in the answer. Just multiplied the count obtained with ai and bi to get the final answer (Contribution technique).
            Now, for ai to appear in the summation this condition must be true :
            ai + bj >= aj + bi
            => ai-bi >= aj-bj
            Make a vector of ai-bi values and then sort it. Use binary search to count the occurences with the above condition (for count of bi inequality will be reversed).

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

          metoo

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

          can you send the code of 4th quesiton? So that i can see what is the approach of the quesion...

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

        Could you please tell what part was wrong in Problem Statement of 5th Problem?

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

          Setter solution didn't ignore double counting.

          For eg. xj[i] = 3;

          then possible lengths of jumps are [2^0,2^1] union [2^1,2^2]

          so,

          {1,2} union {2,3,4} = {1,2,3,4}

          but setter solution has taken it as {1,2,2,3,4}

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

I had solved first, second and fourth partial. For the first I had just checked if string length is greater than 3 and if s(I) == S(I+1) or S(I) ==S(I+2).

For. The second I had separately handled four corner cases and for rest cases just found out operation required to turn minimum of two number to zero and add 2 to it

For fourth partial brute force

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

Can anyone suggest approach for two summation and swap it harder?

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

    This is the solution for Two Summation

    First, in these types of problems, you should try to simplify as much as possible. Let's go through the solution.

    Part- I
    Part- II
    Part- III
    Optimization
    Example
    A Little More Observation
    Final Answer
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      This should be O(nlogn) as you have sorted the diff array.

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

        Yeah, you are right, what I meant was how to do in $$$O(N)$$$ after sorting.

        I'll change that. Thanks!

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

      This leetcode problem is based on the similar profile. Even though, I have solved this problem, I couldn't get the 4th one in the contest =(

      If someone has got similar problems, please do share.

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

x

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

    I appreciate your effort but it is kind of unreadable.

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

    Were the points displayed after submission? They weren't displayed for me when my solutions got fully accepted

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

      Yes the points were not shown when the solution got fully accepted but for partially correct solution points were shown

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

crappiest contest wasted 4 hours solved first three only to learn test cases for problem 2 changed and for problem 3 test cases were super weak and wrong . no learning

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

Can anyone help with the logic of the shipment packaging question?

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

Does anyone know when will they release standings?

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

    After the second version which is to be held on 23rd Oct . Your best of two scores will be considered in final standings.


    Source :- LinkedIn

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

I have received one mail (some days back) regarding another contest of Codeagon on 17th October. But since then, I haven't received any further notifications. Has anyone else got it? image

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

When we can expect results of codeagon 2021 ?

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

    It's better to have no expectation from them :XD

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

      Looks like they were not too much interested this year.In first contest test cases went wrong for second problem.

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

    Shortlisting emails are getting released. Check your mailbox.

    → Reply