codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

319.md (5275B)


      1 Source: https://codeforces.com/blog/entry/8166
      2 
      3 ## [320A - Magic Numbers](/contest/320/problem/A "Codeforces Round 189 (Div. 2)")
      4 
      5 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:
      6 
      7 * The number should only consist of digits 1 and 4.
      8 * The number should begin with digit 1.
      9 * The number should not contain three consecutive fours (i.e. 444).
     10 
     11 Here is a sample implementation in C++:
     12 
     13 ```
     14 #include <iostream>
     15 #include <string>
     16 
     17 using namespace std;
     18 
     19 bool is_magical(string number) {
     20 	for (int i = 0; i < (int)number.size(); i++)
     21 		if (number[i] != '1' && number[i] != '4')
     22 			return false;
     23 
     24 	if (number[0] == '4')
     25 		return false;
     26 
     27 	if (number.find("444") != number.npos)
     28 		return false;
     29 
     30 	return true;
     31 }
     32 
     33 int main() {
     34 	string number;
     35 	cin >> number;
     36 
     37 	if (is_magical(number))
     38 		cout << "YES" << endl;
     39 	else
     40 		cout << "NO" << endl;
     41 
     42 	return 0;
     43 }
     44 ```
     45 
     46 ## [320B - Ping-Pong (Easy Version)](/contest/320/problem/B "Codeforces Round 189 (Div. 2)")
     47 
     48 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!
     49 
     50 Here's an implementation using DFS: [3951145](/contest/320/submission/3951145 "Submission 3951145 by jishen")
     51 
     52 And here's an implementation using BFS: [3947426](/contest/320/submission/3947426 "Submission 3947426 by sister_what_hate_most")
     53 
     54 Finally an implementation using Floyd-Warshall: [3945330](/contest/320/submission/3945330 "Submission 3945330 by toi333")
     55 
     56 ## [319A - Malek Dance Club](/contest/319/problem/A "Codeforces Round 189 (Div. 1)")
     57 
     58 Solving this problem was easy when you modeled the assignment with two sets of points numbered from 0 to 2*n* - 1 (inclusive) paired with 2*n* line segments. Each line segment corresponds to a dance pair. And each pair of intersecting lines increase the complexity by one.
     59 
     60 Imagine you now the solution for binary string *x*. Now we want to calculate the answer for 1*x* and 0*x* easily. Look at the figure below:
     61 
     62 ![ ](/predownloaded/8e/65/8e658ce8d4236581d6237a9aed815b5016a9637c.png)
     63 
     64 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.
     65 
     66 So if *x* has length *n* and *f*(*x*) is the complexity of the assignment then we have:
     67 
     68 * *f*(0*x*) = 2*f*(*x*)
     69 * *f*(1*x*) = 2*f*(*x*) + 22*n*
     70 
     71 An interesting fact is that *f*(*x*) is equal to *x*2*n* - 1.
     72 
     73 ## [319B - Psychos in a Line](/contest/319/problem/B "Codeforces Round 189 (Div. 1)")
     74 
     75 Will be fixed :)
     76 
     77 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.
     78 
     79 Now let *t**i* 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 *t**i* = *max*(*t**j* + 1, ..., *t**i* - 1) + 1.
     80 
     81 Now we have a simple *O*(*n*2) 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](http://stackoverflow.com/a/9495815).
     82 
     83 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](/contest/319/submission/3945963 "Submission 3945963 by pauldb")
     84 
     85 ## [319C - Kalila and Dimna in the Logging Industry](/contest/319/problem/C "Codeforces Round 189 (Div. 1)")
     86 
     87 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 *dp**i* be the minimum cost to cut the *i*-th tree completely. It's easy to figure out that we can calculate *dp**i* if we know the index of the last tree which has been cut completely (*j*-th tree). Knowing this *dp**i* would be equal to *dp**j* + *b**j**a**i*. So *dp**i* = *min**j* = 1..*i* - 1(*dp**j* + *b**j**a**i*).
     88 
     89 Using the above information the problem has an easy dynamic programming solution in *O*(*n*2). 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](http://wcipeg.com/wiki/Convex_hull_trick).
     90 
     91 ## [319D - Have You Ever Heard About the Word?](/contest/319/problem/D "Codeforces Round 189 (Div. 1)")
     92 
     93 TODO
     94 
     95 ## [319E - Ping-Pong](/contest/319/problem/E "Codeforces Round 189 (Div. 1)")
     96 
     97 TODO