### havaliza's blog

By havaliza, 8 years ago,

## 320A - Magic Numbers

Although the input number is very small, solving the problem for arbitrary length numbers using strings is easier. It's easy to prove that a number meeting the following conditions is magical:

• The number should only consist of digits 1 and 4.
• The number should begin with digit 1.
• The number should not contain three consecutive fours (i.e. 444).

Here is a sample implementation in C++:

#include <iostream>
#include <string>

using namespace std;

bool is_magical(string number) {
for (int i = 0; i < (int)number.size(); i++)
if (number[i] != '1' && number[i] != '4')
return false;

if (number[0] == '4')
return false;

if (number.find("444") != number.npos)
return false;

return true;
}

int main() {
string number;
cin >> number;

if (is_magical(number))
cout << "YES" << endl;
else
cout << "NO" << endl;

return 0;
}


## 320B - Ping-Pong (Easy Version)

Imagine the intervals as nodes of a graph and draw directed edges between them as defined in the statement. Now answering the second query would be trivial if you are familiar with graph traversal algorithms like DFS or BFS or even Floyd-Warshall!

Here's an implementation using DFS: 3951145

And here's an implementation using BFS: 3947426

Finally an implementation using Floyd-Warshall: 3945330

## 319A - Malek Dance Club

Solving this problem was easy when you modeled the assignment with two sets of points numbered from 0 to 2n - 1 (inclusive) paired with 2n line segments. Each line segment corresponds to a dance pair. And each pair of intersecting lines increase the complexity by one.

Imagine you now the solution for binary string x. Now we want to calculate the answer for 1x and 0x easily. Look at the figure below:

The figure shows what happens in a simple case. Whenever you append 0 before x the same structure appears twice in the result. But whenever you append 1 before x the same structure appears twice but the first half of points in right column are swapped with the second half. This increases the number of intersections by size of first half times size of the second half.

So if x has length n and f(x) is the complexity of the assignment then we have:

• f(0x) = 2f(x)
• f(1x) = 2f(x) + 22n

An interesting fact is that f(x) is equal to x2n - 1.

## 319B - Psychos in a Line

Will be fixed :)

Let's find the murderer! Well, if you look close you see that each psycho is murdered by the nearest psycho on his left which has a greater id.

Now let ti be the number of the step which i-th psycho in the line is murdered (not the psycho with id equal to i). Assume j-th psycho in the line be the nearest psycho with a larger id than i-th psycho in the line in his left. As we know j-th psycho kills the i-th psycho. We also now that this happens when all psychos between j and i have been killed. So ti = max(tj + 1, ..., ti - 1) + 1.

Now we have a simple O(n2) solution using the above observations. To make things run faster you should be familiar with a classic problem. This problem asks to find the nearest greater element to the left of each element in a array. This problem has a O(n) solution. You can solve it yourself or read about it here.

After knowing about all these things it wouldn't be hard to figure out a way to solve this problem efficiently. Here is a cute implementation of what is described above: 3945963

## 319C - Kalila and Dimna in the Logging Industry

This problem is equal to finding the minimum cost to cut the last tree completely. Because any cutting operation can be done with no cost afterward. Let dpi be the minimum cost to cut the i-th tree completely. It's easy to figure out that we can calculate dpi if we know the index of the last tree which has been cut completely (j-th tree). Knowing this dpi would be equal to dpj + bjai. So dpi = minj = 1..i - 1(dpj + bjai).

Using the above information the problem has an easy dynamic programming solution in O(n2). There's a known method which can be used to improve recursive relations with similar form. It's called Convex Hull Trick. You can read about it here.

TODO

## 319E - Ping-Pong

TODO

• +12

 » 8 years ago, # |   +1 Always the most interesting problems is coming soon!
•  » » 8 years ago, # ^ |   +3 Well, that's because I'm tired right now. I hope I don't get lazy and do the rest of the editorial in the morning! :D
•  » » » 8 years ago, # ^ |   +2 Well , I meant maybe the editorialist should start writing the solution of hardest problems first then if he/she got tired or something happened prevented her/him from continuing writing the editorial then the easiest problems will be coming soon ..
•  » » » 22 months ago, # ^ | ← Rev. 2 →   0 Any updates on the TODO.
•  » » » » 6 months ago, # ^ |   +5 Tomorrow never does
•  » » 8 years ago, # ^ |   +10 http://www.shuizilong.com/house/archives/codeforces-round-189/ （Solution for problem E. Chinese ...
 » 8 years ago, # |   +2 " 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.
•  » » 8 years ago, # ^ |   0 I had the idea of the solution in my mind. Looks like I've made a mistake, Since I haven't done the preparation of this problem.I'll fix it tomorrow, thanks for mentioning.
•  » » » 8 years ago, # ^ |   +3 Hope it will be fixed soon, thanks.
•  » » » 8 years ago, # ^ |   0 I hope you can manage to fix it soon. Thanks:)
•  » » » 4 years ago, # ^ |   0 havaliza, I think the tutorial will be updated after an massive earth-quake! :p
•  » » » 11 months ago, # ^ |   0 havaliza , tutorial is coming or not
•  » » » » 11 months ago, # ^ |   +2 LOL, he found his problem so hard that he couldn't update the tutorial for 7 years
•  » » » 8 months ago, # ^ |   0 havaliza. it is now 7 years of the tutorial. tomorrow never comes. :)
•  » » 8 years ago, # ^ |   0 I think the solution goes more like this. A given psycho X will be killed only when all elements for which X is the first greater element to the right from them is killed. And the life time of X will max of life times of those elements plus one. So the algorithm does the linear solution for finding next greater element for each element while tracking also the life times as items are popped off the stack.
•  » » 3 years ago, # ^ |   0 Yes you are right, each psycho X is murdered by the nearest psycho on his left which has a greater id Y, Unless Y is itself not murdered by another psycho Z, which will take its place , but it won't take affect the solution since in that case Y will be killed by Z before it reaches X or else Y will kill X itself.
 » 8 years ago, # | ← Rev. 2 →   0 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.
•  » » 6 years ago, # ^ |   0 vary good explaination , i didnot get the editorial's solution but your explaination is perfect and easily understandable
 » 8 years ago, # |   +5 We are looking forward to D-E problems editorial.
•  » » 8 years ago, # ^ |   0 Problem D: Seems that brute force works here if done well. The complexity is quadratic, but the constant is (I think) around 3/8. Since the operations you are doing are fairly simple and linear (which is good for caching), that seems to be good enough. I'm pretty sure the worst case for this solution is where you actually don't have any changes in the string so it's easy to test for timeout.I've seen a few solutions that use hashing to test if it's possible that there will be a pair of a certain length and only then try to actually find it. For this kind of solution, the worst case seems to be one where there are a lot of changes (perhaps one per size to minimize the string length reduction) because you need to recompute the hashes when a change happens. On the other hand, it's blazingly fast when there are no changes. Since changes reduce the size of the string, I think you can only have about sqrt(N) different length pairs.
 » 8 years ago, # | ← Rev. 3 →   +41 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.com/blog/entry/8150Thank you.
 » 8 years ago, # |   0 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
•  » » 8 years ago, # ^ |   0 Realized that there is always the option of cutting tree a[i] directly after cutting the first tree. Hence, the answer will never exceed 10^14 (= 10^5 * 10^9) . Silly me.
•  » » » 7 years ago, # ^ | ← Rev. 3 →   0 The answer may exceed 10^14, for a case like, 2 1 1000000000 1000000000 0 But we can prove that the answer won't exceed 10^18 because in the extreme case, b[0] = 1e9 and a[n] = 1e9 and in that case it's sufficient to cut the n th tree to the ground right after the first one. So it is proved that the result will always <= 1e18 :-)
 » 8 years ago, # |   0 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
 » 8 years ago, # |   +5 Heyi havaliza , can you please fix the tutorial for the Psychos in a Line problem ?
•  » » 8 years ago, # ^ |   0 What's wrong with it in the first place and why is it striked out?
 » 8 years ago, # |   +3 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 :)
•  » » 8 years ago, # ^ |   0 What is tournament tree ? i think same thing is possible with segment tree !!BTW, thanks for the explanation. :)
•  » » » 8 years ago, # ^ |   0 It's probably the same thing. I've heard tournament trees called "segment trees" and "interval trees" (though there's a different data structure called "interval tree" that stores a dynamic set of intervals and answers the query "is there an interval intersecting [a, b] in the set" in logarithmic time).If you look at wikipedia's definition of a "segment tree" (http://en.wikipedia.org/wiki/Segment_tree), you'll see that it's more in in line with what I've described above for an interval tree.I like the name "tournament tree" because if you draw this tree, it actually looks like a 2^n players single elimination tournament bracket (i.e. it's a complete binary tree).
 » 7 years ago, # |   0 To be fixed, todo, todo .. Seriously i need solutions :S
 » 7 years ago, # |   0 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 ...
•  » » 7 years ago, # ^ |   0 probably you should learn convex hull better, then the solution will be obvious for u
•  » » 7 years ago, # ^ |   0 ur english is ok
 » 7 years ago, # |   0 D &E?....
 » 6 years ago, # |   0 You're too lazy to write the editorial for a problem? Just write TODO and problem solved ;)
 » 5 years ago, # | ← Rev. 2 →   0 Problem C: Anyone knows why there must be the "(double)" in the inequality? Without the type change, it is incorrect.19613128EDIT: unfortunately, it is a long long overflow problem, so change to double can pass
 » 3 years ago, # |   0 solution to Div1 B using priority_queue code
 » 21 month(s) ago, # |   0 https://codeforces.com/problemset/problem/319/CI did not understand the problem C clearly. Please anyone explain what we have to do elaborately?Thank you.
 » 14 months ago, # |   0 will be fixed? 7 years later, still waiting
 » 12 months ago, # |   0 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
•  » » 12 months ago, # ^ |   0 It is checking , if any digit in the input is neither 1 nor 4, then straight away, saying, that the answer is "NO". Because in the question it is mentioned, that the number Shou only consist of digits 1 & 4.
•  » » » 12 months ago, # ^ |   0 Thanks for the clarification.Can we use statement in or like if(s[i] != '1' || s[i] != '4') meaning if we have either not 1 or not '4' then return false.?
•  » » » » 12 months ago, # ^ |   0 No... Bro.. because that way this if condition will become true for every digit. See lets say digit is '1'. if(s[i] != '1' || s[i] != '4') return false;if( false || true) So overall condition becomes true. And it returns false. It is not correct.
•  » » » » » 12 months ago, # ^ |   0 Thanks @iambjain for clearification.I was confused thanks a lot for the insights.
•  » » » » 12 months ago, # ^ |   0 The and condition is important... Because we can return false only when a digit is not '1' AND at the same time it is also not '4'.
 » 11 months ago, # |   0 Hi everyone! Here you can find English Tutorial of Question 319B - Psychos in a LineMy Blog Entry : https://codeforces.com/blog/entry/78199Thank You.
 » 10 months ago, # | ← Rev. 2 →   0 Can someone please explain why I am getting MLE in 319B - Psychos in a Line for this solution? Code- 83289131
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 void val(vector a, int &count)When you pass a vector to a function, the entire contents is copied to a new vector and the old one stays in memory, so your old ones aren't getting cleared and you are using too much memory by saving them. You can pass by reference, but it seems that that won't make your code pass. Simulating the operations gives TLE (I tried it). Therefore try to improve your algorithm.
•  » » » 10 months ago, # ^ | ← Rev. 2 →   0 Thanks for your help.I get it now
 » 6 months ago, # |   -6 You are so pigeon