TopCoder SRM 701 SortingSubsets
TopCoder Statistics - Problem Statement
This problem is short. Note that we just need to count the count of number's positions to change. We don't care the number of moves we did. So we sort the original array, compare it to the original array. If the number at the same position is not same, we know that that number at the position was changed. So time complexity is O(N).
#include <bits/stdc++.h> using namespace std; class SortingSubsets { public: int getMinimalSize(vector<int> a) { vector<int> c(a); sort(c.begin(), c.end()); int cnt = 0; for (int i = 0; i < int(c.size()); ++i) { cnt += (c[i] == a[i] ? 0 : 1); } return cnt; } }; int main(void) { SortingSubsets a; vector<vector<int> > v(4); v[0] = { 3, 2, 1}; v[1] = {1, 2, 3, 4}; v[2] = {4, 4, 4, 3, 3, 3}; v[3] = {11, 11, 49, 7, 11, 11, 7, 7, 11, 49, 11}; for (auto vv : v) { cout << a.getMinimalSize(vv) << endl; } return 0; }
TopCoder SRM 701 SquareFreeString
TopCoder Statistics - Problem Statement
This problem is Easy. Note that write clean and easy-reading code, do not use much tricky. Because it may cause some bugs that can not be found easily. For each substring, compare the first half of the substring to the second half of the substring. Loop the substrings by length.
#include <bits/stdc++.h> using namespace std; class SquareFreeString { public: string isSquareFree(string s) { string s1 = "square-free", s2 = "not square-free"; for (int len = 2; len <= int(s.size()); len += 2) { for (int j = 0; j <= int(s.size())-len; ++j) { if (check(s.substr(j, len))) { return s2; } } } return s1; } bool check(string s) { int len = s.size() / 2; for (int i = 0; i < len; ++i) { if (s[i] != s[i+len]) return false; } return true; } }; int main(void) { SquareFreeString s; vector<string> a{ "bobo", "apple", "pen", "aydyamrbnauhftmphyrooyq", "qwertyuiopasdfghjklzxcvbnm" }; for (auto ss : a) { cout << s.isSquareFree(ss) << endl; } return 0; }
Compare two huge directories on Linux
I have a huge document directory in my Linux which I copied from my external hard drive long long ago. My hard disk is almost full on my Linux. So I want to move these files to the external to save more space for my Linux. However, I am not sure the huge directory (almost 30GB+) is the same as that in the external drive and whether I have changed some file or not.
So I write this simple bash script. It can work even if the path have spaces.
#!/bin/bash - set -o nounset # Treat unset variables as an error dir1='/home/someone/Documents/' dir2='/run/media/someone/FAT32/Documents Backup/' # We assume the sub directories in dir1 and dir2 are all the same. for i in $(ls $dir1) do com1="${dir1}$i" com2="${dir2}$i" echo "comparing $i in those two paths." diff -ur "$com1" "$com2" echo "Finish comparing $i." done echo "FINISH....!!!"
Though these two directories is about 30GB. It doesn't take very long to finish. :-)
Technocup 2017 - Elimination Round 2 C. Road to Cinema
Problem
There are N cars, each car's price is C[i] and its fuel tank capacity is V[i]. The road length is S. There are K stations on the road. We must pass the road in T minutes.
- Fuel is free.
- Car can drive in two mode: (1) cover 1 kilometer in 2 minutes, and consumes 1 liter of fuel. (2) covers 1 kilometer in 1 minutes, but consumes 2 liters of fuel.
Find the lowest price car to pass the road.
Solution
For each car, we can use O(N) algorithm to check whether it can get the destination in T minutes. Here is the greedy idea:
Let the distance of two stations is LEN.
- If the car's fuel capacity is more than 2 * LEN then it can pass the road between these two stations in LEN minutes. (which is minimum)
- Otherwise, let X is the distance the car runs in first mode. let Y is the distance the car runs in second mode. Then we have: X + Y = LEN; X + 2 * Y = V[i]. Note V[i] must be more than LEN otherwise it can not pass. Then the time it uses is: 2 * X + Y = 3 * LEN - V[i].
If we loop each to check whether it can pass and maintain the lowest price. The algorithm is O(N2) which is about 1010. We notice that if V[i] can pass the road, then V[j] > V[i] can also pass. So we can sort the cars by the fuel tank capacity. And we can use binary search to search the car with the smallest fuel tank capacity which can pass the road. Let that car's index is INDICE. Then for each car in [INDICE..N-1] we can get the lowest price. In this way, we get O(NLogN) + O(N).
This is Perl solution. It got TLE on the 9th test case, maybe because of slow Input and Output. Nobody Got AC in Python either. :-(
#!perl #use strict; #use warnings; use v5.20; use Class::Struct; struct (Car => [c => '$', v => '$']); my ($n, $k, $s, $t); my @interval; while (<>) { ($n, $k, $s, $t) = split; my ($c, $v, $i, $j, @cars); for $i ( 0..$n-1 ) { ($c, $v) = split ' ', <>; $cars[$i] = Car->new(c => $c, v => $v); } @cars = sort { $a->v <=> $b->v } @cars; my @kk = split ' ', <>; unshift @kk, 0; @kk = sort { $a <=> $b } @kk; for $i ( 1..$#kk ) { $interval[$i-1] = $kk[$i] - $kk[$i-1]; } push @interval, $s - $kk[-1]; my $result = -1; my ($left, $right, $mid); $left = -1; $right = $#cars; while ($right - $left > 1) { $mid = int($left + ($right - $left) / 2); if (check($cars[$mid])) { $right = $mid; } else { $left = $mid; } } if (check($cars[$right])) { my @true_cars = @cars[$right..$#cars]; @true_cars = sort { $a->c <=> $b->c } @true_cars; say $true_cars[0]->c; } else { say -1; } } sub check { my $ref = shift; my ($i, $j); $i = $ref->v; my $t1 = 0; for $j ( @interval ) { if ($j * 2 <= $i) { $t1 += $j; } else { if ($j <= $i) { $t1 += 3 * $j - $i; } else { $t1 = $t + 10; } # make it larger to break loop } last if ($t1 > $t); } return $t1 <= $t ? 1 : 0; }
This is C++ solution. Got AC.
// // main.cpp // C. Road to Cinema // // Created by liu on 16/11/22. // Copyright © 2016年 liu. All rights reserved. // #include <iostream> #include <algorithm> #include <vector> using namespace std; struct Car { int c, v; }; int n, k, s, t; const int N = 2 * 100000 + 10; int kk[N], interval[N]; Car cars[N]; bool comp (Car &a, Car &b) { return a.v < b.v; } bool check (Car &a) { int v = a.v, t1 = 0; for (int j = 0; j <= k; ++j) { if (interval[j] * 2 <= v) t1 += interval[j]; else { if (interval[j] <= v) t1 += 3 * interval[j] - v; else t1 = t + 10; // make it larger to break loop. } if (t1 > t) break; } return t1 > t ? false : true; } int main(int argc, const char * argv[]) { while (~scanf("%d%d%d%d", &n, &k, &s, &t)) { int c, v; for (int i = 0; i < n; ++i) { scanf("%d%d", &c, &v); cars[i].c = c; cars[i].v = v; } kk[0] = 0; for (int i = 1; i <= k; ++i){ scanf("%d", &kk[i]); interval[i-1] = kk[i] - kk[i-1]; } sort(kk, kk + k + 1); for (int i = 1; i <= k; ++i){ interval[i-1] = kk[i] - kk[i-1]; } interval[k] = s - kk[k]; sort(cars, cars + n, comp); int left = -1, right = n - 1, mid; while (right - left > 1) { mid = left + (right - left) / 2; if (check(cars[mid])) right = mid; else left = mid; } // printf("interval: "); // for (int i = 0; i <= k; ++i) printf("%d ", interval[i]); // printf("\nright = %d\n", right); // for (int i = 0; i < n; ++i) { // printf("(%d %d)\n", cars[i].c, cars[i].v); // } // printf("------\n"); if (check(cars[right])) { int result = INT_MAX; for (int i = right; i < n; ++i) { result = min(result, cars[i].c); } printf("%d\n", result); } else printf("-1\n"); } return 0; }
Today is my birthday
Today(11/21) is my 24's birthday. It's snowy. Nothing special happens and everything is as usual.
Linux Mint 18
Today I install Plasma to the Linux Mint 18, because I chose the Xfce version when I installed Linux Mint 18. This is what I do:
sudo add-apt-repository ppa:kubuntu-ppa/backports sudo apt-get update && sudo apt-get dist-upgrade sudo apt-get install kubuntu-desktop
It takes a little long. Depends on network speed. For more information: www.tecmint.com
openSUSE Leap 42.2
In the morning I find that openSUSE release Leap 42.2. It's time to upgrade my openSUSE Leap 42.1 to 42.2. I choose a much simpler method: offline upgrade. Please refer to: SDB:Offline upgrade - openSUSE. Use KTorrent in Plasma to download the system image. It's much faster than that in Explore.
Note that DON'T connect to network when upgrading or it will take too long to finish. I tried at first with network and find that the system needs about 17GB+ packages to install or upgrade. And it stuck at 14% for some reason which I don't know. So I started again from start without network. It's much better, only 7GB+ of packages to upgrade or install. However it still takes much longer than a fresh install.
After it finished. Reboot. Remember to run this to update:
sudo zypper up sudo zypper patch
One my computer, it took so long to finish. About 2GB packages to update. Download time is not very long, but installing time is so slow especially installing font package and texlive packages.
This is the new system screenshot:
Beautiful and elegant. ;-)
Technocup 2017 - Elimination Round 2 D. Sea Battle
Problem:
There are N grid on a row, there are A ships, each ship's length is B. Let an int array Array[N] represents the grids. Array[i] == 0 or Array[i] == 1. Ships can only be placed on 0's. Guess some positions that there are at least one grid you guess is occupied by one ship.
Solution:
Method 1:
At first, this problem is complicated by myself at first:
- split the array into some intervals which can be placed ship.
- sort the intervals by their length.
- loop from the shortest interval to longest interval, until you are sure that you are sure that you hit at least a ship.
This is solution one. This is a bit stupid, and its implementation is a little complicated. :-(
Method 2:
We can think solve this problem in the opposite way. First, we place A - 1 ships in the intervals we encountered. Then we know that we must make it impossible to place any ship in remaining intervals.
It's easier than the first solution. And implementation is much simpler. ;-)
Perl Source Code:
All of these two Perl solutions can be accepted.
Codeforces Round #165 (Div. 1) B. Greenhouse Effect
- Because Xi < Xi+1, for i in [1, N). The plants are given in order "from left to the right". So all of Xi values are not important in this problem. We can discard them.
- Now the problem is:
Given N numbers S[N]. Given a number M <= N. 1 <= S[i] <= N. Please divide the array into M sections numbered from 1 to M from left to right with i-th section contains all of the number i. Find the minimum number of numbers you need to reorder. Note that you can insert any number of numbers between two numbers without changing the two number's position.
Let me assume the result numbers are R[N]. Let's compare array R[N] and S[N]. We know that we can insert any number of numbers between any two numbers. So we can find the longest common subsequence of R[N] and S[N] are the numbers which remain their position. Besides, R[i] <= R[i+1], for i in [1,N). So the longest common subsequence is non-decreasing. So we can find the longest non-decreasing subsequence size of S[N]. We assume the sequence is L[K], K <= N. In other words, all of the numbers in L[K] remains their position in R[N]. So the minimum numbers we need to change their positions is N - K.
So key problem is to find the longest non-decreasing subsequence size of S[N].
The easiest algorithm is in O(N^2). However it got TLE in Perl.
So we need to use a more efficient algorithm. There is a O(N*logN) solution. We know there is O(NlogN) algorithm for the getting the size of longest increasing subsequence. We can change it a little bit to get the O(NlogN) algorithm for the non-decreasing version. Perl code is below:
About the solution to the O(NlogN) algorithm to get the size of longest increasing subsequence, see the link below.
Read more