bhagya_rana's blog

By bhagya_rana, 22 months ago, In English

Combined Questions PDF Link

Q1) Two Operations

Problem Description

Q1

Example Test Case + Explanation

Q1-TestCase

Q2) Aesthetic Permutation

Problem Description

Q2

Example Test Case + Explanation

Q2-TestCase

Q3) Treasure Hunt in the city

Problem Description

Q3-A
Q3-B

Example Test Case + Explanation

Q3-TestCase

Q4) Expected Path Length

Problem Description

Q4

Example Test Case + Explanation

Q4-TestCase

Q5) Intersection of segments

Problem Description

Q5

Example Test Case + Explanation

Q5-TestCase

Q6) Possible Array

Problem Description

Q6-A
Q6-B

Example Test Case + Explanation

Q6-TestCase

Please share your Approaches and Solution for problems in comments.

If this Discussion was Helpful, Please do Upvote this Blog for Greater Audience Reach.

Disclaimer : This Thread is made for Discussion of Codeagon-2023-Contest, which was held on 8-Jan-2023 from 12 PM to 3 PM I.S.T. The Contest has been officially Ended and this Discussion Thread is Published after the Contest.

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

| Write comment?
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Appreciate your efforts. How to solve 6th?

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

    The problem can be reduced to the number of simple paths in a graph, which is a standard dp problem

»
22 months ago, # |
Rev. 7   Vote: I like it +12 Vote: I do not like it
Problem 1
Problem 2
Problem 3
Problem 4
Problem 5
Problem 6

I will update the solution to problem 6 in a more detailed way after some time.

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

    Bruh How are you RED with 1800 rating xD

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

    In problem 2nd i figured that
    We have to first sort the array-
    choose a (n/B) length continuous segment and put it on i ,i+B ,i+2*B ,... pos If n is not divisible by B then there are some chain of (n/B) +1 ...

    So I dont know how to implement this like [len(n/B)][len(n/b +1)] .. some random order

    Can you help with this idea

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

      Implementation part or do you have any difficulty in the logic building?

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

        I have problem in implemention But now I get it Thanks:)

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

          Can you share your code and approach ?

          • »
            »
            »
            »
            »
            »
            20 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            I dont recall much of it. I think it has some dp implementation You check below comments there you find implementation

  • »
    »
    20 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    in 4th problem , i dit the exact same but just a small query,

    dp[x] = ( 1/(total_divisor) )* ( (1 + dp[x1]) , (1 + dp[x2]) ,.... (1 + dp[x])) if we separate dp[x] , it will be

    dp[x] = (1/(total_divisor-1)) * ( (1 + dp[x1]) , (1 + dp[x2]), .... + (1))

    I think in your solution you already mentioned that we excluded itself I am thinking the ''one'' that remains from the last block where we chooose 1 as its factor and contribute a step

    //Plz check if i am wrong

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

      Yes if we can go the same number then we will have to shift the dp(x) coefficient to LHS and then divide it. In this contest it was mentioned that we can't go to the same number.
      But in today's Trilogy contest we can go to the same number so your mentioned modification should be done

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

        ohhh i see , Thanks

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

        Can you provide Soln of todays trilogy contest also , It would be helpfull

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

          Do you have the pictures of the problems? Btw I could not solve the first problem completely.

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

            I only know 1st problem statement bcz i managed to solve it , but doesn't have ss of it and other also I only have ss of this expected value question

            • »
              »
              »
              »
              »
              »
              »
              20 months ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              What was your approach for the first problem? Just to confirm your first problem was that monster and hero problem?

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

                i actually created a segtree. Then i sort the Monster array by its health Now for j in Heroes array , We find [0..i] by lower_bound such that we can remove them if they are at B[j][0]

                Now by segtree , point query I store Ans[j] Which means if jth hero comes it will erase Ans[j] amount of monster

                Then just update as heroes comes

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

            Yes I have. Which one you need?

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

    In Problem 6, how to keep track of last chosen index for the next transition?

»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Did you guys receive any acknowledgement mail (like successfully completed the test) after completion of the test? After 3hrs I was taken to a page that says couldn't access test instead of test completed page.

»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it
For me, after I submitted, it came as correct answer, does that mean I passed all test cases?
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone explain solution of problem 2.

»
22 months ago, # |
  Vote: I like it +4 Vote: I do not like it
Expected Path Length:

Using linearity of expectation, Expected Value of Steps = 1 / A * (summation of Exp(x) over all 'x') , where 1 <= x <= A

Let divisors(x) = number of divisors of 'x'.

Exp(x) = 1 / divisors(x) * (1 + summation of Exp(x / d) over all divisors 'd')

Since A <= 10 ^ 5, it can be calculated using sieve.

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

Problem 3

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Solution
Code
Bonus Hint

Thanks for reading! Please point out if I've made any mistake. Feel free to share any better or more interesting approach.

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

How much problems we have to solve to get shortlisted for interviews?

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

Q-2 Aesthetic Permutation solution using DP:

Notice that there would be a total of b sequences of type Sequence1 -> 1, 1+b, 1+2*b ... Sequence2 -> 2, 2+b, 2+2*b ...

Now out of b, b-n%b sequence will have size of n/b and rest (n%b) will have size of n/b+1.

Each sequence should have elements in sorted form. Now dp comes into the picture to decide which sequence should get elements from current_index to current_index + (size_of_chosen_sequence)-1.

C++ code
  • »
    »
    22 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes bro i have the same idea but don't able to implement:( Thanks bro for your implementation

»
22 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Anybody got any mail about selection? Or when is the result anybody knows?

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

Anyone from the 2023 batch received any mail for the next steps?