Ramprosad's blog

C. Array Spliting (Solution With IOI 16 Alien Trick)
By Ramprosad, history, 5 years ago, In English

https://mirror.codeforces.com/contest/1197

https://mirror.codeforces.com/contest/1197/problem/C

Before this contest started, I have learned and implement the dp optimization IOI 16 Alien Trick. When I see the problem C, I thought this problem can be solved With the Alien trick. Then I started trying to solve the problem and finally I got Accepted verdict. This Problem can be solved simply using sorting the difference of adjacent element. Maximum Contestant has solved this with sorting. When I saw that all Contestant solve this problem very easy way, I became very surprised. But I am happy , because I could apply the trick first day in contest time.

This is my Solution.

https://mirror.codeforces.com/contest/1197/submission/57537548

Thanks to Everyone.

  • Vote: I like it
  • +42
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
5 years ago, # |
  Vote: I like it +72 Vote: I do not like it

Please do not be offended but this is so cyan.

→ Reply
»
5 years ago, # |
  Vote: I like it +91 Vote: I do not like it

This is actually quite cool. I realized that I can compute the minimum of array using Li-chao tree. You can simply make $$$n$$$ lines $$$a_i \times x$$$ and query on point $$$x=1$$$!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Where can I learn about this IOI Alien Trick ? Any Links ?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please paste this blog link to contest page?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Das some serious shit right there

→ Reply