farukkastamonuda's blog

By farukkastamonuda, history, 4 years ago, In English

A-Luck(author Halit):

Solution

code by Halit

code

B-)Find the missed number(author Halit)

Solution

code by AhmetKaan

code

C-)Help for Contest(author AhmetKaan)

solution

code by AhmetKaan

code

D-) Smart Move(author farukkastamonuda)

solution

code by farukkastamonuda

code

E-) Infairness In Sugar Distribution(author farukkastamonuda)

Solution

code by farukkastamonuda

code
  • Vote: I like it
  • +18
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

I've hacked the official solution for E (in custom invocation at least, run in >15000ms) with the following test:

35000

1 2 3 ... 35000.

The runtime of the algorithm is actually O(n2) with bad constant, not O(n log n log MAX). And if you do not understand how the optimization in the official solution works, it can be easy to make this mistake.

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Here is the solution for question C using stack with O(n) Time Complexity,

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

    Good job. implementation with stack is easier than implementation with set. Thank you for your sharing.

»
4 years ago, # |
Rev. 4   Vote: I like it +5 Vote: I do not like it

Hi, for D i have a solution which runs in O(N*K) time and O(N+K) space

CODE

I compared my code with your solution and it runs in (66 ms / 1153 ms, 3700KB / 193000 KB). I enjoyed the problems, but it was hard for me to understand the statements.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the optimization part of problem D?? I came up with the n*k*k solution during the contest which is the same as editorial but could not optimize it and even after reading the editorial, I am not able to understand completely.

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

    if(hak>k) return -inf; I didn't change this if. And with this: int cikar=k-i; int ty=dfs(1,cikar,0,0); Firstly cikar means that how many element you select until now. Firstly cikar=0 then for K-1 case you set cikar to 1 and since it means that you are seen like take 1 element and if(hak>k) return -inf means that you can select at most k-1 elements now and you don't fill the dp array try and try.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I use recursion dp in this question. When you use recursivic dp ans_k = f(1,0,0,0)

    then if you dont clear the dp array and get the walue of f(1,1,0,0) then ans_k-1 = this

    and you can do at most n*k*2*3 operation at most.

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

      Okay so we just didn't have to clear the dp table each time. Thank you, it was indeed a smart move.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Stack Solution works in O(n) in problem C.