Leonardo_Paes's blog

EZ Clap
By Leonardo_Paes, history, 3 hours ago, In English

1999/2000 ms

  1. 02:57:15 Unsuccessful hacking attempt
  2. 03:13:10 Unsuccessful hacking attempt
  3. 03:13:18 Unsuccessful hacking attempt
  4. 03:13:53 Unsuccessful hacking attempt
  5. 03:13:59 Unsuccessful hacking attempt
  6. 03:14:16 Unsuccessful hacking attempt
  7. 03:17:38 Unsuccessful hacking attempt
  8. 03:19:16 Unsuccessful hacking attempt
  9. 03:19:30 Unsuccessful hacking attempt
  10. 03:20:19 Unsuccessful hacking attempt
  11. 03:20:21 Unsuccessful hacking attempt
  12. 03:20:49 Unsuccessful hacking attempt
  13. 03:21:31 Unsuccessful hacking attempt
  14. 03:21:54 Unsuccessful hacking attempt
  15. 03:22:12 Unsuccessful hacking attempt
  16. 03:22:33 Unsuccessful hacking attempt
  17. 03:23:01 Unsuccessful hacking attempt
  18. 03:23:19 Unsuccessful hacking attempt
  19. 03:23:56 Unsuccessful hacking attempt
  20. 03:24:45 Unsuccessful hacking attempt
  21. 03:32:37 Unsuccessful hacking attempt
  22. 03:43:11 Unsuccessful hacking attempt
  23. 03:44:49 Unsuccessful hacking attempt
  24. 03:45:17 Unsuccessful hacking attempt
  25. 03:49:26 Unsuccessful hacking attempt
  26. 03:52:07 Unsuccessful hacking attempt
  27. 03:54:15 Unsuccessful hacking attempt
  28. 03:54:44 Unsuccessful hacking attempt
  29. 04:07:35 Unsuccessful hacking attempt
  30. 04:09:54 Unsuccessful hacking attempt
  31. 04:10:08 Unsuccessful hacking attempt
  32. 04:20:09 Unsuccessful hacking attempt
  33. 04:37:57 Unsuccessful hacking attempt
  34. 04:39:22 Unsuccessful hacking attempt
  35. 04:45:43 Unsuccessful hacking attempt
  36. 04:49:15 Unsuccessful hacking attempt
  37. 04:52:11 Unsuccessful hacking attempt
  38. 05:09:40 Unsuccessful hacking attempt
  39. 05:56:25 Unsuccessful hacking attempt
  40. 05:57:03 Unsuccessful hacking attempt
  41. 06:55:06 Unsuccessful hacking attempt
  42. 08:05:42 Unsuccessful hacking attempt
  43. 09:35:15 Unsuccessful hacking attempt
  44. 10:12:43 Unsuccessful hacking attempt
  45. 10:18:41 Unsuccessful hacking attempt
  46. 10:22:24 Unsuccessful hacking attempt
  47. 10:23:44 Unsuccessful hacking attempt
  48. 10:31:17 Unsuccessful hacking attempt
  49. 10:36:35 Unsuccessful hacking attempt
  50. 11:35:52 Unsuccessful hacking attempt
  51. 11:37:09 Unsuccessful hacking attempt
  52. 11:37:34 Unsuccessful hacking attempt
  53. 11:46:50 Unsuccessful hacking attempt
  54. 11:46:56 Unsuccessful hacking attempt
  55. 11:50:31 Unsuccessful hacking attempt
  56. 11:52:25 Unsuccessful hacking attempt
  57. 12:03:54 Unsuccessful hacking attempt
  58. 12:04:32 Unsuccessful hacking attempt
  59. 12:10:46 Unsuccessful hacking attempt
  60. 12:12:56 Unsuccessful hacking attempt
  61. 12:13:54 Unsuccessful hacking attempt
  62. 12:36:01 Unsuccessful hacking attempt
  63. 12:37:40 Unsuccessful hacking attempt
  64. 12:43:01 Unsuccessful hacking attempt
  65. 12:45:35 Unsuccessful hacking attempt
  66. 12:49:09 Unsuccessful hacking attempt
  67. 12:50:55 Unsuccessful hacking attempt
  68. 13:06:04 Unsuccessful hacking attempt
  69. 13:09:44 Unsuccessful hacking attempt
  70. 13:11:34 Unsuccessful hacking attempt
  71. 13:12:07 Unsuccessful hacking attempt
  72. 13:12:48 Unsuccessful hacking attempt
  73. 13:13:34 Unsuccessful hacking attempt
  74. 13:27:01 Unsuccessful hacking attempt
  75. 13:28:41 Unsuccessful hacking attempt
  76. 13:31:04 Unsuccessful hacking attempt
  77. 13:32:33 Unsuccessful hacking attempt
  78. 13:34:26 Unsuccessful hacking attempt
  79. 13:34:57 Unsuccessful hacking attempt
  80. 13:35:46 Unsuccessful hacking attempt
  81. 13:36:05 Unsuccessful hacking attempt
  82. 13:36:19 Unsuccessful hacking attempt
  83. 13:36:27 Unsuccessful hacking attempt

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

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

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    2 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Were you worried?

→ Reply
  • »
    »
    118 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      113 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, i too implemented in O(n*k*2) tc , it worked fine , Due to constraints I did that. I got it in 343ms. So didn't optimised it.

      → Reply
»
114 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

funniest post lol

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

mine N*N*logN got TLE on test 4. So optimised it to N*N.

→ Reply