mon0pole's blog

By mon0pole, history, 3 years ago, In English

As I didn't find any blog for this round discussion so posting this blog

Problems :

Problem 1
Problem 2
Problem 3
Problem 4
Problem 5
Problem 6

My opinion :
I found problems harder than the previous version of CodeAgon 2021.

Please share your approaches and solution for problems in comments.
PS : Sorry for unclear photos of problems (if anyone have clear photos please share them in comments)

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

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

Auto comment: topic has been updated by mon0pole (previous revision, new revision, compare).

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

This time it was smooth, no mistakes

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

    Not exactly, problem D had weak test cases, always buying the stock on first possible day worked for one of my friend, which is clearly wrong.

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

      Was the intended solution, getting an expression in terms of sqrt(y), and then differentiation and solving quadratic to get the global maxima? I did that

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

        Did you got ac with that? I got WA with this approach.

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

        Differentiating was not necessary, the fact that you got quadratic was enough to claim that one of the extreme values in A would give maximum for a fixed B. so just do these 2*m checks

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

          Shouldn't it be having bitonic nature?

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

            My bad, what I said above is incorrect. I substituted buying date as 4*b*b and buying price as Z — 2*b, which when i plug into the profit expression gives a cubic with negative leading term. So I should have checked the least buying date, latest buying date, and second extremum of this cubic (for each choice of selling quotation), but i guess due to weak tests checking the least and latest buying date itself ACed.

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

          Can u please share how did you solved it.

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

      Vin__ar, Since A[i][0] are at a gap of 4 atleast and there is always a fixed gap between sqrt(A[i][0]) and A[i][1], I feel that taking the first buying day is always optimal. Can you tell me why its wrong

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

        Sure, here's a case A = {{12, 47},{36,44}} B = {{100, 48}} Correct me if I'm missing something.

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

Atleast this time I didn't have to guess the setter's solution XD.

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

How to solve problem 1?

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

    For every market $$$i$$$, you can either buy the oranges from the same market or go to one of the markets $$$j$$$, connected to it, get the oranges in minimum possible cost from $$$j$$$ and come back to $$$i$$$. This will incur an extra cost of $$$cost_{ij}$$$ + $$$d*cost_{ij}$$$. You can solve this using Dijkstra's algorithm. Imagine, there is a virtual node connected to all the markets and edge cost is $$$b_i$$$. Also multiply all the original edge weights by $$$d+1$$$. Problem then reduces to finding shortest path from that virtual node to all other nodes.

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

      I have seen this kind of trick somewhere. Can you please share some problem related to this trick, if you can recall?

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

        Sorry, couldn't recall any problem. But generally when I have a solution that is dp but the transitions make a graph with cycles, I try to think if updating the states in the correct order is possible through Dijkstra. So, for this problem, I initially thought $$$ans_i = min(ans_j + (d+1)*cost(i,j))$$$. Then realized that the updates are possible through Dijkstra. That virtual node is a common implementation trick, you can just ignore that and initialize $$$ans_i = b_i$$$ and then do the relaxations in Dijkstra.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    This is the exact same problem of Codeagon 2020. problem 1 Just replace the edge weights with cost * (D + 1). Rest everything is exactly the same. And it's more funny when you find the problem on code forces that they copied from in 2020, which they repeated now. link

»
3 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

In problem 2, I wrote dp[A][A]. dp[i][j] denotes I have written i lines and selected j lines which I can paste and then the transitions were easy. Can someone tell me was there any other obvious method to solve this problem?

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

    I was getting TLE for my solution. How do i optimise the loop inside the recursion?

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

      Actually, you don't need to do the loop for more than 2 or 3 copies. I have no formal proof of it, just by intuition I wrote this.

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

        I didn't get your point, are you saying loop is not required for input greater tha 2 or 3?

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

          Can you please explain your dp states and what you are doing in the loop first? I was saying that if you have already copied x lines from the previous step, then there is one possibility to copy j lines from the top (j varies from 1 to the current number of lines written till now) and it will cost j+1. For this j, I am saying that the max value of j can be 2-3. You just need to copy not more than 2-3 lines using this operation as it's always better to use other cheaper methods.

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

Did anyone solve 4+ ?

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

How many could you solve? Me 4 (1,2,5,6).

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

    Can you state how to solve problem 5

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it
      My approach

      If you find anything wrong correct me

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

What are your approaches for problems 3 and 4? Here are mine-

Problem 3
Problem 4

If you have any suggestions and/or cases where my approaches fail, do let me know.

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

    For 3rd, I think one can simulate the following greedy procedure:

    Take the maximum element = maxx

    Pop all occurences of it, and add them to the permutation.

    Update all remaining values as x &= maxx.

    Repeat.

    You will have to do this at most 20 times.

    The reason this works is because at each step, we are selecting the lexicographically largest element according to the current active bitmask(mask of bits which have still not encountered a 0)

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

Any information about ranklist?