Archive | Articles RSS feed for this section

24 September 2011 Comments Off

Power up C++ with the Standard Template Library: Part I

By DmitryKorolev

(collected from Topcoder)

Containers
Before we begin
Vector
Pairs
Iterators
Compiling STL Programs
Data manipulation in Vector
String
Set
Map
Notice on Map and Set
More on algorithms
String Streams
Summary

Perhaps you are already using C++ as your main programming language to solve TopCoder problems. This means that you have already used STL in a simple way, because arrays and strings are passed to your function as STL objects. You may have noticed, though, that many coders manage to write their code much more quickly and concisely than you.

Or perhaps you are not a C++ programmer, but want to become one because of the great functionality of this language and its libraries (and, maybe, because of the very short solutions you’ve read in TopCoder practice rooms and competitions).

Regardless of where you’re coming from, this article can help. In it, we will review some of the powerful features of the Standard Template Library (STL) – a great tool that, sometimes, can save you a lot of time in an algorithm competition.

The simplest way to get familiar with STL is to begin from its containers.

Containers
Any time you need to operate with many elements you require some kind of container. In native C (not C++) there was only one type of container: the array.

The problem is not that arrays are limited (though, for example, it’s impossible to determine the size of array at runtime). Instead, the main problem is that many problems require a container with greater functionality.

For example, we may need one or more of the following operations:

  • Add some string to a container.
  • Remove a string from a container.
  • Determine whether a string is present in the container.
  • Return a number of distinct elements in a container.
  • Iterate through a container and get a list of added strings in some order.

Of course, one can implement this functionality in an ordinal array. But the trivial implementation would be very inefficient. You can create the tree- of hash- structure to solve it in a faster way, but think a bit: does the implementation of such a container depend on elements we are going to store? Do we have to re-implement the module to make it functional, for example, for points on a plane but not strings?

If not, we can develop the interface for such a container once, and then use everywhere for data of any type. That, in short, is the idea of STL containers.

Before we begin
When the program is using STL, it should #include the appropriate standard headers. For most containers the title of standard header matches the name of the container, and no extension is required. For example, if you are going to use stack, just add the following line at the beginning of your program:

#include <stack>

Container types (and algorithms, functors and all STL as well) are defined not in global namespace, but in special namespace called “std.” Add the following line after your includes and before the code begin:

using namespace std;

Another important thing to remember is that the type of a container is the template parameter. Template parameters are specified with the ‘<’/’>’ “brackets” in code. For example:

vector<int> N;

When making nested constructions, make sure that the “brackets” are not directly following one another – leave a blank between them.

vector< vector<int> > CorrectDefinition;
vector<vector<int>> WrongDefinition; // Wrong: compiler may be confused by 'operator >>'

Vector
The simplest STL container is vector. Vector is just an array with extended functionality. By the way, vector is the only container that is backward-compatible to native C code – this means that vector actually IS the array, but with some additional features.

 vector<int> v(10);
 for(int i = 0; i < 10; i++) {
      v[i] = (i+1)*(i+1);
 }
 for(int i = 9; i > 0; i--) {
      v[i] -= v[i-1];
 }

[...]

Tags: , ,
5 August 2011 Comments Off

No More Free Books….

Due to copyright issue, ACMsolver website will offer no more free books for download. Thanks for understanding. Anyway, next edition of Art of Programming Contest (fully revised) is planned to release after 2014. Till then..

9 July 2011 Comments Off

Some ACM-ICPC Problems & Solutions (ACM-ICPC: 2011 in Fukuoka)

Problems here: http://icpc2011.ait.kyushu-u.ac.jp/icpc2011/contest/all_en.html

Solution (s) by Tatuyan:

Problem-A: I did not have a hard time so much because this problem looks like my self-made problem. When we made the problem, I checked all number with for-loop. This time, I prepare prime table with using Eratosthenes’s sifter.
Problem-B: There is Kind Problem at UTPC2011(University of Tokyo Programming Contest 2011). I solved with making stack.
Problem-C: I solved this problem with back track. In Japan domestic contest, We usually see problem which require counting cells,do we?
Problems are here.

C Source.

A.Chebyshev’s Theorem.
#include<stdio.h>
#include<stdlib.h>
#define NUM 123456
unsigned int list[NUM];
void makelist(void);
int main(void){
unsigned int i,j,n,ans;
makelist();
while(scanf("%u",&n) && n){
ans=0;
if(n==1){
puts("1");
continue;
}else if(n==2){
puts("1");
continue;
}
for(i=((n+1)>>1);i<n;i++) if(list[i]!=0) ans++;
printf("%u\n",ans);
}
return 0;
}
void makelist(void){
unsigned int i,j;
for(i=0;i<NUM;i++) list[i]=(i<<1)+1;
for(i=1;i*i<NUM;i++){
if(list[i]==0) continue;
for(j=(i*(i+1))<<1;j<NUM;j+=(i<<1)+1) list[j]=0;
}
}

B. The Balance of the World

#include<stdio.h>
#include<string.h>
#define NUM 100
int main(void){
int brac[NUM+1],now,i,flg;
char str[NUM+2];
while(fgets(str,sizeof(str),stdin) && strcmp(str,".\n")){
memset(brac,0,sizeof(brac));
flg=0;
now=0;
for(i=0;i<strlen(str)-1;i++){
if(str[i]=='('){
brac[now]=1;
now++;
}else if(str[i]=='['){
brac[now]=2;
now++;
}else if(str[i]==')'){
if(now==0 || brac[now-1]!=1){
flg=1;
break;
}
now--;
}else if(str[i]==']'){
if(now==0 || brac[now-1]!=2){
flg=1;
break;
}
now--;
}
}
if(now!=0) flg=1;
if(flg==0) puts("yes");
else puts("no");
}
return 0;
}

C.Identically Colored Panels Connection

#include<stdio.h>
#include<stdlib.h>
typedef struct{
int col;
int check;
} panels;
int max,h,w,c,num;
void getmax(panels **panel,int color,int nest,int n);
void change(panels **panel,int color,int i,int j);
void countnum(panels **panel,int i,int j);
int main(void){
panels **panel;
int i,j,colors;
while(scanf("%d %d %d",&h,&w,&c) && h && w && c){
panel=(panels **)calloc(h,sizeof(panels *));
for(i=0;i<h;i++) *(panel+i)=(panels *)calloc(w,sizeof(panels *));
for(i=0;i<h;i++){
for(j=0;j<w;j++){
scanf("%d",&colors);
(*(panel+i)+j)->col=colors;
(*(panel+i)+j)->check=0;
}
}
max=0;
for(i=0;i<6;i++) getmax(panel,i+1,0,0);
printf("%d\n",max);
for(i=0;i<h;i++) free(*(panel+i));
free(panel);
}
return 0;
}
void getmax(panels **panel,int color,int nest,int n){
panels **tmp;
int i,j,k;
if(nest==4 && color!=c) return;
tmp=(panels **)calloc(h,sizeof(panels *));
for(i=0;i<h;i++) *(tmp+i)=(panels *)calloc(w,sizeof(panels *));
for(i=0;i<h;i++){
for(j=0;j<w;j++){
(*(tmp+i)+j)->col=(*(panel+i)+j)->col;
(*(tmp+i)+j)->check=0;
}
}
change(tmp,color,0,0);
num=0;
countnum(tmp,0,0);
if(max<num) max=num;
if(nest==4 || num==n){
for(i=0;i<h;i++) free(*(tmp+i));
free(tmp);
return;
}
for(i=0;i<6;i++) getmax(tmp,i+1,nest+1,1);
for(i=0;i<h;i++) free(*(tmp+i));
free(tmp);
}
void change(panels **panel,int color,int i,int j){
(*(panel+i)+j)->check=1;
if(i>0 && (*(panel+i)+j)->col==(*(panel+i-1)+j)->col && (*(panel+i-1)+j)->check==0) change(panel,color,i-1,j);
if(i<h-1 && (*(panel+i)+j)->col==(*(panel+i+1)+j)->col && (*(panel+i+1)+j)->check==0) change(panel,color,i+1,j);
if(j>0 && (*(panel+i)+j)->col==(*(panel+i)+j-1)->col && (*(panel+i)+j-1)->check==0) change(panel,color,i,j-1);
if(j<w-1 && (*(panel+i)+j)->col==(*(panel+i)+j+1)->col && (*(panel+i)+j+1)->check==0) change(panel,color,i,j+1);
(*(panel+i)+j)->col=color;
}
void countnum(panels **panel,int i,int j){
(*(panel+i)+j)->check=2;
if(i>0 && (*(panel+i)+j)->col==(*(panel+i-1)+j)->col && (*(panel+i-1)+j)->check!=2) countnum(panel,i-1,j);
if(i<h-1 && (*(panel+i)+j)->col==(*(panel+i+1)+j)->col && (*(panel+i+1)+j)->check!=2) countnum(panel,i+1,j);
if(j>0 && (*(panel+i)+j)->col==(*(panel+i)+j-1)->col && (*(panel+i)+j-1)->check!=2) countnum(panel,i,j-1);
if(j<w-1 && (*(panel+i)+j)->col==(*(panel+i)+j+1)->col && (*(panel+i)+j+1)->check!=2) countnum(panel,i,j+1);
num++;
}
19 June 2011 Comments Off

Let’s Learn Programming (Sticky Post-updated daily)

Let’s Learn Programming (Sticky Post-updated daily)

Let’s create an alternative approach in computer programming learning.. here I plan to create a comic series using the characters from Futurama, my favorite TV series. Let me know what you think of this approach- Arefin

previous episodes..? click below

[...]

Tags:
30 May 2011 Comments Off

The 2011 World Finals Ranklist – ACM International Collegiate Programming Contest

The 2011  World Finals Ranklist – ACM International Collegiate Programming Contest. See live cast:

http://scrool.se/icpc/wf2011/

http://www.icpclive.com/?page=live333#

photo by Bettina Johnson

John Bonomo, ICPC World Finals chief judge, has been part of the judging team since the 2002 Honolulu competition. “Our main purpose is to handle any slight problems with the test data, look at problems that contestant teams continually get wrong, and for clarification,” he said. Bonomo explained how the judging process has become increasingly automated with the advancement of technology. “We used to look through code and run testing,” he said. “Now the satisfaction comes from crafting challenging sets of problems.”

According to ICPC director of judges Jo Perry, there is one judge per problem in the World Finals. The chief judge and director of judges are used as extra hands during the finals and are also responsible for putting the problem sets together for the competition. Perry became involved with the judging side of the competition after being asked by a colleague at North Carolina State University to submit problems to a then infant ICPC competition.

Some of the judging staff became involved with judging simply for their love of the ICPC. Originally born in Sweden and now living in Canada, Per Austrin became involved with the competition as a contestant for his Swedish university. He joined the judging team when he could no longer compete due to age and has been a regular World Finals judge since 2008. “I enjoy the contest,” he said. “The construction of problems is almost like the other side of solving them.”

Former Google programmer Derek Kisman got his start with the World Finals as a contestant for The University of Waterloo during the Prague competition. He said, “I love the ICPC and being behind the scenes now as a judge.” Kisman enjoys coming up with problems that spawn interesting discussions and plans to continue judging for the ICPC as long as possible.

While many on the judging team have always known the international programming competition under the familiar ICPC name, Stan Wileman remembers the forerunner to the official contest we know today. While attending the University of Houston as a graduate student, Wileman and his early team of programmers learned of a contest at Texas A&M. “We overslept the day of the completion and arrived at the tail-end,” Wileman said. “We were late but still managed to win the damn thing and split the $100 grand prize!”

Today, Wileman has earned two hats with the ICPC as a World Finals judge and the regional director of North Central North American region. Bettina Johnson, ICPC Digital

Live Ranklist

http://scrool.se/icpc/wf2011/

21 May 2011 Comments Off

ACM UVa Problems Category

New Comer

★ 100 The 3n + 1 problem
★ 10189 Minesweeper
★ 10137 The Trip
★ 706 LCD Display
★ 10267 Graphical Editor
★★ 10033 Interpreter
★ 10196 Check The Check
★ 10142 Australian Voting

Data Structure

★ 10038 Jolly Jumpers
★★ 10315 Poker Hands
★★ 10050 Hartals
★★   843 Crypt Kicker
★ 10205 Stack ‘em Up
★★ 10044 Erdos Numbers
★ 10258 Contest Scoreboard
★★★ 10149 Yahtzee

String

★ 10082 WERTYU
★★ 10010 Where’s Waldorf?
★ 10252 Common Permutation
★★ 850 Crypt Kicker II
★ 10188 Automated Judge Script
★★ 10132 File Fragmentation
★★★ 10150 Doublets
★★ 848 Fmt

Sorting

★ 10041 Vito’s Family
★★   120 Stacks of Flapjacks
★★★ 10037 Bridge
★ 10191 Longest Nap
★★ 10026 Shoemaker’s Problem
★★ 10138 CDVII
★★ 10152 ShellSort
★ 10194 Football (aka Soccer)

Arithmetic and Algerba

★ 10035 Primary Arithmetic
★ 10018 Reverse and Add
★   701 The Archeologists’ Dilemma
★★ 10127 Ones
★★★   847 A Multiplication Game
★ 10105 Polynomial Coefficients
★ 10077 The Stern-Brocot Number System
★★★★ 10202 Pairsumonious Numbers

Combinations

★ 10183 How Many Fibs?
★★ 10213 How Many Pieces of Land ?
★★ 10198 Counting
★★ 10157 Expressions
★★ 10247 Complete Tree Labeling
★★ 10254 The Priest Mathematician
★★ 10049 Self-describing Sequence
★★   846 Steps

Number Theory

★ 10110 Light, More Light
★★ 10006 Carmichael Numbers
★ 10104 Euclid Problem
★★ 10139 Factovisors
★★ 10168 Summation of Four Primes
★ 10042 Smith Numbers
★ 10090 Marbles
★★ 10089 Repackaging

Backtracking

★★ 861 Little Bishops
★★★ 10181 15-Puzzle Problem
★★ 10128 Queue
★★ 10160 Servicing Stations
★★ 10032 Tug of War
★★ 10001 Garden of Eden
★★★ 704 Colour Hash
★★★ 10270 Bigger Square Please…

Graph Traversal

★ 10004 Bicoloring
★★ 10067 Playing with Wheels
★★★ 10099 The Tourist Guide
★★   705 Slash Maze
★★★ 10029 Edit Step Ladders
★★★ 10051 Tower of Cubes
★★★ 10187 From Dusk Till Dawn
★★★ 10276 Hanoi Tower Troubles Again!

Graph Algorithm

★★ 10034 Freckles
★★★ 10054 The Necklace
★★ 10278 Fire Station
★★★ 10039 Railroads
★★★ 10158 War
★★★ 10199 Tourist Guide
★★★★ 10249 The Grand Dinner
★★★ 10092 The Problem with the Problem Setter

Dynamic Programming

★★ 10131 Is Bigger Smarter?
★★★ 10069 Distinct Subsequences
★★★ 10154 Weights and Measures
★★★   116 Unidirectional TSP
★★ 10003 Cutting Sticks
★★★ 10261 Ferry Loading
★★★ 10271 Chopsticks
★★★ 10201 Adventures in Moving – Part IV

Grid

★ 10161 Ant on a Chessboard
★★★ 10047 The Monocycle
★★ 10159 Star
★★ 10182 Bee Maja
★★★   707 Robbery
★★ 10177 (2/3/4)-D Sqr/Rects/Cubes/Boxes?
★★ 10233 Dermuba Triangle
★★★ 10075 Airlines

Geometry

★ 10310 Dog and Gopher
★★ 10180 Rope Crisis in Ropeland!
★★ 10195 The Knights Of The Round Table
★★★ 10136 Chocolate Chip Cookies
★★ 10167 Birthday Cake
★★ 10215 The Largest/Smallest Box …
★★★ 10209 Is This Integration ?
★★★ 10012 How Big Is It?

Computational Geometry

★★ 10135 Herding Frosh
★★ 10245 The Closest Pair Problem
★★★ 10043 Chainsaw Massacre
★★★ 10084 Hotter Colder
★★★ 10065 Useless Tile Packers
★★   849 Radar Tracking
★★★ 10088 Trees on My Island
★★★★ 10117 Nice Milk

Source: http://www.cnblogs.com/penseur/archive/2011/03/10/1979491.html