Invitation to April Easy '16 on HackerEarth

8 лет назад, # ^ |

;_;

→ Ответить

belowthebelt

8 лет назад, # |

+35

I read the tags! :P

→ Ответить

belltolls

8 лет назад, # ^ |

+44

then you're a whore :P

→ Ответить

Errichto

8 лет назад, # ^ |

+21

He didn't add tags though (and he didn't "ad" them).

→ Ответить

8 лет назад, # |

Reminder: Contest starts in a couple of minutes. Do take part.

→ Ответить

pakalupapito

8 лет назад, # |

+11

Great Problems,thanks for your effort, problems could had been less ambiguous

→ Ответить

8 лет назад, # ^ |

← Rev. 2 →

I agree, nice problems! In linear recurrences though, TL may be is too tight.

EDIT: as Pranet showed to me, my problem was in slow IO. The TL is fine!

→ Ответить

pranet

8 лет назад, # ^ |

Just going to put this here... http://codeforces.com/blog/entry/44126?#comment-287712

→ Ответить

abisheka

8 лет назад, # |

How to solve linear recurrences?Mine was O(6^3*logn) which obviously din't pass.

→ Ответить

8 лет назад, # ^ |

I had 5x5 matrix M which mapped (F[n - 2], F[n - 1], G[n - 2], G[n - 1], T[n - 1]) to (F[n - 1], F[n], G[n - 1], G[n], T[n]) where T[n] = H[0] + H[1] + .... Also precomputed all powers of the matrix M^e for e = 0, ..., 2¹⁵ - 1 and for e = 2¹⁵, 2 * 2¹⁵, 3 * 2¹⁵, ...2¹⁵ * 2¹⁵. Then each query can be done with multiplication of two matrices (one from the first set and one from the second). But still I had to optimize to fit in 2 seconds TL.

→ Ответить

8 лет назад, # ^ |

If you pre-compute M¹, M², M⁴, ... , M^2³⁰, then you can compute the answer to each query in approximately 5^2*log(n) operations. To achieve this reduction perform the multiplication from right to left. Refer to the editorial for more details.

→ Ответить

8 лет назад, # ^ |

speaking about editorials, where are they actually?

→ Ответить

8 лет назад, # ^ |

If you are looking at the problem page then there are 3 options, "Problem", "editorial", and "my submissions".

→ Ответить

8 лет назад, # ^ |

I have there only Problem and My submissions, but no Editorial :(

→ Ответить

8 лет назад, # ^ |

Editorial.

Also, if you are getting the option to go to practice area, do that and then see if you get any editorial option. If even that does not work then contact HackerEarth admins for help.

→ Ответить

8 лет назад, # ^ |

I precomputed M¹, M², M³, ..., M^2¹⁵ and M^2¹⁵, M^2·2¹⁵, M^3·2¹⁵, ..., M^{2¹⁵·2¹⁵}. So that I can compute M^e = M^{a + 2¹⁵·b} = M^a·M^b·2¹⁵ in only one matrix multiplication.

So I wonder what was so unoptimal in my solution, such that even log(n) multiplications from your solution may pass.

→ Ответить

pranet

8 лет назад, # ^ |

← Rev. 2 →

~~You seem to be answering each query in O(m^3) (Please correct me if I'm wrong). Intended is O(m^2*log(m)) per query.~~

My bad. Yours is indeed faster in theory( 5 vs log2(1000000000) ). ~~However, your solution does seem to be suffering from cache misses(just changing the order of the loops in matrix mul achieves a small speedup).~~

Dude! Use scanf and printf!. Your solution gets AC well within time limit(0.9s)

http://ideone.com/anJgcj

→ Ответить

8 лет назад, # ^ |

Ahh right, thank you very much for the investigation! My PR() macro confused me.

→ Ответить

ivanilos

8 лет назад, # ^ |

← Rev. 2 →

Is it too much to ask you what was your matrix M? I tried the same thing but I couldn't even pass the sample tests.

PS: Just found editorial is available, sorry for comment

→ Ответить

8 лет назад, # ^ |

+10

Sure, here it is:

    int step[5][5] = {
    //  F-2 F-1 G-2 G-1 T-1
       {0,  1,  0,  0,  0}, // F-1
       {0,  A,  B,  0,  0}, // F-0
       {0,  0,  0,  1,  0}, // G-1
       {D,  0,  0,  C,  0}, // G-0
      {FD, EA, EB, FC,  1}, // T-0
    };

→ Ответить

8 лет назад, # |

+13

How to solve A?

→ Ответить

8 лет назад, # ^ |

int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  SORT(a);
  ll ans = 0;
  for (int i = 0, v = 1; i < n; ++v) {
    ll c = v * 1ll * v;
    if (c >= a[i]) {
      ans += c - a[i];
      ++i;
    } else {
      ans += c;
    }
  }

  cout << ans << endl;

→ Ответить

8 лет назад, # ^ |

← Rev. 2 →

+20

It doesnt work, actually.. Test:

2
4 10

UPD: But is gets 100 on Oj...

→ Ответить

8 лет назад, # ^ |

-8

You did not read statement carefully:

"You quickly gather the balls and try to reconstruct a square pyramid(maybe of a different height) by using ALL the recovered balls"

You have to use all found balls. E.g. in your example the optimal solution is to buy 1, for first colour, then 0 for second (you have 4 already), 9 for third (you have 10 balls, but according to statement we have to use ALL balls, so we can't throw one extra ball away), and we heed to buy 6 balls for the last color (16 — 10 that we have = 6). so, all together we need to buy 1 + 9 + 6 = 16 balls.

→ Ответить

8 лет назад, # ^ |

← Rev. 4 →

Im using all the recovered balls, man:

Lets split 10 into 1 + 9 and now we can build a square pyramid with height = 3.

→ Ответить

vsp4

8 лет назад, # ^ |

← Rev. 2 →

You cannot split them as each layer has to be coloured differently. The 10 balls are of the same color

→ Ответить

8 лет назад, # ^ |

← Rev. 3 →

you can't split balls into two or more groups, because then you will have at least two layers of same colour which is prohibited.

→ Ответить

8 лет назад, # ^ |

You are right, thanks for explanations.

→ Ответить