125 Ad spot 125 Ad spot

ACMSolver or Art of Programming? 24 X 7 Updates

From 2002 ACMSolver is campaigning for free programming knowledge!

7 August 2011 Comments Off

Let’s Learn STL (Rerefences)

The Standard Template Libraries (STL’s) are a set of C++ template classes to provide common programming data structures and functions such as doubly linked lists (list), paired arrays (map), expandable arrays (vector), large string storage and manipulation (rope), etc. The STL library is available from the STL home page. This is also your best detailed reference for all of the STL class functions available.

  • From YoLinux and Wiki
    • Sequences:
      • vector: (this tutorial) Dynamic array of variables, struct or objects. Insert data at the end.
      • deque: Array which supports insertion/removal of elements at beginning or end of array
      • list: (this tutorial) Linked list of variables, struct or objects. Insert/remove anywhere.
    • Associative Containers:
      • set (duplicate data not allowed in set), multiset (duplication allowed): Collection of ordered data in a balanced binary tree structure. Fast search.
      • map (unique keys), multimap (duplicate keys allowed): Associative key-value pair held in balanced binary tree structure.
    • Container adapters:
      • stack LIFO
      • queue FIFO
      • priority_queue returns element with highest priority.
    • String:
      • string: Character strings and manipulation
      • rope: String storage and manipulation
    • bitset: Contains a more intuitive method of storing and manipulating bits.
  • Operations/Utilities:
    • iterator: (examples in this tutorial) STL class to represent position in an STL container. An iterator is declared to be associated with a single container class type.
    • algorithm: Routines to find, count, sort, search, … elements in container classes
    • auto_ptr: Class to manage memory pointers and avoid memory leaks.
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..

16 July 2011 Comments Off

Bunch of Programming Judges…

Some of the online judges designed for programming course are:

  • Moodle Online Judge Plugin, an assignment type for Moodle, which can automatically grade C/C++ assignments.
  • HUSTOJ, HUST Online Judge,C/C++/Pascal/Java/Ruby/Bash/Python supported, an open source OJ system using GPL2.0 license, which support LiveCD mode and FPS format.
  • FPS, Free Problem Set, an open source problemset exchange format based on XML, which providing more than 400 free problems in FPS format.
Tags: ,
15 July 2011 1 Comment

New online judge in Bangladesh

A new online judge is going to start from Bangladesh which is now in test purpose open. This site is developed and owned by Jan-e-Alam, Graduate from DU and he is also an employee of Google. The site, temporarily used for AIUB and DU students practice is better than most of the sites available. You can also solve problem there.

Website: http://180.211.224.73/lightoj/login_main.php

For getting username/pass, mail to jan876_du@yahoo.com with your identity.

(News source: http://groups.yahoo.com/group/cuetcoders/)

Tags: , , ,
9 July 2011 Comments Off

Merge Sort

void MergeSort(int low, int high)
   // a[low : high] is a global array to be sorted.
   // Small(P) is true if there is only one element to
   // sort. In this case the list is already sorted.
   {
       if (low < high) { // If there are more than one element
              // Divide P into subproblems.
              // Find where to split the set.
              int mid = (low + high)/2;
              // Solve the subproblems.
              MergeSort(low, mid);
              MergeSort(mid + 1, high);
              // Combine the solutions.
              Merge(low, mid, high);
       }
   }

   void Merge(int low, int mid, int high)
   // a[low:high] is a global array containing two sorted
   // subsets in a[low:mid] and in a[mid+1:high]. The goal
   // is to merge these two sets into a single set residing
   // in a[low:high]. b[] is an auxiliary global array.
   {
       int h = low, i = low, j = mid+1, k;
       while ((h <= mid) && (j <= high)) {
          if (a[h] <= a[j]) { b[i] = a[h]; h++; }
          else { b[i] = a[j]; j++; } i++;
       }
       if (h > mid) for (k=j; k<=high; k++) {
                       b[i] = a[k]; i++;
                    }
       else for (k=h; k<=mid; k++) {
               b[i] = a[k]; i++;
            }
       for (k=low; k<=high; k++) a[k] = b[k];
   }
Tags:
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++;
}