The first stage of the National Olympiad in Informatics in Romania is taking place this Saturday, so this week there were hosted some practice contests on the Romanian OJ kilonova.

I participated in one of them and one of the problems basically sounds like this: "You are given 3 numbers $$$A,B,C(A,B,C \le 3000)$$$, count the number of strings that have $$$A$$$ letters a in them, $$$B$$$ letters b and $$$C$$$ letters c and also don't have abc as a substring".

As I have some skill issue when it comes to combinatorics and dynamic programming, I did not manage to solve the problem for a full score but, my interest for this problem came back to life while talking to Matteo.Verz, who told me that he managed to solve the problem (we both tested and his solution gets a full score) in linear time. I was quite surprised because the constraints allowed solutions with a quadratic time complexity and all of the solutions that I heard about were also quadratic. After explaining me his thought process and showing his code, I realized that his solution uses the same idea that I actually tried in the contest, but with a very small change.

Now here comes the problem: neither me nor Matteo.Verz nor tibinyte nor anyone that I tried to discuss this problem with understands why this solution works, so we decided to ask the amazing community of codeforces hoping to get an answer. There are 2 almost identical solutions for this: here and here.

Let's consider the first solution. There $$$dp_i$$$ is the number of strings that contain exactly $$$i$$$ abc substrings. Now here come some questions:

• If this is the case, why don't we need to subtract all values of $$$dp_{i + 1}$$$, $$$dp_{i + 2}$$$ and so on from $$$dp_i$$$ to compute it correctly?

• The formula used for initializing $$$dp_i$$$ is quite strange as it counts some strings multiple times, like when having $$$1$$$ abc group and $$$1$$$ unused character from each a, b and c, it will count the string abcabc twice, but the solution is still giving the correct result.

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.

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