Always the most interesting problems is coming soon!

" Well, if you look close you see that each psycho is murdered by the nearest psycho on his left which has a greater id" are u sure this statement is correct? (10 9 1 2 3 4 5 6 7 8, 8 is killed by 10, not 9) Anyway it doesn't affect the following solution.

for Problem C (div 2) or Problem A (div 1) here is a much better solution. We have to find number of pairs (a,b) & (c,d) such that a < c and b > d. Obviously if a < c then we can assume in binary a is of the form A0B and c is of the form A1C where 'A' is the starting set of bits that are same in both. For example, if a= 111010 and c= 111111 then here A= 111, B=10 and C= 11. Now when we perform b= a xor x and d= c xor x then A would get converted to a new set of bits (say D) which is same in both case. Now in order to make b>d we should have 1 in x in a position of 0 after A in a which would convert 0 in a to 1 and 1 in c to 0 making b>d. So let us have a binary string x. For each i (1-based) such that x[i]='1' we can have pow(2,i-1) possibilities for A, pow(2,n-i) possibilities for B and pow(2,n-i) possibilities for C.

We are looking forward to D-E problems editorial.

I would be more than happy if you tell me whether my thoughts about 319D - Have You Ever Heard About the Word? were right or not.

Here is my blog entry: http://codeforces.net/blog/entry/8150

Thank you.

In 319C — Kalila and Dimna in the Logging Industry, how can one prove that the answer fits in a 64 bit int? Can't we have a solution where we have to cut trees in order i=0,1...n and the values are similar to - a[1]=10^9-n, a[i]=a[i-1]+1 if i>1 - b[0]=10^9,b[i]=b[i-1]-1 if i<n-1 - n=10^5.

Regarding 319B, my solution goes like this:

First, let's try a O(N^2) approach. Because why not :D We process psychos from left to right, and remember psychos that live before turn k in an array T[k] (so T is a 2D array; it's sufficient to only consider 0 <= k <= N). The leftmost one always lives. Now when adding the next psycho, we go from turn 0 to turn N and if the rightmost psycho that lives before turn i has larger id, then this added psycho dies at turn i+1, so we append him to the ends of T[0 <= k <= i] (or to T[0 <= k <= N], if he never dies). The answer is maximum of all i+1 of dying psychos (or 0 if the sequence is decreasing). This is just a bruteforce, but it's constructed positionwise and not timewise.

It's actually easier to optimize this approach to O(N).

First, observe that we're only interested in the last element of every T[k]. So we make T[k] an integer and we assign to this variable instead of appending to an array.

Next, we remember just intervals of equal values in T[], on a stack — for each interval, we remember the value and its right end (the left end is given implicitly by the previous one), and as they'd go from left to right, we remember them top to bottom.

Now, we do the same thing as in bruteforce, but go over entire intervals of equal values of T[] in 1 step, instead of going over separate values. The trick to time complexity is here: each of N intervals is added at most once, and if we replace all values in it by a new interval, we delete it also at most once, so the total time is O(N).

Implementation: 4050295

Heyi havaliza , can you please fix the tutorial for the Psychos in a Line problem ?

I'll take the liberty to write some comments about these problems that aren't covered in the editorial.

First Problem B (Psychos): I have 2 solutions for this one. The simpler one to code and explain is this. The idea is as follows. You want to compute for each psycho the "time" (i.e. turn) in which it gets killed (I call this tdeath[i] in the code). The solution is then the max of all these times plus 1. The key observation is that tdeath[i] cannot depend on anything that happens to the right of the psycho, i.e. it is completely determined by what happens on its left.

So, how is it determined by what happens on the left? If there's a taller psycho directly to your left, you will die right away (in turn 0). However, if there is a shorter psycho directly to your left, you can't possibly die before he does. Now, if he gets killed by a psycho that is taller than you, that psycho will also kill you in the very next turn. Otherwise, if the psycho just left of you gets killed by a psycho that is still shorter than you, you have to wait for that psycho to get killed before you die. This can go on for some time before ultimately a taller psycho comes along and kills you. The idea is to store this sequence of "active" psychos on a stack and process the whole line from left to right.

It turns out it is convenient to set tdeath of psychos that don't ever die to -1. The first psycho has tdeath = -1, and we put him on the stack. Now for the ith psycho, we look at the top of the stack. If the psycho on the stack is shorter than the ith psycho, we update the ith tdeath and pop the stack. We can pop the stack because the psycho on the top of the stack will not kill any psychos to the right of the ith one. Furthermore, if we emptied the stack by this procedure, that means that the ith psycho is the tallest psycho in this prefix of the line so it never dies (set tdeath to -1).

Since any psycho can be pushed and popped to/from the stack at most once, the time complexity is O(N).

The second solution that I thought of first but is a bit harder to code is the following. We use a tournament tree to find the tallest psycho in some interval. We represent the line with a random-access doubly linked list and we simulate the process. The code is here. So, in the tournament tree, M is the maximal height in the interval represented by a node and P is the original position of the tallest psycho in that interval that isn't already dead. The change function does one iteration of the process. First, you find the tallest psycho and remove the decreasing subsequence to its right. You recurse on the left of the tallest psycho and on the part after the decreasing subsequence. The key optimization that makes this run in time is that if there is no change in some interval at any point in time, there can't be any change later on either (that's what the line T.kill(l, r) does).

I'm not completely sure what the worst case for this algorithm is. When there is a change in every tried interval, there will be at most around logN rounds so the run time will be about O(NlogNlogN). If there are no changes in some intervals, then that part of the line will be skipped in all further rounds. If anyone can come up with a case to fail this solution or to describe the worst case, I'd be grateful for the reply :)

can anyone explain how to use convex hull trick in 319c, i want to exactly know about the fact that how to convert this question into y=kx+b lines question sorry for very bad english ...

You're too lazy to write the editorial for a problem? Just write TODO and problem solved ;)

https://codeforces.net/problemset/problem/319/C

I did not understand the problem C clearly. Please anyone explain what we have to do elaborately?

Thank you.

For the Editorial for Problem A : I didnot understand the condition :

if (number[i] != '1' && number[i] != '4')
			return false;

What is the logic of checking under && condition.??Can somebody please explain this?Thanks

Can someone please explain why I am getting MLE in 319B - Psychos in a Line for this solution? Code- 83289131

You are so pigeon

I'm still waiting for 319B havaliza

IN 320B
why this is not working 145740758

Idk why 319B is crossed out, and no one mentioned this approach so here is my solution:

Just simulate each turn. It's clear that if we can process one death in $$$O(1)$$$ then the solution would be $$$O(n)$$$, since there are at most $$$n - 1$$$ death.

If we store the psycho in a linked list, then we can easily find out who will be death in the next turn by just checking whenever 2 elements become adjacent. One simple way to process multiple death in one turn is just to process them from right to left, you can see my implementation here: 179449591.

I think this approach was overlooked because linked-list are often neglected by CPers.

319B)
My approach

• Just simulated the whole process of maintaining set data structure
  For the next iteration

• Efficiently iterating only through indices where recent changes were made.

A hack of 319E:

Input: 5 1 1 3 1 2 5 1 1 5 2 1 3 2 3 1 Output: YES NO

You will be wrong in this case if you judge two different segments after merge which have same value incorrectly.

Bump for editorial

these TODOs aren't still done, also the div1 B ain't fixed YET

For Div1-B/Div2-D, the following works:

Observe that we can assign a round-of-death to each number. So, for the given example, we have the following:

Heights:   [10 9 7 8 6 5 3 4 2 1]
KillTimes: [-1 0 0 1 0 0 0 1 0 0]

We can use -1 for the psychos that do not die at all. For the second example, we have:

Heights:   [1 2 3 4 5 6]
KillTimes: [-1 -1 -1 -1 -1 -1]

Now, we can see that the total number of rounds = 1 + max(KillTimes). So, if we can efficiently compute KillTimes we are done.

We can maintain a list of active_killers and proceed in the following way:

[10] -> Person 0 is the only active killer and their kill_time is -1[10 9] -> Both 0 and 1 are active killers and kill_time[1] = 0
[10 9 7] -> All 0,1,2 are active killers and kill_time[2] = 0
[10 9 7 8] -> Now, 7 fails to kill 8, which means that 8 will survive for atleast one more round in comparison to 8. Therefore, kill_time[3] = 1. Further, we notice that height 7 can no longer be the one to kill anyone to the right. Therefore, we can remove them from list of active killers. Further, we can see that the kill_time[1] = 0 which means that despite having a greater height (9) in comparison to current height (8), psycho at index 1 cannot be the one to kill psycho at index 3. Therefore, we can once again remove them list of active killers. So, the new active_killers are 0 and 3.
[10 9 7 8 6] -> As height 6 is lower than 8, psycho 4 would be killed by psycho 3, and the list of active_killers would have 0, 3 and 4.
.. the process continues so on.

If at any time we run out of killers, then the ith psycho would have a kill_time of -1 as it would stay alive till end of all rounds.

    std::stack<int> killers;
    std::vector<int> kill_time(num, 0);
    kill_time[0] = -1;
    killers.push(0);
    for (int i = 1; i < num; ++i) {
        while (!killers.empty()) {
            int cur_killer = killers.top();
            if (kill_time[cur_killer] != -1 && kill_time[cur_killer] < kill_time[i]) {
                killers.pop();
            } else if (height[cur_killer] < height[i]) {
                kill_time[i] = std::max(kill_time[i], kill_time[cur_killer] + 1);
                killers.pop();
            } else break;
        }
        if (killers.empty()) kill_time[i] = -1;
        killers.push(i);
    }
    std::cout << *std::max_element(kill_time.begin(), kill_time.end()) + 1 << std::endl;

Sorry for necroposting but problem 320A has a simpler brute force solution. Since none of the strings are suffixes of each other it suffices to search by removing every single suffix recursively, terminate when we reach the strings "1", "14" and "144" themselves. I use Python but it shouldn't be hard implementing the same thing in C++.

def ismagic(s: str) -> bool:
    for i in ["1", "14", "144"]:
        if s == i:
            return True
        elif s.endswith(i):
            return ismagic(s[:-len(i)]) # remove the suffix
    return False

Update: never mind this has probably exponential time complexity, the only thing that didn't bit me in the ass was the small value of $$$|N|$$$ (I'm treating $$$N$$$ as a string)

I solve div 1 B with monotonic stack + segment tree. For each index i-th find the nearest greater element to the left (if not exist then clearly i-th will not be erased) we call this nearest index j. We use mono stack to find j. And for each i, if j exist, i will be cleared at 1 + max(j + 1, i — 1) (we need to erase all element between i and j before can clear i). To query max in range [j + 1, i — 1], we use segment tree with point update.

[submission:https://codeforces.net/contest/319/submission/297127565]