Thursday, June 28, 2012

[UVa] 11456 - Trainsorting


Method:
The problem at first glance seems too straightforward but it's not that much. Think a bit about the lines "Erin can add it to the beginning or end of her train, or refuse to add it at all. The resulting train should be as long as possible, but the cars within it must be ordered by weight.". What I understand from these lines is.

1. Erin can choose to start making the train from any point of the arrivals of the cars. So she may have started to make the train from either 1st or n-1st or nth or n/2nd, any point.
2. And from the point in time where she starts this, she checks if the new car is smaller in weight than the last car of her train or higher in weight than the first car or vice versa.
3. So the sorting can start from any point and the optimal choice is at any point.
Ofcourse you have to use LIS, but you also need LDS. Why??

Because suppose she starts from position i. Since she wants to make the train as long as possible so she must make sure the train is optimal from the last till i. Then after i she wants to join the longest possible train using the cars i+1 to n. So, she wants to join the LIS(1 -> i) with LDS(i+1 -> n).

In my solution, I subtracted 1 from LIS(i)+LDS(i) because in both the i car is present. So erased it from 1 of them.
// BISMILLAHIRRAHMANIRRAHIM

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <vector>
#include <list>
#include <iostream>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <stack>

#define swp(type, a, b) {type x=a; a=b; b=x;}

typedef long long lint;
typedef unsigned long long ulint;

using namespace std;

int seq[10000];
int lis[10000], lds[10000];

int LIS(int n) {
 
 int i, j, mx=0;
 
 
 for (i=n-1 ; i>=0 ; i--) {
  lis[i] = 1;
  for (j=i+1 ; j<n ; j++) {
   if (seq[i]<seq[j]) {
    lis[i] = max(lis[i] , 1+lis[j]);
   }
  }
  mx = max(mx, lis[i]);
 }
 return mx;
}

int LDS(int n) {
 
 int i, j, mx=0;
 
 
 for (i=n-1 ; i>=0 ; i--) {
  lds[i] = 1;
  for (j=i+1 ; j<n ; j++) {
   if (seq[i]>seq[j]) {
    lds[i] = max(lds[i] , 1+lds[j]);
   }
  }
  mx = max(mx, lds[i]);
 }
 return mx;
}



int main ( void ) {
 
 int i, kount, kase, n, x, mx, mnn, mxx, len, res;
 
 
 
 cin >> kase;
 
 while (kase--) {
  cin >> n;
  mx = n;
  
  len = 0;
  kount = 0;
  while (mx--) {
   cin >> x;
   seq[kount++] = x;
  }
  
  LDS(n); LIS(n);
  
  res = 0;
  
  for (i=0 ; i<n ; i++) {
   res = max(res, lis[i]+lds[i]-1);
  }
  
  
  /*cout << "{ debug-start" << endl;
  for (i=0 ; i<n ; i++) {
   cout << seq[i] << " ";
  } cout << endl;
  for (i=0 ; i<n ; i++) {
   cout << lis[i] << " ";
  } cout << endl;
  for (i=0 ; i<n ; i++) {
   cout << lds[i] << " ";
  } cout << endl;
  cout << "end-debug }" << endl;*/
  
  cout << res << endl;
 }
 
 return 0;
}

Sunday, June 24, 2012

Installing uTorrent in Linux


One of the biggest frustrations when downloading torrents in a Linux environment is the crappy Transmission UI. I'm an old uTorrent user. So I always feel like somehow I'm not getting the exact same performance using Transmission. But installing uTorrent is a mess sometimes specially in Fedora and Mint. Here's a really great guide which, however is a bit BIG but works.
[ http://blog.kxr.me/2011/12/utorrent-server-on-linux-step-by-step.html ]
Update:
Note: If you are not a Fedora user, do not do the symbolic linking (soft link) from the tutorial

In case you face the problem that uTorrent wants libssl 0.9.8 just follow this

  1. Open terminal in su mode or use sudo
  2. Type apt-get install libssl0.9.8
Source: HowToOpensource

[UVa] 11296 - Counting Solutions


Method:
First design a bruteforce solution with small input in mind. It should be able to compute answers for 100 101 etc. Now sequentially examine all the answers you'll find a pattern. The solution to every i-th even number is the sum of all numbers till i+1. It also applies to all odd numbers. Such as 2, 1st even number, so result is 1+2, till 2nd number And for 3, 1st odd number, it's the same. Just find the i using i = (n/2) and use i*(i+1)/2 formula for the result.
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <vector>
#include <list>
#include <iostream>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

typedef long long lint;

lint res[1000010];

int main ( void ) {
 
 lint i, j, k, n, cnt, ser;
 res[0] = 1LL;
 res[1] = 1LL;
  
 for (i=2, ser=2LL ; i<=1000001LL ; i+=2, ser++) {
  res[i] = (res[i-1]+ser);
  res[i+1] = res[i];
 }
 
 
 while ( cin >> n ) {
  cout << res[n] << endl;
 }

 return 0;
}

Friday, June 15, 2012

Backtracking Basic Code


This is one of the first things you do when you learn how to program a backtracking simulation. Generate all permutations of a given number range. When the program is at halt enter any number greater than 0 to see all numbers in that range permuted. The program terminates with the 0 input.
#include <cstdio>
#include <iostream>
using namespace std;

int src[100], out[100], used[100], n;

void btrack( int k ) {
 
 if (k>=n) {
  for (int i=0 ; i<n ; i++) {
   printf(" %d ",out[i]);
  }
  printf("\n");
  return;
 }
 
 for (int i=0 ; i<n ; i++) {
  if (!used[i]) {
   used[i] = 1;
   out[k] = src[i];
   btrack( k+1 );
   used[i] = 0;
  }
 }
 return;
}


int main ( void ) {
 
 while ( scanf("%d",&n) && n ) {
  for (int i=0 ; i<n ; i++) {
   used[i] = 0;
   src[i] = i+1;
  }
  btrack( 0 );
 }
 
 return 0;
}

Thursday, June 14, 2012

[UVa] 437 - The Tower of Babylon


Method: LIS (Modified)
You can only see the problem as an LIS Problem but you cannot solve it using LIS principles. All the six sides of the blocks have to be considered. If you test them using the rotational if in the LIS algorithm, they are just testing one or two but all the sides. So you have to make the list with six sides. -Thanks to Rakib (My team mate for contests) for pointing this out :) Code:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

typedef int lint;

using namespace std;

typedef struct blk {
 int x, y, z; 
} block;


bool comp( block a, block b ) {
 if (a.x != b.x) return (a.x<b.x);
 else if (a.y!=b.y) return (a.y<b.y); 
 else return (a.z<b.z);
}

vector<block> lst;
int lis[1000];

int LIS( int n ) {

 int max_lis(-1), i, j, k;
 
 for (int i=0 ; i<n ; i++) {
  lis[i] = lst[i].z;
  for (int j=0 ; j<i ; j++) {
   if (( (lst[i].x > lst[j].x && lst[i].y > lst[j].y) || (lst[i].x > lst[j].y && lst[i].y > lst[j].x) ) ) {
    lis[i] = max ( lis[i] , lis[j]+lst[i].z );
   }
  }
  max_lis = max ( lis[i] , max_lis );
 }
 return max_lis;
}

int main( void ) {

 int n, i, x, y, z, kase=1;

 while ( scanf("%d",&n) && n ) {
 
  lst.clear();
 
  for (i=0 ; i<n ; i++) {
   scanf("%d %d %d",&x,&y,&z);
   
   lst.push_back( (block) {x,y,z} );
   lst.push_back( (block) {x,z,y} );
   lst.push_back( (block) {y,x,z} );
   lst.push_back( (block) {y,z,x} );
   lst.push_back( (block) {z,x,y} );
   lst.push_back( (block) {z,y,x} );
  }
  
  sort(lst.begin(), lst.end(), comp);
  
  int res = LIS( lst.size() );
  
  printf("Case %d: maximum height = %d\n",kase++,res);
 } 
 return 0;
}

Saturday, June 02, 2012

[LFS] Hackathon 001 - A hacker's day out



I attended in Bangladesh's first ever Hackathon on Linux From Scratch today. A whole night inter city travel and we were at the very first phenomenal arrangement of Hacking Linux. Some of the craziest Linux enthusiasts met up at Ankur ICT Development there. Our favorite MAK Bhai (Mahey Alam Khan), Shihan Bhai and new Hacker Robin Mehdee and a bunch of other awesome Linux enthusiasts including my friends Saadi and Ri Ne.

Although we had planned for a whole LFS completion throughout the day, we ultimately ended up only compiling the Linux kernel. Today what we really gained from the meet up are:

1. Ideas about conducting a successful Hackathon (on LFS)
2. Suggestions about what to do on the next Hackathon
3. Ultimate goal of the LFS Hacking project
4. Gained insights on the Linux building method
5. Some great ideas about projects (using LFS) other than building a distro. Some of them are
  • Building lightweight OS for POS (Point of sales) systems
  • An OS for ATM Booths that doesn't use the extra payload of Windows XP, built entirely from LFS project
  • A Library system built on LFS


Shihan bhai talked about taking over the IT sector by pure enthusiastic and passionate IT lovers from unethical administrators. MAK bhai pointed out how robustly developed system can change the outlook of people towards the underrated IT sector of Bangladesh. We also heard some great stories on Hackathons outside the country where people actually focus on the fun of gossiping about geeky and on the spot hacks rather than waste useless time on formalities of events. We all agreed upon how Hackathons should be like. Hackathons should be like a breeding ground of new ideas, hacks, productive usage of the topics under consideration rather than going round and round on the formalities of the events.

We compiled a Linux Kernel from source and talked about problems experienced during compilation. During compilation various issues such as toolchain problems, cyclic execution of the compilation process etc might take place.

Shihan bhai also showed us why the Kernel is actually called the heart of OS. He explained in depth about booting, master boot records, execution of instructions by the OS etc.

The commands used during the compilation of the kernel are: 

Install qemu
  sudo apt-get install qemu
Install Busybox
  sudo apt-get install busybox
Install Clibs: glibs, ulibc
  sudo apt-get install linux-libc-dev libucommon3
Check CPU
  cat /proc/cpuinfo
Download & extract kernel to /usr/src/
  uname -r
Move to linux kernel folder
  sudo nano Makefile
Change EXTRAVERSION to ‘uname -r’ value
  sudo make mrproper
  sudo make mproper
  sudo make oldconfig
  sudo cp /boot/config-3.2.0-23-generic-pae .config
  sudo make prepare
  sudo make allnoconfig
  sudo make menuconfig
  sudo make

Connect Rapoo MT750S with Linux (Tested on Manjaro)

 I bought this obvious copy of MX Master 2S in hopes of having the device switching functionality along with a lightweight body because I ha...