Блог пользователя mon0pole

Автор mon0pole, история, 3 года назад, По-английски

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)

  • Проголосовать: нравится
  • +30
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

This time it was smooth, no mistakes

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Shouldn't it be having bitonic nature?

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            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 года назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится

          Can u please share how did you solved it.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem 1?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    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 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Code

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Did anyone solve 4+ ?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you state how to solve problem 5

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
      My approach

      If you find anything wrong correct me

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Any information about ranklist?