EZ Clap - Codeforces

#	User	Rating
1	jiangly	3845
2	tourist	3798
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3589
6	Ormlis	3532
7	Benq	3468
8	Radewoosh	3463
9	ecnerwala	3451
10	Um_nik	3450

#	User	Contrib.
1	cry	165
2	Qingyu	160
3	-is-this-fft-	159
4	atcoder_official	157
5	Dominater069	156
6	adamant	154
7	djm03178	151
8	luogu_official	149
9	awoo	147
10	TheScrasse	145

1999/2000 ms

02:57:15 Unsuccessful hacking attempt
03:13:10 Unsuccessful hacking attempt
03:13:18 Unsuccessful hacking attempt
03:13:53 Unsuccessful hacking attempt
03:13:59 Unsuccessful hacking attempt
03:14:16 Unsuccessful hacking attempt
03:17:38 Unsuccessful hacking attempt
03:19:16 Unsuccessful hacking attempt
03:19:30 Unsuccessful hacking attempt
03:20:19 Unsuccessful hacking attempt
03:20:21 Unsuccessful hacking attempt
03:20:49 Unsuccessful hacking attempt
03:21:31 Unsuccessful hacking attempt
03:21:54 Unsuccessful hacking attempt
03:22:12 Unsuccessful hacking attempt
03:22:33 Unsuccessful hacking attempt
03:23:01 Unsuccessful hacking attempt
03:23:19 Unsuccessful hacking attempt
03:23:56 Unsuccessful hacking attempt
03:24:45 Unsuccessful hacking attempt
03:32:37 Unsuccessful hacking attempt
03:43:11 Unsuccessful hacking attempt
03:44:49 Unsuccessful hacking attempt
03:45:17 Unsuccessful hacking attempt
03:49:26 Unsuccessful hacking attempt
03:52:07 Unsuccessful hacking attempt
03:54:15 Unsuccessful hacking attempt
03:54:44 Unsuccessful hacking attempt
04:07:35 Unsuccessful hacking attempt
04:09:54 Unsuccessful hacking attempt
04:10:08 Unsuccessful hacking attempt
04:20:09 Unsuccessful hacking attempt
04:37:57 Unsuccessful hacking attempt
04:39:22 Unsuccessful hacking attempt
04:45:43 Unsuccessful hacking attempt
04:49:15 Unsuccessful hacking attempt
04:52:11 Unsuccessful hacking attempt
05:09:40 Unsuccessful hacking attempt
05:56:25 Unsuccessful hacking attempt
05:57:03 Unsuccessful hacking attempt
06:55:06 Unsuccessful hacking attempt
08:05:42 Unsuccessful hacking attempt
09:35:15 Unsuccessful hacking attempt
10:12:43 Unsuccessful hacking attempt
10:18:41 Unsuccessful hacking attempt
10:22:24 Unsuccessful hacking attempt
10:23:44 Unsuccessful hacking attempt
10:31:17 Unsuccessful hacking attempt
10:36:35 Unsuccessful hacking attempt
11:35:52 Unsuccessful hacking attempt
11:37:09 Unsuccessful hacking attempt
11:37:34 Unsuccessful hacking attempt
11:46:50 Unsuccessful hacking attempt
11:46:56 Unsuccessful hacking attempt
11:50:31 Unsuccessful hacking attempt
11:52:25 Unsuccessful hacking attempt
12:03:54 Unsuccessful hacking attempt
12:04:32 Unsuccessful hacking attempt
12:10:46 Unsuccessful hacking attempt
12:12:56 Unsuccessful hacking attempt
12:13:54 Unsuccessful hacking attempt
12:36:01 Unsuccessful hacking attempt
12:37:40 Unsuccessful hacking attempt
12:43:01 Unsuccessful hacking attempt
12:45:35 Unsuccessful hacking attempt
12:49:09 Unsuccessful hacking attempt
12:50:55 Unsuccessful hacking attempt
13:06:04 Unsuccessful hacking attempt
13:09:44 Unsuccessful hacking attempt
13:11:34 Unsuccessful hacking attempt
13:12:07 Unsuccessful hacking attempt
13:12:48 Unsuccessful hacking attempt
13:13:34 Unsuccessful hacking attempt
13:27:01 Unsuccessful hacking attempt
13:28:41 Unsuccessful hacking attempt
13:31:04 Unsuccessful hacking attempt
13:32:33 Unsuccessful hacking attempt
13:34:26 Unsuccessful hacking attempt
13:34:57 Unsuccessful hacking attempt
13:35:46 Unsuccessful hacking attempt
13:36:05 Unsuccessful hacking attempt
13:36:19 Unsuccessful hacking attempt
13:36:27 Unsuccessful hacking attempt

Blessed by the $$$O(n^2 \log n)$$$ no-brainer! Try harder hacking next time :P

Comments (10)

Write comment?

Aritro_

4 hours ago, # |

What is your approach that takes exactly $$$1999/2000$$$ ms?

→ Reply

Leonardo_Paes

4 hours ago, # ^ |

← Rev. 2 →

I brute force the last painted element. That part is $$$O(n)$$$. Then, I get the subarrays from the left and from the right of it and sort them. The idea is that if I get at least one element on the left of our pivot and one from the right, I can guarantee that it is a valid last painted element. So, for $$$k\geq2$$$ I take the maximum on the left and on the right of our last painted element. Then, I sort all the other $$$n-3$$$ elements (without the last painted and the two maximums) and take the $$$k-2$$$ biggest ones. Sorting the remaining $$$n-3$$$ elements take $$$O(n \log n)$$$, so the overall complexity is $$$O(n^2 \log n)$$$. For $$$k = 1$$$, we just do a linear solution brute forcing the first painted item, noticing that the last one can only by the first or the last element of the array.

Here is the code!

DenimFlame12

70 minutes ago, # ^ |

Same approach

Swayam78

3 hours ago, # |

Were you worried?

3 hours ago, # ^ |

Yes. During the contest it took 1984ms on pretests. I was considering implementing the $$$O(n)$$$ solution after getting D, but after 12 WAs I was a bit tilted and didn't have the patience to re-implement B.