BledDest's blog

By BledDest, 4 months ago, In English

The contest was prepared by awoo, Neon, adedalic, Roms and me. We are very grateful to all of the testers of the contest: PavelKunyavskiy, ashmelev, vladmart, Vladosiya and mariibykova.

We hope you enjoyed both the problems and coding in Kotlin!

Okay, now let's talk about how these problems can be solved:

1910A - Username

Idea: BledDest, preparation: Neon

Tutorial
Solution (PavelKunyavskiy)

1910B - Security Guard

Idea: Roms, preparation: Roms

Tutorial
Solution (Neon)

1910C - Poisonous Swamp

Idea: BledDest, preparation: awoo

Tutorial
Solution (PavelKunyavskiy)

1910D - Remove and Add

Idea: BledDest, preparation: awoo

Tutorial
Solution (PavelKunyavskiy)

1910E - Maximum Sum Subarrays

Idea: BledDest, preparation: Neon

Tutorial
Solution 1 (Neon)
Solution 2 (PavelKunyavskiy)

1910F - Build Railway Stations

Idea: BledDest, preparation: awoo

Tutorial
Solution (PavelKunyavskiy)

1910G - Pool Records

Idea: adedalic, preparation: adedalic

Tutorial
Solution (adedalic)

1910H - Sum of Digits of Sums

Idea: BledDest, preparation: BledDest

Tutorial
Solution (PavelKunyavskiy)

1910I - Inverse Problem

Idea: BledDest, preparation: awoo

Tutorial
Solution (awoo)

1910J - Two Colors

Idea: BledDest, preparation: BledDest

Tutorial
Solution (PavelKunyavskiy)
  • Vote: I like it
  • +35
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Nicely curated problems orz in order of difficulty to slowly dive into the syntax and structure of Kotlin, took me time but enjoyed in solving and learning syntax on way.

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For the problem H, there is actually an O(nlogA) solution. When i'm saying "b.s.", i'm refering to "binary search". The O(nlognlogA) complexity we need to "patch" comes in 2 parts: the sorting, and the b.s.. For the sorting, we can do lsd radix sort (with base 10), and store every iteration of it. For the second part, we don't actually have to do b.s.. If we focus on the "queries" of the b.s. on an arbitrary array (one of the logA ones), the inputs of the b.s. are m-ar[i], where m is the current power of 10, and ar[i] is the value on the array. Because ar is sorted (we don't care about order), the sequence m-ar[i] is also sorted, in reverse order (because m is constant). Therefore, we can find all the positions of the sequence, with a basic 2-pointer method (see merge-sort), in linear time. So we have O(n) time for every array, and we have logA arrays, so the final time (and space) complexity is O(nlogA). I'm gonna upload c++ code in a while too.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just coded it up, the only test cases i've tested it on, are the 2 input examples from the problem statement (it works). 239141643 It obviously doesn't compile, its on c++. I sent the submission for you to see the code.

    ALSO: The space complexity can be improved to O(n), even tho i'm not gonna bother coding it: We need to store only the current iteration of the (base 10) lsd radix sort, and calculate the values for the indeces, and then move on to the next iteration. From now on, we don't need the previous one, so we don't have to keep storing it.

    Final time complexity: O(nlogA), where A is the max element

    Final space complexity: O(n).

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Just did it, 239202554. I believe that this is the optimal time and space complexity