You are not logged in. Please login at www.codechef.com to post your questions!

×

CO92REST - EDITORIAL

Author: Trung Nguyen
Tester and Editorialist: Alei Reyes

Problem Link

Practice
Contest

Difficulty

Easy-Medium

PREREQUISITES:

Data Structure

Problem

We are given an array A with some elements and some unknowns. The goal is to find the number of possible arrays with numbers from 1 to k that satisfies certain constraints. Every constraint forces us to make some interval either strictly increasing or strictly decreasing in steps of one.

Explanation

Let's store the information of constraints in another way. Let dx[i] = how much we have to add to A[i] to get A[i+1].

  • If interval from L to R should be increasing, then dx[L] = dx[L + 1] = ... = dx[R - 1] = 1;
  • If interval from L to R should be decreasing, then dx[L] = dx[L + 1] = ... = dx[R - 1] = -1;

For some elements there are no constraints and we have more freedom, for sake of simplicity let's define its dx value as 0.

Note that all information about constraints is stored in dx. Moreover the structure of dx is as follows: [C][0][C][0][C][0]... Where each [C] represent a block of contiguos cells with values either 1 or -1, and [0] represents a block were dx is 0.

Let's see in how many ways is possible to complete the array A for every type of block.

  • Blocks of type [C]:

    If array A contains at least one known element in the block, then all the elements are determined, and we only have to check their values.
    Otherwise, suppose that the first element is 0, and calculate the maximum and minimum values in the block (this can be done by adding the values of dx). We can generate new possibilities by adding some constant c to all the elements of the block, however c + minimum ≥ 1, and c + maximum ≤ k (remember that all numbers should be between 1 and k).

  • Blocks of type [0]

    In this case, we have more freedom and we can set any value between 1 and k. Except for the first element, it can be uniquely determined if the previous element of dx is 1 or -1.

The only question that remains is how to generate array dx. If we iterate over every constraint it is quadratic. However, if constraints are not overlapping it is linear.

Note that is not necessary to store overlapping intervals (constraints). For example, if segments [3, 5] and [4, 6] should be increasing, then is the same as saying that [3,6] is increasing. Therefore we can merge intervals and get only non-overlapping intervals.

There are many ways of merging intervals. For example, we can keep a set of disjoint intervals. Let's say that interval [l1, r1] is smaller than [l2, r2] iff r1 < l2. When we add a new interval to the set, we have to remove all the intervals that intersect it (we can find them with binary search) and add a new interval. Every interval is added and removed at most once, so it is asymptotically efficient.

Implementation

Author's Solution
Tester's and Editorialist's Solution

This question is marked "community wiki".

asked 18 Mar '18, 23:43

alei's gravatar image

7★alei
2315
accept rate: 0%

edited 23 Mar '18, 01:06


I know that i should merge queries ... I was looking at editorial to find how to do that.. can anyone help me ?? this editorial only contains logic which i already knew... how to do it optimally in code is my question and motto of viewing editorial...

link

answered 22 Mar '18, 18:50

l_returns's gravatar image

5★l_returns
1.4k19
accept rate: 25%

edited 22 Mar '18, 18:52

1

I added another paragraph explaining that. For reference, in editorialist code, the function "add" adds the interval to the set keeping all intervals disjoint.

(22 Mar '18, 21:08) alei7★

thanks... :)

(31 Mar '18, 16:57) l_returns5★

Is there any other way to solve this question? Thanks in advance.

link

answered 22 Mar '18, 17:46

mayankbajaj269's gravatar image

4★mayankbajaj269
111
accept rate: 0%

In the author's solution and in the line - if (a[k] < 1 || a[k] > ::k) res = 0; what is the meaning of ::k ? what does a[k]> ::k give ?

link

answered 25 Mar '18, 11:59

chari407's gravatar image

2★chari407
44827
accept rate: 0%

If there are two increasing sequence [1..5], [10.. 15] And one decreasing sequence [5 10] How will divide the block in [c][0][c]

link

answered 25 Mar '18, 15:20

kamal_kulu_23's gravatar image

4★kamal_kulu_23
1
accept rate: 0%

@kamal_kulu_23, This case will not have the block [0]. So, it can be represented as, [c][c][c], where, the first [c] is a block with increasing values [1,1,1,1], second [c] will be [-1,-1,-1,-1,-1] and the third would be [1,1,1,1,1].

(25 Mar '18, 22:01) chari4072★

Can someone please explain me how are we calculating number of ways = k-(max-min) for a range having all unknown elements(a[i]=-1) using sum,max,min from dx[]

We can generate new possibilities by adding some constant c to all the elements of the block, however c + minimum ≥ 1, and c + maximum ≤ k (remember that all numbers should be between 1 and k)

link

answered 26 Mar '18, 14:22

dushyant7917's gravatar image

5★dushyant7917
716
accept rate: 0%

edited 26 Mar '18, 22:41

Perhaps an elegant way to generate array dx[] can be

for (int i = 0; i < n; ++i)
    adi[i] = add[i] = 0;
for (int i = 0; i < m; ++i) {
    char c;
    int l, r;
    cin >> c >> l >> r;
    --l;
    --r;
    if (c == 'I')
        ++adi[l], --adi[r];
    else
        ++add[l], --add[r];
}
for (int i = 0; i < n; ++i)
    dx[i] = 0;
int ni = 0, nd = 0;

for (int i = 0; i < n ; ++i) 
{
    ni += adi[i];
    nd += add[i];
    if (ni && nd) {
        cout << 0 << "\n";
        return;
    }
    if (ni)
        dx[i] = 1;
    else if (nd)
        dx[i] = -1;
}
link

answered 26 Mar '18, 19:13

sonu_628's gravatar image

4★sonu_628
3458
accept rate: 8%

edited 26 Mar '18, 19:21

can we make array dx[] with the help pf segment trees? how much will be its time complexity? O(mlogn) i guess?

link

answered 31 Mar '18, 00:41

ayushgoyal1703's gravatar image

4★ayushgoyal1703
222
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,683
×1,672
×843
×32
×7

question asked: 18 Mar '18, 23:43

question was seen: 1,781 times

last updated: 31 Mar '18, 16:58