UVa 357

Its basically a variation of the famous "Coin Change" problem. The code is pretty much self-explanatory. Here it is:

#include<stdio.h>
unsigned long tab[6][30001];
int denom[]={0,1,5,10,25,50};
int main()
{
    // tab[denom][val]
    // tab[i][j] = no of ways we can pay value j using upto ith denominations
    for(int i=0;i<6;++i)
    {
        tab[i][0]=1;
    }
    for(int i=0; i<30001;++i )
    {
        tab[0][i]=0;
    }
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(tab[5][n]!=0)
        {
            if(tab[5][n]==1) printf("There is only 1 way to produce %d cents change.\n",n);
            else printf("There are %lu ways to produce %d cents change.\n",tab[5][n],n);
            continue;
        }
        bool found =false;
        for(int i=1;i<=n;++i)
        {
            if(found) break;
            for(int j=1;j<=5;++j)
            {
                if(!tab[j][i])
                {
                    if(denom[j]>i) tab[j][i]=tab[j-1][i];
                    else
                    {
                        tab[j][i]=tab[j-1][i]+tab[j][i-denom[j]];
                    }
                }
                if(j==5 && i==n)
                {
                    if(tab[5][n]==1) printf("There is only 1 way to produce %d cents change.\n",n);
                    else printf("There are %lu ways to produce %d cents change.\n",tab[5][n],n);
                    found =true;

                }
            }
        }

    }
    return 0;
}

UVa 113

Basic formula but difficult constraints. The code I wrote was the first thought that came to my mind. I use binary search to correctly guess 'k' by using 1 to 10^9 as the range. This is my only Java submission, mainly because I did not have a pre-written BigInt class in C/C++. However later on I came across a neat mathematical way of doing it though I have not coded it yet. Here it is:

k^n = p

n*log(k) = log(p)

log(k) = log(p)/n

k = exp(log(p)/n)

My code is as follows:

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.math.BigInteger;







public class Main {




public static void main(String args[]) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String str1 = "", str2 = "";

int n = 0;

BigInteger p = new BigInteger("0");

while (true) {

str1 = br.readLine();

if (str1 == null) {

break;

}

n = Integer.parseInt(str1);

str2 = br.readLine();

if (str2 == null) {

break;

}

p = new BigInteger(str2);

double lo = 0, hi = 10e9;

while (lo <= hi) {

boolean flag = false;

double mid = lo / 2 + hi / 2;

BigInteger temp = new BigInteger(Integer.toString((int) mid));

temp = temp.pow(n);

int comp = temp.compareTo(p);

switch (comp) {

case 0:

flag = true;

System.out.println((int) mid);

break;

case 1:

hi = (int) mid - 1;

break;

case -1:

lo = (int) mid + 1;

break;

}

if (flag) {

break;

}

}

}

}

}




SPOJ PROBTNPO

When I saw this problem for the first time memoization was the word that came to my mind. And as usual, I jumped into coding it without giving it much thought before it struck me that a static memo is not a very good option as the numbers might go out of bounds because off the 3*n+1 step. Then I resorted to using map, a fancy but very useful data structure. But the "Man proposes, God disposes and I slog" rule came into play and I got some runtime errors, thanks to my flamboyant coding skills ;-) . Next came a tsunami of TLEs. After sometime i got really frustrated and started typing afresh right into the "code pasting" text field. It was the most naive solution I could think of and expected a TLE. But to my surprise, there it was smiling at me, a beautiful ACC.

#include <cstdio>

#include <algorithm>

using namespace std;

int f(int i)

{

int cnt = 1;

while(i != 1) {

if(i&1) cnt+=2,i=(3*i+1)>>1;

else ++cnt,i=i>>1;

}

return cnt;

}

int main()

{

int i, j, a;

int mx;

while(scanf("%d%d", &i, &j)!=EOF) {

mx = -1;

for(a=min(i,j); a<=max(i,j); ++a)

mx = max(mx, f(a));

printf("%d %d %d\n", i, j, mx);

}

return 0;

}

SPOJ GOSSIPER

This problem fooled me into thinking that it was all about transitive closure. So the first thing I did was to use Floyd-Warshall on it which failed miserably. But then with the help of Gowtham I could figure out that a meeting does not propagate the gossip back to the previous gossiper, a fact that I had clearly ignored even when it was screaming out in the sample input. Anyways couple of WAs, TLEs and SIGSEGVs later I finally got an AC. Phew...

#include<stdio.h>

#include<string>

#include<map>

#include<iostream>

using namespace std;

char tab[2100][2100];

map<string,int> name_map;




int main() {

int n,m;

while(scanf("%d%d",&n,&m)!=EOF) {

if(n==0 && m==0) return 0;

int _n=0,x,y;

string name1,name2;

name_map.clear();

while(_n<n) {

cin>>name1;

name_map.insert(make_pair(name1,_n++));

}

while(m--) {

cin>>name1>>name2;

x=name_map.find(name1)->second;

y=name_map.find(name2)->second;

for(_n=0;_n<n;++_n) {

if(tab[x][_n] && _n!=y) tab[y][_n]=1;

if(tab[y][_n] && _n!=x) tab[x][_n]=1;

}

tab[x][y]=tab[y][x]=1;

}

int cnt=0;

for(x=0;x<n;++x) {

for(y=0;y<n;++y) {

if(tab[x][y]) {

cnt++;

tab[x][y]=0;

}




}

}

if(cnt==n*n-n) printf("YES\n");

else printf("NO\n");

}

return 0;

}




UVa 108

This is a well known problem. Also called Kadane's 2D problem, it asks to find the maximum sub matrix from a given matrix of integers. The theory is to reduce it to Kadane's 1D problem which aims at finding the maximum sub array in a given array of integers. How do we reduce, this is how:

1) First find the column sums, can be done on the fly. O(n^2)

2) Then just chose pair of rows from this table of column sums. O(n^2)

3) For each pair selected find the partial sum of each column from 1 to n

4) Run Kadane's 1D on the 1D array found above. O(n)

5) Voila sub matrix found in O(n^3)

Here it goes:

#include<stdio.h>

#include<algorithm>

using namespace std;

int tab[101][101];

int main() {

int n;

while(scanf("%d",&n)==1) {

for(int i=1;i<=n;++i) {

for(int j=1;j<=n;++j) {

scanf("%d",&tab[i][j]);

tab[i][j]+=tab[i-1][j];

}

}

int mx=tab[1][1];

for(int i=0;i<n;++i) {

for(int j=i+1;j<=n;++j) {

int temp=0;

for(int k=1;k<=n;++k) {

temp+=tab[j][k]-tab[i][k];

if(temp<0) temp=0;

mx=max(mx,temp);

}

}

}

printf("%d\n",mx);

}

return 0;

}




Posting Code Snippets on Blogger

Well after some googling I found out the following "no fuss" code snippet transformers, good for casual bloggers like me. Hope it helps you too:

1) webformatter

2) formatmysourcecode

SPOJ PRIME1

Here is another one of those problems that any wannabe programmer should solve to get initiated in the art of problem solving (trying to preach here ;)) . This code got me through, barely though.

It tends to be pretty slow, one must try segmented sieve for problems like this. But after I got an ACC I was not in a mood to dive into it again. Hopefully, someday I'll return to it and give it a second look. Till then ...

#include<cstdlib>

#include<iostream>

#include<string>

#include<fstream>

#include<cmath>

#include<cstring>

using namespace std;

#define SZ 32000




bool prime_tab[SZ];




int main(int argc, char** argv) {

int m, n, t;

prime_tab[0] = prime_tab[1] = 1;

for (int i = 2; i < SZ; i++) {

if (!prime_tab[i]) {

for (int j = 2; i * j < SZ; j++) {

prime_tab[i * j] = 1;

}

}

}







cin >> t;

while (t--) {

cin >> m >> n;







for (int i = m; i <= n; i++) {

bool pass = (i != 1);

for (int j = 2; j * j <= i; j++) {

if (!prime_tab[j]) {

if (i % j == 0) {

pass = 0;

break;

}

}




}

if (pass)

cout << i << endl;







}

cout << endl;




}

return 0;

}




SPOJ SUMITR

This was good problem for people interested in pure algorithm and tweaking. I had to spend some time (read 2 hours) to come up with something that would satisfy the 256 bytes constraint. Luckily I happen to be a friend of a gifted individual (read one whose got an ACC) who had solved this problem before. With his tips I was able to to get an ACC finally :) So here it goes

#include<iostream>

#define f(a,b,c) for(a=b;a<=c;++a)

#define _ std::

int a[100][100],t,n,i,j,x;main(){_ cin>>t;while(t--){_ cin>>n;f(i,1,n)f(j,1,i)_ cin>>a[i][j],a[i][j]=_ max(a[i-1][j],a[i-1][j-1])+a[i][j],x=_ max(x,a[i][j]);_ cout<<x<<_ endl;x=0;}}

PS- I am open to criticism, please post any improvements that you can suggest.