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++;
}
1 June 2011 Comments Off

QuestToSolve.Com | A nice attempt to improve problem solving skills

A nice attempt to improve problem solving skills: http://www.questtosolve.com/

“(…)In the spirit of Steven Halim’s World of Seven: Methods to Solve website, that posted the solutions to hundreds of problems for the University of Valladolid (UVa) Online Judge website, we have decided to not only tackle UVa problems in preparation of ACM ICPC competition, but also to post the answers that we find for each problem in the hope that our repository of solutions will be as great an informational resource to programmers everywhere as Steven’s was.

Who are we? Two students majoring in Computing Science from Simon Fraser University in British Columbia, Canada.(…)”

31 May 2011 Comments Off

Ranklist (Scoreborad) ACM ICPC WF 2011

ACM International Collegiate Programming Contest (abbreviated as ACM-ICPC or just ICPC) is an annual multi-tiered computer programming competition among the universities of the world.Congratulations to Zhejiang University – the 2011 ACM-ICPC World Champions!

Congratulations to Zhejiang University – the 2011 ACM-ICPC World Champions!

Photo by Ravi Melaram

Photo by Jason Daly

Rank Team Solved Time
1 Zhejiang University 8 1228
2 University of Michigan at Ann Arbor 8 1462
3 Tsinghua University 7 800
4 St. Petersburg State University 7 893
5 Nizhny Novgorod State University 7 938
6 Saratov State University 7 966
7 Friedrich-Alexander-University Erlangen-Nuremberg 7 1088
8 Donetsk National University 7 1155
9 Jagiellonian University in Krakow 7 1176
10 Moscow State University 7 1187
11 Ural State University 7 1345
12 University of Waterloo 7 1555
13 Taurida V.I. Vernadsky National University 6 614
14 National Taiwan University 6 804
15 University of Warsaw 6 872
16 St. Petersburg State University of IT, Mechanics and Optics 6 931
17 Nanyang Technological University 6 958
18 Universidad de Buenos Aires – FCEN 6 965
19 Korea Advanced Institute of Science and Technology 6 965
20 Peking University 6 1012
21 Sharif University of Technology 6 1066
22 Carnegie Mellon University 6 1110
23 Shanghai Jiao Tong University 6 1113
24 Lviv National University 6 1150
25 The Chinese University of Hong Kong 6 1243
26 Zhongshan (Sun Yat-sen) University 6 1367
27 University of Electronic Science and Technology of China 5 648
28 Taras Shevchenko Kiev National University 5 754
29 Massachusetts Institute of Technology 5 803
30 Belarusian State University 5 811
31 Universidade Federal de Pernambuco 5 817
32 University of Tokyo 5 822
33 South Ural State University 5 839
34 Kazakh-British Technical University 5 874
35 Perm State University 5 927
36 Kyoto University 5 935
37 Novosibirsk State University 5 1010
38 Fudan University 5 1225
39 Harbin Institute of Technology 5 1312
40 Tianjin University 5 1353
41 University of Helsinki 5 1447
42 Universidade Federal do Paraná 4 386
43 Moscow Institute of Physics & Technology 4 452
44 Wuhan University 4 550
45 Universidade de São Paulo – Escola Politécnica 4 590
46 Princeton University 4 673
47 Universidade de São Paulo – Instituto de Matemática e Estatística 4 675
48 International Institute of Information Technology – Hyderabad 4 710
49 East China Normal University 4 732
50 Universidad Nacional de Córdoba – FaMAF 4 759
51 University of Alberta 4 763
52 Seoul National University 4 772
53 Swiss Federal Institute of Technology Zurich – VIS 4 808
54 Beijing Jiaotong University 4 813
55 Indian Institute of Technology – Delhi 4 862
56 University of Wroclaw 4 896
57 University of Stellenbosch 4 981
58 Pontificia Universidad Católica del Perú 4 1025
59 Hangzhou Dianzi University 3 263
60 Fuzhou University 3 272
61 California State University – Chico 3 288
62 German University in Cairo 3 389
63 University of New South Wales 3 395
64 Ain Shams University 3 426
65 Bangladesh University of Engineering and Technology 3 431
66 Leiden University 3 447
67 Huazhong University of Science & Technology 3 447
68 Instituto Tecnológico de Aeronautica 3 491
69 University of Miami 3 536
70 Shandong University 3 538
71 Universidade Federal de Minas Gerais 3 560
72 Harvey Mudd College 3 601
73 Simon Fraser University 3 682
74 Ho Chi Minh City University of Science 2 137
75 University of Oklahoma 2 142
76 Hong Kong University of Science and Technology 2 152
77 Universidad de Guanajuato – CIMAT 2 159
78 Zhejiang Normal University 2 193
79 University of Chicago 2 225
80 Duke University 2 243
81 Alexandria University – Faculty of Engineering 2 248
82 American University of Sharjah 2 299
83 Harbin Engineering University 2 332
84 University of Wisconsin – Madison 2 359
85 Orel State Technical University 2 374
86 Universidad del Valle 2 375
87 Universidad Católica Boliviana – La Paz 2 377
88 University of Minnesota – Twin Cities 2 408
89 Universidad de las Ciencias Informáticas 2 426
90 University of California – San Diego 2 542
91 University of Maryland 2 596
92 Illinois State University 2 607
93 Universidad de La Habana 2 703
94 Universidad Nacional de Colombia – Bogotá 2 718
95 University of Virginia 2 883
96 University of Canterbury 1 38
97 South Dakota School of Mines and Technology 1 146
98 EAFIT University 1 175
99 Cairo University – Faculty of Computers and Information 1 193
100 University of Illinois at Urbana-Champaign 1 242
101 Amirkabir University of Technology 0 0
101 DJ Sanghvi College of Engineering 0 0
101 Indian Institute of Technology – Kanpur 0 0
101 King Abdullah University of Science and Technology 0 0
101 Sichuan University 0 0

Well.done all teams specially-B.U.E.T. Annihilator, Dr. Mohammad Kaykobad, Tasnim Imran Sunny, Muntasir Mashuq, Anindya Das for solving three (3) problems.
Source: http://scrool.se/icpc/wf2011/

30 April 2011 Comments Off

Some ICPC Related Blogs

Tags: ,
21 April 2011 Comments Off

Training ICPC Teams: A Technical Guide by Rujia Liu

Hello, everyone should take a look to Training ICPC Teams: A Technical Guide by Rujia Liu

5 March 2011 Comments Off

ACM-ICPC Prominent Problemsetters and Sites

Here we mention about some problem setters of ACM and their problems (click below):

Shahriar Manzoor Find Shahriar in wikipedia
Gordon V. Cormack
Derek Kisman
K. Monirul Hasan
Md. Kamruzzaman (KZaman)
Piotr Rudnicki
Rujia Liu
Sohel Hafiz
Igor Naverniouk (Abednego)
Rezaul Alam Chowdhury
Abdullah-al-Mahmud (Satej)
Jimmy Mårdell
Md. Arifuzzaman Arif
Manzurur Rahman Khan (Sidky)
Mohammad Mahmudur Rahman
Ondřej Lhoták
Joachim Wulff (Little Joey)
Mak Yan Kei
Mohammad Sajjad Hossain
Jane Alam Jan
Per Austrin
Shamim Hafiz
Anupam Bhattacharjee

Source: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=43&limit=50&limitstart=0

ACM-ICPC websites (From Wikipedia)