codechef MARCHA1 - "paying up": http://www.codechef.com/problems/MARCHA1
tutorial: http://www.codechef.com/wiki/tutorial-paying
subset sum problem explained in dp(dynamic programming): http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
rutgers university algo for subset sum problem: http://crab.rutgers.edu/~guyk/ex/part.pdf
reduction of subset-sum-optimization to subset-sum-decision(washington university): http://courses.cs.washington.edu/courses/csep521/05sp/lectures/sss.pdf
carnegie-mellon courtesy, subset-sum and knapsack explained: http://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/subsetsum.pdf
i suggest to have a look at MIT knapsack recitation: http://www.youtube.com/watch?v=wFP5VHGHFdk
subset sum(backtracking) video: http://www.youtube.com/watch?v=WRT8kmFOQTw
my c++ solution to codechef MARCHA1 - "paying up" problem: http://ideone.com/p04R4k
// A recursive solution for subset sum problem
#include <stdio.h>
#include <iostream>
using namespace std;
// Returns true if there is a subset of set[] with sun equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
//cout<<set[n]<<" "<<n<<" "<<sum<<endl; i've printed it to learn what my code is doing
// Base Cases
if (sum == 0)
return true;
if (n == 0 && sum != 0)
return false;
// If last element is greater than sum, then ignore it
if (set[n-1] > sum)
return isSubsetSum(set, n-1, sum);
/* else, check if sum can be obtained by any of the following
(a) including the last element
(b) excluding the last element */
return isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1]);
}
// Driver program to test above function
int main()
{
int set[100];
int sum;
int a, b;
//int n = sizeof(set)/sizeof(set[0]);
cin>>a;
for(int z=0; z<a; z++) {
int n;
cin>>n>>sum;
for(int k=0; k<n; k++) cin>>set[k];
if (isSubsetSum(set, n, sum) == true)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
NOTE: to be honest, i myself don't have any idea about what my code is doing. i havent understood the topic yet, so i appreciate any guiding comments. thnx
Thursday, December 12, 2013
Monday, December 9, 2013
codechef COOLING - Cooling Pies solution
problem: http://www.codechef.com/problems/COOLING/
editorial: http://discuss.codechef.com/questions/4211/cooling-editorial
my (copied) c++ solution to codechef COOLING - Cooling Pies: http://ideone.com/cQAzcX
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
// your code goes here
int a, b, i, j, weigh[35], limt[35], count;
cin>>a;
while(a--) {
cin>>b;
count=0;
for(i=0; i<b; i++) cin>>weigh[i];
for(j=0; j<b; j++) cin>>limt[j];
std::stable_sort(weigh, weigh+b);
std::stable_sort(limt, limt+b);
for(i=0, j=0; i<b && j<b; i++) {
while(j<b && weigh[i]>limt[j]) {
j++;
}
if(j<b) {
count++; j++;
}
}
cout<<count<<endl;
}
return 0;
}
NOTE: in my opinion, it would be nice if you count++ inversely. assume weight is X, and limit is Y func respectively. we have(or reach) our desired count++ when Y's element is bigger than or equal to X's particular element. and in that condition we count++. otherwise, we just pass onto Y's next element, till we meet the condition.
editorial: http://discuss.codechef.com/questions/4211/cooling-editorial
EXPLANATION
The following greedy algorithm always finds the optimum answer:
- Choose the lightest pie not yet on a rack
- If none of the remaining racks can hold this pie, stop
- Of all the racks that can hold this pie, place the pie on the rack with the smallest weight limit
- If there are no more pies, stop. Otherwise, go back to step 1
my (copied) c++ solution to codechef COOLING - Cooling Pies: http://ideone.com/cQAzcX
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
// your code goes here
int a, b, i, j, weigh[35], limt[35], count;
cin>>a;
while(a--) {
cin>>b;
count=0;
for(i=0; i<b; i++) cin>>weigh[i];
for(j=0; j<b; j++) cin>>limt[j];
std::stable_sort(weigh, weigh+b);
std::stable_sort(limt, limt+b);
for(i=0, j=0; i<b && j<b; i++) {
while(j<b && weigh[i]>limt[j]) {
j++;
}
if(j<b) {
count++; j++;
}
}
cout<<count<<endl;
}
return 0;
}
NOTE: in my opinion, it would be nice if you count++ inversely. assume weight is X, and limit is Y func respectively. we have(or reach) our desired count++ when Y's element is bigger than or equal to X's particular element. and in that condition we count++. otherwise, we just pass onto Y's next element, till we meet the condition.
codechef NUMGAME - yet another number game solution
http://www.codechef.com/problems/NUMGAME/
my c++ solution to codechef NUMGAME - yet another number game: http://ideone.com/L7cjyb
#include <iostream>
using namespace std;
int main() {
// your code goes here
int a, b;
cin>>a;
while(a--) {
cin>>b;
if(b%2) cout<<"BOB"<<endl;
else cout<<"ALICE"<<endl;
}
return 0;
}
NOTE: imho, you should focus on divisor, the least possible divisor(here 1) so that rounds take longer, and chances of player get maximized
my c++ solution to codechef NUMGAME - yet another number game: http://ideone.com/L7cjyb
#include <iostream>
using namespace std;
int main() {
// your code goes here
int a, b;
cin>>a;
while(a--) {
cin>>b;
if(b%2) cout<<"BOB"<<endl;
else cout<<"ALICE"<<endl;
}
return 0;
}
NOTE: imho, you should focus on divisor, the least possible divisor(here 1) so that rounds take longer, and chances of player get maximized
my c++ solution to codechef TLG - The Lead Game problem
codechef TLG - The Lead Game problem: http://www.codechef.com/problems/TLG/
The Lead Game
All submissions for this problem are available.
The game of billiards involves two players knocking 3 balls around
on a green baize table. Well, there is more to it, but for our
purposes this is sufficient.
on a green baize table. Well, there is more to it, but for our
purposes this is sufficient.
The game consists of several rounds and in each round both players
obtain a score, based on how well they played. Once all the rounds
have been played, the total score of each player is determined by
adding up the scores in all the rounds and the player with the higher
total score is declared the winner.
obtain a score, based on how well they played. Once all the rounds
have been played, the total score of each player is determined by
adding up the scores in all the rounds and the player with the higher
total score is declared the winner.
The Siruseri Sports Club organises an annual billiards game where
the top two players of Siruseri play against each other. The Manager
of Siruseri Sports Club decided to add his own twist to the game by
changing the rules for determining the winner. In his version, at the
end of each round the leader and her current lead are calculated. Once
all the rounds are over the player who had the maximum lead at the
end of any round in the game is declared the winner.
the top two players of Siruseri play against each other. The Manager
of Siruseri Sports Club decided to add his own twist to the game by
changing the rules for determining the winner. In his version, at the
end of each round the leader and her current lead are calculated. Once
all the rounds are over the player who had the maximum lead at the
end of any round in the game is declared the winner.
Consider the following score sheet for a game with 5 rounds:
Round Player 1 Player 2
1 140 82
2 89 134
3 90 110
4 112 106
5 88 90
The total scores of both players, the leader and the lead after
each round for this game is given below:
each round for this game is given below:
Round Player 1 Player 2 Leader Lead
1 140 82 Player 1 58
2 229 216 Player 1 13
3 319 326 Player 2 7
4 431 432 Player 2 1
5 519 522 Player 2 3
The winner of this game is Player 1 as he had the maximum lead (58
at the end of round 1) during the game.
at the end of round 1) during the game.
Your task is to help the Manager find the winner and the winning
lead. You may assume that the scores will be such that there will
always be a single winner. That is, there are no ties.
lead. You may assume that the scores will be such that there will
always be a single winner. That is, there are no ties.
Input
The first line of the input will contain a single integer N (N
≤ 10000) indicating the number of rounds in the game. Lines
2,3,...,N+1 describe the scores of the two players in the N rounds.
Line i+1 contains two integer Si and Ti, the scores of the Player 1
and 2 respectively, in round i. You may assume that 1 ≤ Si ≤
1000 and 1 ≤ Ti ≤ 1000.
≤ 10000) indicating the number of rounds in the game. Lines
2,3,...,N+1 describe the scores of the two players in the N rounds.
Line i+1 contains two integer Si and Ti, the scores of the Player 1
and 2 respectively, in round i. You may assume that 1 ≤ Si ≤
1000 and 1 ≤ Ti ≤ 1000.
Output
Your output must consist of a single line containing two integers
W and L, where W is 1 or 2 and indicates the winner and L is the
maximum lead attained by the winner.
W and L, where W is 1 or 2 and indicates the winner and L is the
maximum lead attained by the winner.
Example
Input:
5 140 82 89 134 90 110 112 106 88 90
Output:
1 58
| Author: | admin |
| Tags | admin |
| Date Added: | 28-07-2009 |
| Time Limit: | 1 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.8.1, CPP11, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
my c++ solution to codechef TLG - The Lead Game problem: http://ideone.com/yiqBAr
#include <iostream>
using namespace std;
int main() {
// your code goes here
int a, b, c, diff, max=0, winner, temp, sc_1=0, sc_2=0;
cin>>a;
while(a--) {
cin>>b>>c;
sc_1=sc_1+b;
sc_2=sc_2+c;
if(sc_1>sc_2) {
diff=sc_1-sc_2; temp=1;
}
else {
diff=sc_2-sc_1; temp=2;
}
if(diff>max) {
max=diff; winner=temp;
}
}
cout<<winner<<" "<<max;
return 0;
}
NOTE: focus on overall lead score
> Your output must consist of a single
> line containing two integers W and L,
> where W is 1 or 2 and indicates the
> winner and L is the maximum lead
> attained by the winner.
there L is maximum overall lead, but it needs to be calculated per round
NOTE: focus on overall lead score
> Your output must consist of a single
> line containing two integers W and L,
> where W is 1 or 2 and indicates the
> winner and L is the maximum lead
> attained by the winner.
there L is maximum overall lead, but it needs to be calculated per round
my c++ solution to codechef ONP - Transform the Expression
codechef ONP - Transform the Expression: http://www.codechef.com/problems/ONP/
Transform the Expression
All submissions for this problem are available.
Reverse Polish Notation (RPN) is a mathematical notation where every operator follows all of its operands. For instance, to add three and four, one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 − 4 + 5" would be written "3 4 − 5 +" first subtract 4 from 3, then add 5 to that.
Transform the algebraic expression with brackets into RPN form.
You can assume that for the test cases below only single letters will be used, brackets [] will not be used and each expression has only one RPN form (no expressions like a*b*c)
Input
The first line contains t, the number of test cases (less then 100).
Followed by t lines, containing an expression to be translated to RPN form, where the length of the expression is less then 400.
Output
The expressions in RPN form, one per line.
Example
Input: 3 (a+(b*c)) ((a+b)*(z+x)) ((a+t)*((b+(a+c))^(c+d))) Output: abc*+ ab+zx+* at+bac++cd+^*
| Author: | admin |
| Tags | admin |
| Date Added: | 1-12-2008 |
| Time Limit: | 5 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLPS, CPP 4.3.2, CPP 4.8.1, CPP11, CS2, D, ERL, FORT, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
my c++ solution to codechef ONP - Transform the Expression: http://ideone.com/eY3A2o
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int main() {
// your code goes here
int a, i;
string s;
stack <char> oper;
stack <char> extra;
cin>>a;
while(a--) {
cin>>s;
for(i=0; i<s.size(); i++) {
if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/' || s[i]=='^' || s[i]=='%') oper.push(s[i]);
else if(s[i]==')') {
cout<<oper.top();
oper.pop();
}
else if(s[i]=='(') extra.push(s[i]);
else cout<<s[i];
}
cout<<endl;
}
return 0;
}
Saturday, December 7, 2013
my c++ solution to codechef PERMUT2 - ambiguous permutations problem
codechef PERMUT2 - ambiguous permutations: http://www.codechef.com/problems/PERMUT2
Ambiguous Permutations
All submissions for this problem are available.
Some programming contest problems are really tricky: not only do they
require a different output format from what you might have expected, but
also the sample output does not show the difference. For an example,
let us look at permutations.
A permutation of the integers 1 to n is an
ordering of
these integers. So the natural way to represent a permutation is
to list the integers in this order. With n = 5, a
permutation might look like 2, 3, 4, 5, 1.
However, there is another possibility of representing a permutation:
You create a list of numbers where the i-th number is the
position of the integer i in the permutation.
Let us call this second
possibility an inverse permutation. The inverse permutation
for the sequence above is 5, 1, 2, 3, 4.
An ambiguous permutation is a permutation which cannot be
distinguished from its inverse permutation. The permutation 1, 4, 3, 2
for example is ambiguous, because its inverse permutation is the same.
To get rid of such annoying sample test cases, you have to write a
program which detects if a given permutation is ambiguous or not.
require a different output format from what you might have expected, but
also the sample output does not show the difference. For an example,
let us look at permutations.
A permutation of the integers 1 to n is an
ordering of
these integers. So the natural way to represent a permutation is
to list the integers in this order. With n = 5, a
permutation might look like 2, 3, 4, 5, 1.
However, there is another possibility of representing a permutation:
You create a list of numbers where the i-th number is the
position of the integer i in the permutation.
Let us call this second
possibility an inverse permutation. The inverse permutation
for the sequence above is 5, 1, 2, 3, 4.
An ambiguous permutation is a permutation which cannot be
distinguished from its inverse permutation. The permutation 1, 4, 3, 2
for example is ambiguous, because its inverse permutation is the same.
To get rid of such annoying sample test cases, you have to write a
program which detects if a given permutation is ambiguous or not.
Input Specification
The input contains several test cases.
The first line of each test case contains an integer n
(1 ≤ n ≤ 100000).
Then a permutation of the integers 1 to n follows
in the next line. There is exactly one space character
between consecutive integers.
You can assume that every integer between 1 and n
appears exactly once in the permutation.
The last test case is followed by a zero.
The first line of each test case contains an integer n
(1 ≤ n ≤ 100000).
Then a permutation of the integers 1 to n follows
in the next line. There is exactly one space character
between consecutive integers.
You can assume that every integer between 1 and n
appears exactly once in the permutation.
The last test case is followed by a zero.
Output Specification
For each test case output whether the permutation is ambiguous or not.
Adhere to the format shown in the sample output.
Adhere to the format shown in the sample output.
Sample Input
4 1 4 3 2 5 2 3 4 5 1 1 1 0
Sample Output
ambiguous not ambiguous ambiguous
| Author: | admin |
| Tags | admin |
| Date Added: | 1-12-2008 |
| Time Limit: | 10 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.8.1, CPP11, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
and here is my c++ solution to codechef PERMUT2 - ambiguous permutations problem: http://ideone.com/qhJAdR
#include <iostream>
using namespace std;
int main() {
int a=1, i, arr[100005], arrInv[100005], not_amb;
while(a!=0) {
cin>>a;
not_amb=0;
for(i=1; i<=a; i++) {
cin>>arr[i];
}
for(i=1; i<=a; i++) {
arrInv[arr[i]]=i;
}
for(i=1; i<=a; i++) {
if(arr[i]!=arrInv[i]) not_amb=1;
}
if(a!=0) {
if(not_amb) cout<<"not ambiguous"<<endl;
else cout<<"ambiguous"<<endl;
}
}
return 0;
}
some explanation:
1 - use 1-based array
2 - think of inverse permutation as bijection function
3 - create inverse(Y) function(permutation) of given array(X)
4 - if array(X) and its inverse(Y) is equal to each other then the function(permutation) is ambiguous
NOTE: all my ideas hold variability due to my lack of math and programming knowledge. thanx
helpful input and output:
input:
4
1 4 3 2
5
2 3 4 5 1
1
1
7
6 3 7 2 1 4 5
5
4 1 3 2 5
5
1 3 5 4 2
5
2 5 3 1 4
5
2 5 1 3 4
0
output:
ambiguous
not ambiguous
ambiguous
not ambiguous
not ambiguous
not ambiguous
not ambiguous
not ambiguous
some explanation:
1 - use 1-based array
2 - think of inverse permutation as bijection function
3 - create inverse(Y) function(permutation) of given array(X)
4 - if array(X) and its inverse(Y) is equal to each other then the function(permutation) is ambiguous
NOTE: all my ideas hold variability due to my lack of math and programming knowledge. thanx
helpful input and output:
input:
4
1 4 3 2
5
2 3 4 5 1
1
1
7
6 3 7 2 1 4 5
5
4 1 3 2 5
5
1 3 5 4 2
5
2 5 3 1 4
5
2 5 1 3 4
0
output:
ambiguous
not ambiguous
ambiguous
not ambiguous
not ambiguous
not ambiguous
not ambiguous
not ambiguous
Friday, December 6, 2013
awesome sites for programmers
sites are:
1 - here is some awesome site for programmer and programming: http://rosettacode.org/wiki/Rosetta_Code
there you can find a problem's implementation in many various languages
2 - site was established based on Donald Knuth's concept of literate programming. here it is: http://en.literateprograms.org/LiteratePrograms:Welcome
there codes are displayed in easy-to-read way
3 - the stony brook algorithm repository: http://www.cs.sunysb.edu/~algorith/
4 - dictionary of algorithms and data structures: http://xlinux.nist.gov/dads/
5 - CS portal for geeks: http://www.geeksforgeeks.org/
6 - algorithm and data structures with implementations in c++ and java: http://www.algolist.net/
7 - IBM's C/C++ documentation and its features: http://publib.boulder.ibm.com/infocenter/comphelp/v8v101/index.jsp
8 - C/C++ learning made simple: http://www.c4learn.com/
9 - http://wcipeg.com/wiki/Main_Page
10 - learn C with good explanations: http://www.cprogramming.com/
11 - video tutorials: http://www.thenewboston.org/tutorials.php
enjoy
i want to update the list with sites that would gain attention of coders:
1 - sharpen your skilss: http://sixrevisions.com/resources/10-puzzle-websites-to-sharpen-your-programming-skills/
2 - leetcode: http://leetcode.com/
3 - programming praxis: http://programmingpraxis.com/
4 - hacker earth: http://www.hackerearth.com/
5 - for hacker, hackthissite: http://www.hackthissite.org/
6 - blog of some puzzles: http://www.cseblog.com/search/label/EasyPuzzles
7 - stanford's site 01: http://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign
8 - stanford's site 02: http://www.stanford.edu/class/cs97si/
i got the above links from: http://www.quora.com/Websites/What-are-the-best-websites-a-programmer-should-visit
- Polish programming tasks: http://main.edu.pl/en/archive
- Online Encyclopedia of Integer Sequences: http://oeis.org/wiki/Welcome
- Puzzle Sequences from Online Encyclopedia of Integer Sequences: http://oeis.org/Spuzzle.html
- Some cool math: https://brilliant.org/
happy coding :)
1 - here is some awesome site for programmer and programming: http://rosettacode.org/wiki/Rosetta_Code
there you can find a problem's implementation in many various languages
2 - site was established based on Donald Knuth's concept of literate programming. here it is: http://en.literateprograms.org/LiteratePrograms:Welcome
there codes are displayed in easy-to-read way
3 - the stony brook algorithm repository: http://www.cs.sunysb.edu/~algorith/
4 - dictionary of algorithms and data structures: http://xlinux.nist.gov/dads/
5 - CS portal for geeks: http://www.geeksforgeeks.org/
6 - algorithm and data structures with implementations in c++ and java: http://www.algolist.net/
7 - IBM's C/C++ documentation and its features: http://publib.boulder.ibm.com/infocenter/comphelp/v8v101/index.jsp
8 - C/C++ learning made simple: http://www.c4learn.com/
9 - http://wcipeg.com/wiki/Main_Page
10 - learn C with good explanations: http://www.cprogramming.com/
11 - video tutorials: http://www.thenewboston.org/tutorials.php
enjoy
i want to update the list with sites that would gain attention of coders:
1 - sharpen your skilss: http://sixrevisions.com/resources/10-puzzle-websites-to-sharpen-your-programming-skills/
2 - leetcode: http://leetcode.com/
3 - programming praxis: http://programmingpraxis.com/
4 - hacker earth: http://www.hackerearth.com/
5 - for hacker, hackthissite: http://www.hackthissite.org/
6 - blog of some puzzles: http://www.cseblog.com/search/label/EasyPuzzles
7 - stanford's site 01: http://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign
8 - stanford's site 02: http://www.stanford.edu/class/cs97si/
i got the above links from: http://www.quora.com/Websites/What-are-the-best-websites-a-programmer-should-visit
- Polish programming tasks: http://main.edu.pl/en/archive
- Online Encyclopedia of Integer Sequences: http://oeis.org/wiki/Welcome
- Puzzle Sequences from Online Encyclopedia of Integer Sequences: http://oeis.org/Spuzzle.html
- Some cool math: https://brilliant.org/
happy coding :)
Subscribe to:
Posts (Atom)