Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link ×

object022's blog

By object022, 8 years ago, In English,

UPD:Minor mistakes in grammar and expression fixed.

Disclaimer: This is not an official editorial.

If you have better or easy-to-understand solutions and thoughts, feel free to share your idea. Also welcome to point out mistakes so I can fix it.

160A - Близнецы

It's obvious that you should take the most valueable coins. so sort values in non-decreasing order, then take coins from the most valueable to the least, until you get strictly more than half of total value.

Time complexity depends on the sorting algorithm you use. O(n^2) is also acceptable, but if you use bogosort which runs in O(n!)...

160B - Несчастливый билет

Deal with the situation that "first half is strictly less than second half" first. the other one can be solved accordingly.

You can use greedy here: sort digits in first and second half seperately. then if the i-th digit in first half is always less than i-th in second half for 1<=i<=n, answer is YES.

Time complexity is as same as problem A. Count sort may run faster in O(n+10), but it's not necessary

Read more »

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