AlexLorintz's blog

By AlexLorintz, 3 months ago, In English

Hi, I recently came across this problem on CSES: https://cses.fi/problemset/task/2184 and the best solution I found is something like O((N + Q) * sqrt(N) * log(N)), but I'm pretty sure there should be a better solution, because this would probably not fit in 1 second.

We know the greedy way of solving it from its easier version: https://cses.fi/problemset/task/2183/ : we need to sort the array and keep a current answer meaning the smallest sum that can't be produced with the elements 1...i(if we are at the ith element in sorted order), which is of course initialized with 1. When we move from i to i+1, if array[i+1] <= currentAnswer, then currentAnswer gets increased by array[i+1](using 1...i we can get every sum from 1...currentAnswer-1 so adding i+1 helps us get all sums from 1...currentAnswer+array[i+1]-1), else we stop and print currentAnswer as the answer to the problem(we will not be able to obtain currentAnswer further on because all elements in the remaining suffix are already too big).

My idea to solve it for queries was to use MO algorithm with a segment tree on normalized values from the array. The problem gets reduced to something similar with: "Find the first index i such that array[i]-preffixSum[i-1] > 1", so it's easy to keep this information in a segment tree for the current useful elements(from the current query interval) using lazy updates and in order to solve the query the answer can be "binary searched" directly in the segment tree in logarithmic time. I'm eager to hear any solution that would fit in the time limit or any observations about my solution if it's wrong.

Read more »

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

By AlexLorintz, 6 months ago, In English

Hello! I've been thinking about this problem for a while and I couldn't be able to come up with a decent solution(basically implementing operations of type 2 and 3 which are the hard ones) and, unfortunately, there's no editorial describing the solution on the internet, only codes(or at least I can't find any editorial). I think the problem is a quite interesting tree task and I was wondering if someone could describe a possible approach to solve it? Problem statement: http://www.math.bas.bg/infos/2019_Shumen/A_day1_en.pdf

Read more »

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