saptarshikuar2003's blog

C. Earning on Bets :- How the idea of LCM hits.
By saptarshikuar2003, history, 3 days ago, In English

Hello everyone,

problem link:- https://mirror.codeforces.com/problemset/problem/1979/C

I was solving the problem and got stuck,

and in the editorial it was mentioned their that we have to use LCM I am not getting how the LCM is intuted.

what is the role of LCM...... is it observational or there is some proof for the use of LCM

please clarify about it..

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

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

you can solve it without lcm

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

    Please can you explain the approach

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

      You can use binary search to find the minimal outcome for the maximum k[i], which helps to determine the "number of coins returned for each possible winning outcome" -> middle. This is because it's monotonic. Once you fix the maximum value, you can use a greedy algorithm for each k[i]. For each k[i], we need to find the maximum outcome[i] such that outcome[i] * k[i] ≤ maximum(k[i]) * middle.

      1st sample case: n = 3 k = {3, 2, 7}

      maximum_k[i] = 7. Using binary search to find the outcome value gives us 6. (6 * 7) = 42

      outcome = {14, 21, 6} —> that's the result.

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

        ok that means I am in case of maximum we can take any other element that is also true.... thank you for your help.

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

      Also you can check my solution

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

During the contest I simply guessed that lcm worked and I couldn't come up with a counter test case so I went with it

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

I can see your nationality with my eyes closed

→ Reply