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

Автор wanbo, история, 10 лет назад, По-английски

Hello Codeforces community!

I am glad to announce that HackerRank 101 Hack 42 will be held on 18th Oct 2016 at 16:30 UTC. You can sign up for the contest here. Though what's priceless is solving interesting problems and the thrill of competition, prizes make the competition fierce. Top 10 performers will get a HackerRank T-shirt.

The contest will consist of 5 problems with variable scoring distribution. We have tried our best to prepare a nice problem set. Hopefully everyone will enjoy. Also, you'll be able to enjoy the detailed editorials written by the setter.

Good luck and have fun!

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

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Who is the setter this time around?

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

Is this correct for the earlier version of 4th problem ?

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +44 Проголосовать: не нравится

I solved E in O(n × log3(n)) and it passed TL. Problem statement for D was totally wrong for 70 minutes of contest. Strange contest.

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

1) Will the round be rated?
2) What is "BIT" in "can solved offline using BIT" in E-problem's editorial?

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

In problem E, why does iterating over the smaller segment doesn't time out?

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +32 Проголосовать: не нравится

About problem D, if you have a loop that takes k time and a loop that takes n/k time, then the complexity is O (n), not O (nk). I'm guessing the statement wasn't the only part of this problem that was rushed...

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

For E problem.I wrote N*log(N)*log(N) solution but it give TLE.Pls help find my mistake.I used ordered set and divide conquer. Here is my code.

»
10 лет назад, скрыть # |
 
Проголосовать: нравится -38 Проголосовать: не нравится

I was initially using a sparse table in problem E, that took O(NlogN) memory, that caused MLE. However, all this time, HackerRank's judge showed me the verdict Wrong Answer.

After the contest, I used a segment tree, that takes O(N) memory, and guess what, my solution passed. Why doesn't HackerRank provide a verdict like MLE ? Is giving wrong answer the right way to deal with this? This made me really angry after the contest.

When one creates an online judge, the first thing one should deal with is small things like various verdicts. This is really stupid from HR.

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

In 4th problem, why the theory that no button should be pressed twice works?Proof!

»
10 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится +8 Проголосовать: не нравится

I have an alternative (albeit harder to implement) approach for problem E:

We will be using D&C approach. Let's now consider a segment [l...r) ans fix m = (l + r) / 2. We will recurse for [l...m) and [m...r) and, after that, calculate the answer for and .

Now, let's suppose the maximum value lies on the right segment. Then, we could sort the left segment decreasingly by value A[i] and sort right segment decreasingly by value max[m...j] / A[j].

Now, we can impose the constraint A[i] * A[j] ≤ max[m...j] by an algorithm similar to merging sorted arrays, with the two pointer approach. Let's also not forget about the other constraint, created by out supposition: max[i...m) ≤ max[m...j]. This can be solved by keeping a data structure of your choice (I used BIT).

The other case is solved similarly, with some extra care for double-counting.

No arguing, the other solution is easier to understand and write. And it's a nice trick to remember.

Code is here. I had to parse input data in order to squeeze it within time limits. Sneaky and overcomplicated, but rather fun nonetheless.