thefourtheye's weblog

opinions are my own; try code/suggestions at your own risk

PuttY Style Word Selection in Xfce4-terminal

| Comments

For all those who have made themselves comfortable with PuttY software, word selection by double clicking in xfce4-terminal would be difficult to get used to.

So they can follow these steps to use PuttY style word selection.

  1. Right click anywhere inside xfce4-terminal and select Preferences

  2. Select the Advanced tab

  3. Paste the following text in the box below "Double Click" section

That's it. Enjoy PuttY style word selection on xfce4-terminal :)

MongoDB Miscellaneous

| Comments

Querying based on Date & Time
   db.[Colletion].find ({Date:ISODate('2013-04-22T00:00:00Z')})

Equivalent of Oracle's Count function
   db.[Collection].find ({'FieldName':'value').length

Find distinct values of a column, after Querying
   db.[Collection].distinct ('ColumnName', {'SearchColumnName' : 'SearchValue'})

Number of distinct values
   db.[Collection].distinct ('ColumnName').length

Sorting the returned result with pymongo

db.[Collection].find().sort (
("FieldName1", pymongo.DESCENDING),
("FieldName2", pymongo.DESCENDING),
("FieldName3", pymongo.ASCENDING),

Ubuntu Screen Custom Resolution

| Comments

Configuring the screen resolution to custom value in Ubuntu was a big headache to me. With most of the monitors I was not able to change the resolution to something of my choice, apart from what is listed in the Display settings. Then I found the following way.

First, lets see how to get to know the list of displays attached to Ubuntu

~$ xrandr
Screen 0: minimum 8 x 8, current 2881 x 1280, maximum 16384 x 16384
VGA-0 connected 1600x1280+1281+0 (normal left inverted right x axis y axis) 376mm x 301mm
1280x1024 60.0*+ 75.0
1152x864 75.0
1024x768 75.0 60.0
800x600 75.0 60.3
640x480 75.0 59.9
LVDS-0 connected (normal left inverted right x axis y axis)
1600x900 60.0 + 40.0
DP-0 connected 1280x1024+0+0 (normal left inverted right x axis y axis) 376mm x 301mm
1280x1024 60.0*+ 75.0
1152x864 75.0
1024x768 75.0 60.0
800x600 75.0 60.3
640x480 75.0 59.9
DP-1 disconnected (normal left inverted right x axis y axis)
HDMI-0 disconnected (normal left inverted right x axis y axis)
DP-2 disconnected (normal left inverted right x axis y axis)
DP-3 disconnected (normal left inverted right x axis y axis)
This is what I got on my machine. And following are the display names as per Ubuntu.
Now to set the resolution 1600x900 on VGA-0, I would execute the following

xrandr --newmode "1600x900_60.00"  118.25  1600 1696 1856 2112  900 903 908 934 -hsync +vsync
xrandr --addmode VGA-0 "1600x900_60.00"
xrandr --output VGA-0 --mode "1600x900_60.00"

First command creates a new mode with resolution 1600x900
Second command makes it available for use, with display (in this case VGA-0)
Third command selects the newly added mode as the display resolution for the specified display

We see that, the first line has lot of numbers. To come up with those numbers, there is a helper tool called cvt. It takes width and height as inputs.

~$ cvt 1600 1280
# 1600x1280 59.92 Hz (CVT 2.05M4) hsync: 79.51 kHz; pclk: 171.75 MHz
Modeline "1600x1280_60.00" 171.75 1600 1712 1880 2160 1280 1283 1290 1327 -hsync +vsync

To change this to any custom resolution, just replace Modeline in the output of cvt with xrandr --newmode. Thats it. Enjoy :)

SPOJ - ACODE - AlphaCode

| Comments

Problem Description -

Approach :

1) Initialize an Array of Size N with 0 and element 0 as 1
2) Loop through all the elements
3) If it is a valid single digit number, Copy the previous element's value to the current element (DP[i] = DP[i-1])
4) If it is a valid two digit number, Add the previous to previous element's value to the current element (DP[i] += DP[i-2])

In one line : DP[i] = DP[i-1] {if valid single digit number} + DP[i-2] {if current and previous elements make a valid two digit number}

# include <cstdio>
# include <cstring>
char Input[5001] = "";
unsigned long long DP[5001];
int main()
freopen ("Input.txt", "r", stdin);
freopen ("Scratch.txt", "w", stdout);
scanf ("%s", Input);
while (strcmp(Input, "0"))
int Len = strlen (Input), Index = 1;
memset (DP, 0, sizeof DP);
DP[0] = 1;
while (Index < Len)
int temp = 0;
temp = (Input[Index-1]-'0') * 10;
temp += (Input[Index] -'0');
if (Input[Index]-'0') DP[Index] = DP[Index-1];
if (temp <= 26 && temp > 9) DP[Index] += DP[Index-2 < 0?0:Index-2];
//printf ("%d\t%llu\n",Index, DP[Index]);
//printf ("%llu\t%s\n", DP[Len-1], Input);
printf ("%llu\n", DP[Len-1]);
scanf ("%s", Input);

Timus - 1018 - Binary Apple Tree - Dynamic Programming

| Comments

Today, I saw this interesting problem.

Timus - 1018 - Binary Apple Tree

When I started working on this, I didnt know why do we need Dynamic Programming to solve this. My idea was pretty simple.
1. While reading Inputs find the total number of apples
2. Find all the leaf Branches (I mean branches without any branches on them)
3. Get the branch with the least number of apples and remove that
4. Goto Step 2 until N - Q - 1 times. (N is the total number of enumerated points on the tree, Q is the number of branches to keep, Always there will be N - 1 branches on the binary tree. So N - Q - 1 will give the number of branches to be removed)
It was pretty straight forward to implement.
# include <cstdio>
# include <map>
# include <set>
# include <bitset>
using namespace std;
int N, Q;
unsigned long long Total = 0;
struct Branch
bool operator< (const Branch & branch) const
if (this->Apples == branch.Apples)
if (this->Start == branch.Start)
return this->End < branch.End;
return this->Start< branch.Start;
return this->Apples < branch.Apples;
Branch (int a, int b, int c){Start = a; End = b; Apples = c;}
int Start, End, Apples;
set <Branch> Edges;
bitset <101> Visited;
map <int, map <int, int> > Tree;
void FindEdges (int current, int parent)
//printf ("%d\t%d\n", current, parent);
if (Visited[current]) return;
//printf ("%d\t%d Not Visited\n", current, parent);
Visited[current] = true;
map<int, int>::iterator it = Tree[current].begin();
if (Tree[current].size() == 1)
Edges.insert (Branch (parent, current, Tree[parent][current]));
for (; it != Tree[current].end(); it++)
if (!Visited[it->first])
FindEdges (it->first, current);
int main()
//freopen ("Input.txt", "r", stdin);
//freopen ("Scratch.txt", "w", stdout);
scanf ("%d%d", &N, &Q);
Q = N - 1 - Q;
int A, B, C;
for (int i = 0; i < N - 1; i++)
scanf ("%d%d%d", &A, &B, &C);
Tree[A][B] = C;
Tree[B][A] = C;
Total += C;
for (int i = 0; i < Q; i++)
map<int, int>::iterator it1 = Tree[1].begin();
Visited[1] = true;
for (; it1 != Tree[1].end(); it1++)
FindEdges(it1->first, 1);
//printf ("Edges Size : %lu\n", Edges.size());
set<Branch>::iterator it = Edges.begin();
//printf ("%d\t%d\t%d\n", it->Start, it->End, it->Apples);
Total -= it->Apples;
Tree[it->Start].erase (it->End);
Tree[it->End].erase (it->Start);
printf ("%llu\n", Total);
However, this solution was failing so many times. Then I found the testcase for which this program was failing.
4 1
1 2 1
1 3 2
2 4 3

The above shown solution returns 1 as the result whereas the optimal result is 2. This approach is greedy approach I believe.
In the first iteration, it detects the branches
1 3 2
2 4 3
and removes the branch 1 3 2, since it has the least number of apples and in the next iteration it detects the following branch
2 4 3
since that is the only leaf branch available and it removes that, leaving us with the suboptimal solution 1.

Here is the DP solution which can really solve this problem and this got accepted by Timus.

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

int N,Q, Tree[101][101], DP[101][101];
int solve (int current, int parent, int q)
if (q <= 0) return 0;
int lindex = -1, rindex = -1;
int & result = DP[current][q];
if (result != -1) return result;
for (int i = 0; i < 101; i++)
if (Tree[current][i] != -1 && i != parent) {lindex = i; break;}
for (int i = (lindex == -1?0:lindex+1); i < 101; i++)
if (Tree[current][i] != -1 && i != parent) {rindex = i; break;}
//printf ("%d\t%d\t%d\t%d\t%d\n", current, parent, lindex, rindex, q);
if (lindex == -1 || rindex == -1) return 0;
for (int i = 0; i <= q; i++)
result = max (result, (i == q?0:Tree[current][lindex] + solve(lindex, current, q - i - 1))
+ (i == 0?0:Tree[current][rindex] + solve(rindex, current, i - 1)));
//printf ("Returning %d\n", result);
return result;
int main()
//freopen ("Input.txt", "r", stdin);
//freopen ("Scratch.txt", "w", stdout);
memset (Tree, -1, sizeof Tree);
memset (DP, -1, sizeof DP);
for (int i = 0; i < N; i++)
for (int j = 0, x, y, z; j < N; j++)
scanf ("%d%d%d", &x, &y, &z);
Tree [x][y] = z;
Tree [y][x] = z;
printf ("%d\n", solve (1, 0, Q));
return 0;
Please write to me if you want me to explain this program. We can do that over chat.