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 (12)

Write comment?

Aritro_

8 hours ago, # |

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

→ Reply

Leonardo_Paes

7 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

5 hours ago, # ^ |

Same approach

Swayam78

7 hours ago, # |

Were you worried?

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.