UpAndDown's blog

By UpAndDown, history, 4 weeks ago, In English

Hello Codeforces,

I have prepared a mashup. It'll take place on Thursday at 17:35 (UTC+3). You will be given 7 problems and 2 hours and 15 minutes to solve them.

I did my best to do this problems:

Challenging, interesting, only in A algorithms and data structures aren't used.

With clear statements

Available in Russian and in English

Difficulties are 800-1600-1700-1700-1800-2000-2400

UPD: The registration is opened now.

Congrats to MarioPariona117 and pavlovoleg4889 for solving all the problems!

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

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

Can someone tell, how to implement C in less than O(n^2)? The brute force would be for the current range pick the minimum, subtract it from a and add that to b. Am I right?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Use sparse table to calculate the minimum. The preparation will take O(n log n). Then just cover the maximal possible ranges with segments.

    Code
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I implemented C using stack. In stack there are elements always in increasing order. When you add element that is smaller than top element, you erase all elements from stack that are greater than should be.

    For example, let $$$a = [1, 5, 7, 2, 4]$$$.

    Step $$$1$$$: $$$s = [1]$$$, $$$b = [0, 0, 0, 0, 0]$$$

    Step $$$2$$$: $$$s = [1, 5]$$$, $$$b = [0, 0, 0, 0, 0]$$$

    Step $$$3$$$: $$$s = [1, 5, 7]$$$, $$$b = [0, 0, 0, 0, 0]$$$

    Step $$$4$$$: $$$s = [1, 5, 7]$$$, you pop last element($$$7$$$) and add $$$2$$$ to the range $$$[3, 3]$$$. Now $$$b = [0, 0, 2, 0, 0]$$$

    Step $$$5$$$: Now $$$s = [1, 5]$$$. Then you pop last element again ($$$5$$$) as it is greater than $$$2$$$ and add 4 to the range $$$[2, 3]$$$. Now $$$b = [0, 4, 6, 0, 0]$$$.

    Step $$$6$$$: Now $$$s = [1, 2]$$$ and $$$b = [0, 4, 6, 0, 0]$$$.

    Keep going like that and you will construct the array. Time complexity: $$$O(n)$$$.

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

      Can you explain how are you deciding the range to which we add, like in step 4 you said, add 2 to the range [3, 3]. Why is that?

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

        We add to the range from element of top of the stack (in this case $$$7$$$, index $$$3$$$) to the element in which we are currently in (in this case $$$2$$$, index $$$4$$$) minus 1.

        In step $$$4$$$ we add 2 to the range $$$[3, 4)$$$.

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

Auto comment: topic has been updated by UpAndDown (previous revision, new revision, compare).