Блог пользователя Pirate_King

Help in OA problem
Автор Pirate_King, история, 13 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
13 месяцев назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    13 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      13 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
13 месяцев назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

>< 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

→ Ответить
  • »
    »
    13 месяцев назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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
    → Ответить
»
13 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
13 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

isn't it this problem from USACO?

→ Ответить
»
13 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить