Unofficial Editorial TSEQ August Long Challenge

** Beep Beep **
Unofficial Editorial here.

Been a long time since last time I wrote an editorial unofficially, so thought to give it a try again.

I won’t be following the standard editorial style because My editorial, My rules :stuck_out_tongue:

Do not expect an awesome short and interesting editorial because I’ll try to make it long and boring. :stuck_out_tongue_winking_eye:

So, Let’s get started with the problem TSEQ (the problem i liked the most from august challenge, it’s elegant) (which i assume you have read statement here because I’m not gonna explain statement too).

Time for a combinatorics class first!

  • What’s the number of ways to select K distinct elements in the range (A, B) excluding A and B assuming A +1 < B.
    It’s ^{(B-A-1)}C_{K} since we can select any combination of K elements from B-A-1 choices.

  • What’s the number of ways to select K elements with repetition allowed in the range [A, B].
    It’s ^{(B-A+1 + K-1)}C_K, explained here as I am not explaining.

End of combinatorics class.

Let’s assume we are not given a tree, but an array, and we have to answer the same queries for subarrays.

There are four types of queries, strictly increasing, strictly decreasing, non-decreasing and non-increasing and we have to answer the query for subarray [u, v] and values [A, B]. (Note that for this problem, subarray [u, v] is not same as [v, u].)

But, we can notice that number of ways to get the strictly increasing sequence in subarray [u, v] is same as the number of ways to get strictly decreasing sequence in subarray [v, u]. That’s it, we can just swap the ends of the subarray, whenever we get a query for decreasing or non-increasing sequence.

Let’s answer queries now.
If there is any position in subarray [u, v] containing value smaller than A or larger than B, the answer is already 0. Also, if the sequence is not strictly-increasing/non-decreasing, then too answer is 0.

Considering the subarray [u, v] and value range [A, B], It looks something like following. (… means any number of -1 present).

-1 -1 ...   v1 -1 -1 ... v2 -1 -1 ... v3 -1 -1...      vk -1 -1 ....

Where for each 2 \leq i \leq k, v_{i-1} < v_i or v_{i-1} \leq v_i depending upon query.

Calling C_i as the number of occurrences of -1 after V_i and C_0 as the number of occurrences of -1 at the start. Let’s call these blocks of -1 as sections.

Assume f(x, y, k, strict) gives the number of ways to select k elements from x to y considering strict, or non-strict inequality.

We can see, we can fill each section independently of each other, so the answer is the product of the number of ways to fill each section.

For non-decreasing sequence, The number of ways to fill the section with k occurrences of -1 and values within range [L, R] is same as the number of ways to select K elements with repetition allowed in the range $[L, R]. Remember Combinatorics class? :wink: The range of value can be determined from v_i by being smart.

A similar conclusion can be drawn for a strictly increasing sequence.

Now, considering the very first and very last section, the lower limit and upper limit for sections can be found using A and B given in the query.

But hey! didn’t we calculate the number of ways to fill all sections except border sections without A and B, so let’s precompute them all. Doing for all subarrays is expensive, so a data structure class is necessary, using any range structure such as segment tree would work. But we also need the information about the number of -1 at start and end of array. But we are segment-tree experts, right, and we have solved this problem, so we can make a special node storing all required info and answer queries.

Too Sleepy to take Data structure class now. Suggest topics for a class, and I will take it.

All done, right?
But we are given a tree, how we are supposed to use this array problem in the tree. Turns out, we need another trick under our sleeve, Heavy Light Decomposition Turns out, it answers all our doubts to reduce a path in the tree into an array problem.

Implementation can be tough, but the price of 100 points has never been less. For HLD, take care whether for this node, we are moving up or down (Path from u to v -> Path moving up from u to lca(u, v) and then moving down from lca(u, v) to v).

That’s all for today folks. I’ll try to read any suggestions you offer at the pleasure of myself. :stuck_out_tongue:

All done within an hour (excluding solving time, which is ofcourse, in days :sweat_smile:)

\sout {PS: Someone challenged me that I cannot get more than 25 likes on an editorial. Can you guys help me prove him wrong? Thanks!}
UPDATE: Challenge is up, Defeat conceded by challenger.

EDIT: Adding details about segment tree node, each node represent some segment in segment tree.
Each node contains following data (as per my solution linked below).
contains > boolean whether current range contains any value other than -1.
Left -> if contains is true, this denote smallest value other than -1 in current segment
Right -> if contains is true, this segment denote largest value other than -1 in current segment
lCount -> if contains ia true, then this contains the number of -1 as prefix.
If false, it denotes the number of -1 in range.
rCount -> if contains is true, this stores the number of -1 as suffix.
S -> number of ways to fill all -1 except prefix and suffix such that the sequence is strictly increasing.
NS -> number of ways to fill all -1 except prefix and suffix such that the sequence is non-decreasing.

Refer the node in this solution (ignore TLE, that’s something wrong in lifting). You can view my AC submission, but that is too messy. See that at your own risk :stuck_out_tongue:

Important part in this solution is merge function, and the eval function in node class.

32 Likes

I would have commented something.
[Insert some old jokes related lengthy editorial].
But I will stay neutral. :stuck_out_tongue:

3 Likes

Seems like you missed this. :stuck_out_tongue:

2 Likes

I spent many hours on this problem, but could only get 10 points for the case where all are -1.

In the problem statement it says

INCREASING U V A B : Find the number of ways to replace each −1 in the sequence S(U,V) by an integer between A and B (inclusive) such that the resulting sequence is strictly increasing .

I understood this to mean that if we were given a sequence like 2 -1 5 -1 10 with A = 3 and B = 8, then replacing the two -1 with 4 and 7 would satisfy the conditions. This is different from what you say.

Also it is not clear whether if we are given a sequence with no values of -1 in increasing order there are 0 ways of inserting any more digits, or there is 1 way which is to do nothing.

3 Likes

@david_s I completely agree with you. There problem statement is not clear, and the two points which you mentioned are still unclear to me from the problem statement.
I spent some 5 hrs coding and debugging this solution in the last few hrs of the contest. I submitted it in the last hr, and got only 10 pts for all - 1 case just like yours. Its so disappointing.
But ultimately, what are the answers to the above mentioned unclear statements?
@taran_1407 can you please help us out with this? Can you please check my blog post?

You may want to read the setters notes I put up at the invite thread once.

1 Like

Tch! Tch! Tch!

Pretty sure asking for sympathy votes was not allowed by him :stuck_out_tongue:

2 Likes

In the example you gave, the problem requires you to replace -1s in sequence by any values, such that final sequence (say 2 4 5 7 10) is stricly increasing and have elements in range [3, 8]. But 2 lies outside this range over which we have no control, so number of ways is 0.

I have mentioned this.

For your second doubt.
In combinatorics, not doing anything is also considered one way, as long as conditions are satisfied. In current problem, if no values on path is -1, the number of ways would be 1 if and only if the values on path are strictly increasing, and within range [A, B].

Hope that helps.

Added details. Hope that suffices.
Btw, your post is down, so cant reply there xD

1 Like

Haters gonna say that :crazy_face:

1 Like

@vijju123
Feel free to refer to this while writing official editorial :stuck_out_tongue:

1 Like

Aaaand you just proved my point yourself that YOU are the one boasting :smiley:

1 Like

I understand what you say, but the problem actually states

Find the number of ways to replace each −1 in the sequence S(U,V) by an integer between A and B (inclusive) such that the resulting sequence is strictly increasing .

When I replace all the -1 by values in the range A to B, the result is strictly increasing. It does not say that the entire sequence must be in the range A to B.

Okay, I understand your point now. Let me check.

I ran few accepted submissions and seems like this test was missed in test cases. Some solutions give 0 (Including mine) while some give 6.

Nice catch. I’ll modify the explanation after solving the other version :stuck_out_tongue:

Thanks @david_s

Can U please provide unofficial editorial for Complementing Spanning Tree .
I am unable to understand the concept to solve this problem after reading a
lot on spanning trees and their counts from various resources . Thanks in advance . I will be very very thankful to you.

My brute force code for 20 pts passed even though I had considered only the fact that all the numbers in the path u to v should be the range [a, b] rather than replacing only -1’s in the sequence with nos in the range[a, b](maybe because I misread the problem statement).
e.g seq = {2, 3, -1, -1, 5} and [a, b] = [3, 4], this results in 0 for my case.
The consequence was that I implemented a whole HLD solution keeping this point in mind and kept getting WA until only a few hours were left for the contest.

I assume a basic understanding of matrix transformations and determinant operations.

For CSTREE, All you need to do is to read first about Kirchhoff’s Theorem, and then Page 1 to Page 6 of this paper, especially Theorem 3.1 and 3.2

My approach was to compute the expression at page 6 with m = 1, n = n*k and B as explained in theorem 3.2

I too solved for 100 points believing that. There must be some other issue with your solution in HLD.

Yeah, I agree that there were some errors.
But wait what ? I thought the TC’s were weak only for the 1st subtask :expressionless:
I think @alex_2oo8 should look into this(either update the TC’s or the problem statement as suitable).