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

Hints for problem 431B — Shower Line
Автор SiddhyaRushLittlelordOP, история, 11 месяцев назад, По-английски

Note: I'm unware whether I can ask question here. LMK if this post isn't suitable for guidelines. I'll delete it. ;-)

Hello, I'm having confusion about understanding the intuition behind the problem 431B — Shower Line.

I've read the problem statement and editorial it suggested this solution

Can anyone who has solved this problem please give me hint on how to come up with these arr[i][j] numbers in the loop

 do
    {
        //01234
        tmp = g[p[0]][p[1]] + g[p[1]][p[0]];
        tmp += g[p[2]][p[3]] + g[p[3]][p[2]];
        
        //1234
        tmp += g[p[1]][p[2]] + g[p[2]][p[1]];
        tmp += g[p[3]][p[4]] + g[p[4]][p[3]];
        
        //234
        tmp += g[p[2]][p[3]] + g[p[3]][p[2]];
        
        //34
        tmp += g[p[3]][p[4]] + g[p[4]][p[3]];
        
        if(tmp > ans)
        {
            ans = tmp;
            for(int i = 0 ; i < n ; ++i)
                pans[i] = p[i];
        }
    }
    while(next_permutation(p, p+n));

Thanks in advance :-)

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

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

Hi, You look one by one all cases(12345, 13245, 14235, ... ) with next_permutation(), pls say me what are you not understand

→ Ответить
  • »
    »
    11 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Isa_m The input is coming in this format:

    0 0 0 0 9
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
7 0 0 0 0

    I am unable to understand how the 1D cases(12345, 13245, 14235, ... ) are getting interpreted here in 2d matrix. I also could not found any explanation online.

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

      they should talk in such order that the answer is maximum: example 12345 if 1 talk with 2 answer += g12 + g21, after 3 talk with 4 answer += g34 + g43, after 1 gone to shower, now remained 2345 in queue,

      now: 2 talks with 3 and 4 talks with 5, after 2 gone to shower , now remained 345

      now: 3 talks with 4 , after 3 gone to shower and remained 45

      4 talks 5 , after 4 gone shower and remained 5

      if i talks j answer += g[i][j] + g[j][i]

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

      The 1D matrix has the current permutation of the numbers 1 to 5. Now inside g[i][j] 2D array, you are using the elements of the permutation as the index.

      for example, p = [5,3,4,1,2]

      then g[p[0]][p[3]] is actually g[5][1], as p[0] = 5 and p[3] = 1.

      → Ответить