Pirate_King's blog

Help in OA problem
By Pirate_King, history, 14 months ago, In English

I'll keep it short.

Bob has an element x and Alice has a permutation p of size n.

Alice goes through the permutation sequentially and asks Bob what is the relation between x and p[i] .

if p[i] < x + 0.5 Bob replies '<' otherwise Bob replies '>'.

Ex: x = 2 and p = [1,3,2] gives us a string "<><" .

Now Alice is smart and does not ask unnecessary questions.

Ex: x = 2 and p = [3,4,1,2] will gives us a string "><<"

Here Alice ignores the 2nd element because in first question she determined that 3 > x+0.5 so of course 4 is also going to be greater than x+0.5 .

Let c be the number of times "><" occurs as a substring in our resultant string. Find all c for x in range 0 to n.

input:

6

5 1 2 4 3 6

output:

0 1 1 2 1 0 0

I did a brute force O(n^2) solution using stack but as expected got TLE in some tc's as n<=2*1e5. Can someone please guide me towards an efficient solution

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

»
14 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

UPD: I understood the problem incorrectly. Nothing I said is related to the actual problem.

Let's consider all positions of the string where we could have >< separately.

For consecutive elements $$$p_i$$$ and $$$p_{i+1}$$$ of the permutation if we wanted to get a >< for these elements, $$$x$$$ must satisfy $$$p_i \ge x + 0.5$$$ and $$$p_{i+1} < x + 0.5$$$.

These are equivalent to $$$p_i > x$$$ and $$$p_{i+1} \le x$$$, i.e. $$$p_{i+1} \le x < p_i$$$.

If $$$p_{i+1} \ge p_i$$$, the inequality is never satisfied. Otherwise it's satisfied for all $$$x$$$ in range $$$[p_{i+1}, p_i)$$$ which means that in this position we get a >< for all $$$x \in [p_{i+1}, p_i)$$$. Thus, we need to increase the count of >< for all $$$x$$$ in that range, and repeat this for all pairs of adjacent elements.

Range add operations can be performed in multiple ways, but since we only need the resulting array, we can do them in $$$O(n)$$$ total with difference arrays.

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But it is not necessary that Alice asks a question for all x in the range no ?

    Like if p = [6,10,3.....] we cannot increment the count for all x in range [3,10) as for all x >= 6 we will be ignoring the third element

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, I missed this: Now Alice is smart and does not ask unnecessary questions. Sorry! I'll reply later if I come up with a solution to the actual problem.

      → Reply
»
14 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

>< for 1 means [2..n][1..1], for 2 [3..n][1..2] something like

map index = x -> i;
n_before(x, predicate) = predicate(a[index[x] - 1]) ? 1 : 0
n_after(x, predicate) = predicate(a[index[x] + 1]) ? 1 : 0
dp[x] = dp[x-1] - n_before(x-1, <=x) - n_after(x-1, <x) + n_before(x, >x) + n_after(x,<x)
ans = dp

comes to mind. And since it's permutation indexing should be unique and log(n) or better

→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I was curious and implemented it to try, seems to work in O(n) time and memory:

        let c = |x: usize, inc: isize, r: Range<usize>| {
        if let Some(z) = aa.get((idx[x] as isize + inc) as usize) {
            std::println!("{:?}", (x, inc, &r, z));
            if r.contains(&z) {
                1
            } else {
                0
            }
        } else {
            0
        }
    };

    let mut dp = 0;
    for i in 1..n {
        dp += c(i, -1, i + 1..n) - c(i, 1, 1..i);
        std::println!("{i}: {dp}");
    }

    Output:

    (1, -1, 2..7, 5)
(1, 1, 1..1, 2)
1: 1
(2, -1, 3..7, 1)
(2, 1, 1..2, 4)
2: 1
(3, -1, 4..7, 4)
(3, 1, 1..3, 6)
3: 2
(4, -1, 5..7, 2)
(4, 1, 1..4, 3)
4: 1
(5, -1, 6..7, 0)
(5, 1, 1..5, 1)
5: 0
(6, -1, 7..7, 3)
(6, 1, 1..6, 0)
6: 0
    → Reply
»
14 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I can think of nlogn solution,firstly we will form an array where it's element will be a pair [p[i],p[i+1]] for all i where p[i]>p[i+1], let's call it array interval,sort interval according to first element of pair,and make a ordered map containing [second element of pair ],now we run a loop for ans we ready for 0 to n,now for each x we do binary search on first pair of element,and remove second pair which comes befor it from ordered map,and the total numbers less than x in the ordered map will be ans for x,we can keep track of which index was last selected for removal,also keep in mind 0.5

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

isn't it this problem from USACO?

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yup this is it. Thanks man

    it seems they copied word for word from here

    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How many TCs were you able to pass for each problem?

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You gave it too ?

    for this question brute force was able to pass 6/8 and other 2 passed all tc's

    → Reply