Contest date: 11 August 2009 9:15-14:15
Contest Problems: A-H, click here
Problem
Setter: Seksun Suwanmanee Problem
described in English
Solved by 21 teams First team solver: CU Star04 Chulalongkorn University at 11 minutes
Problem
explanation
Happy number verification: 6*(9^2) = 486 is the max value of the sum of square of each
digit of a positive number n less than 10^6. Any positive integer having 3
digits yield eventually the sum (of square of its digits) having value
between 1 and 10. Check if it can reach the value 1, 7 or 10. If so, it
is a happy number. Otherwise, it is not.
Prime number verification: If number n is an odd number greater than 2, check from i=3 until i=sqrt(n) if n is divisible by
i . Stop immediately when n is divisible by any
number because it is not a prime number.
Happy Prime number: For odd numbers i from 3 up to n,
first verify if i is a happy
number. If so, then verify if it is also a prime number.
Example
solution program
C source
code : happyPrime.c
Test Cases
|
Input |
Output |
|
n=1000000,
1 data, 1 line |
11144 lines (doutput.out, size 74.5KB) |
|
1000000 |
7 13 19 23 31 79 97 103 109 139 167 193 239 263 293 313 331 367 379 383 397
|
Problem
Setter: Amarin Deemagarn Problem
described in Thai ไทย
Solved by 34 teams First team solver: Optimus
Prince of
Problem
explanation
การสลับตัวอักษรในสตริง
...
Test Cases
|
Input |
Output |
|
12
data sets, 13 lines( binput.in,
size 128 bytes) |
12 lines |
|
abc cba acb bdca fedcba abcdefghijklmnopqrstuvwxzy zyxa baxwzy porqtsvuyx ijklmnopq egkptszx zbcdefghijklmnopa 000 |
0 1 1 2 3 1 2 3 5 0 2 1 |
Problem
Setter: Amarin Deemagarn Problem
described in Thai ไทย
Solved by 21 teams First team solver: Soda - Khon Khaen University at 21 minutes
Problem
explanation
การแปลงสตริง ...
Test Cases
|
Input |
Output |
|
16
data sets, 33 lines ( ainput.in,
size 290 bytes) |
16 lines |
|
Ttsze isium ztoai uah a a xyzt mmi thinner rih tttt rr tvaaaaaa im ttttta rruu wwwwwwwwwwwwwwwwwwwwwrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrxxxxxxxxxaaa m saat sopp rt ey a x bbbbbbtt uu axaxaxaxvttttttttasdsasas iiii eeeeeffffffg mmg trrriiii fqqqqqq 000 |
YES YES YES YES YES YES YES YES YES NO NO NO YES YES YES NO |
Problem
Setter: Seksun Suwanmanee Problem
described in Thai ไทย
Solved by 7 teams First team solver: CU Star08 Chulalongkorn University at 34 minutes
Problem
explanation
ต้องคำนวณหาจำนวนรถให้กับแต่ละทัวร์ตามลำดับ
โดยแต่ละทัวร์ต้องใช้จำนวนรถของแต่ละประเภทที่มีเหลืออยู่เท่านั้นและจำนวนที่นั่งต้องเพียงพอต่อจำนวนลูกทัวร์
ลองเปลี่ยนจำนวนรถแต่ละประเภทและคำนวณที่นั่งรวมให้มากกว่าหรือเท่ากับ np แล้ว คำนวณราคารวม
(นำ nkm ไปคิดด้วย)
ให้ได้น้อยที่สุด
Test Cases
|
Input |
Output |
|
20
data sets, 21 lines |
20 lines |
|
20 8
100 9
200 8
150 6
500 9
200 8
1000 5
800 6
650 9
700 10
1050 10
500 18
650 180
300 210
600 42
510 75
500 65
800 49
200 230 500 25 300 |
1 0 0 0 3100 1 0 0 0 4200 1 0 0 0 3650 1 0 0 0 7500 1 0 0 0 4200 1 0 0 0 13000 1 0 0 0 10800 1 0 0 0 9150 1 0 0 0 9700 1 0 0 0 13550 1 0 0 0 7500 0 1 0 0 11600 0 0 1 3 45800 1 0 0 4 86600 0 0 0 1 17250 0 1 2 0 37100 0 2 1 0 47200 0 1 1 0 13100 0 0 0 0
0 0 0 1 0 9800 |
Problem
Setter: Andrew Davison
Problem
described in English
Solved by 11 teams First team solver: CU Star03 Chulalongkorn University at 19 minutes
Problem explanation
The first step is to identify the problem category, which in this case is a variant of the knapsack problem in dynamic programming. You should be familiar with this kind of algorithm since it's common in programming (and programming competitions).
The basic solution to a knapsack problem is to generate all combinations of some elements, and score them. The combination with the 'best' score is the winner. A larger combination, and its score, is based on adding to an existing smaller combination, and its score. In other words, the fina answer is built by combining sub-answers.
A crucial part of the knapsack problem is the cost function used to score a combination. Identifying the cost function for a problem is a big step in solving it.
You should also look for ways to reduce the problem size, so you can get to an answer in a reasonable amount of time.
The problem states that there are at most 100 people in the association, and the two teams must not differ by more than one. That means that a team can have at most 50 members. The actual total size of the association is easy to find by counting the number of inputs.
The maximum weight of a player is 450, and so the total weight of all the players must be 100*450 (45000) or less. The actual total weight is easy to find by summing the input weights.
Note that you only need to calculate team weights, not build a list of team members.
The cost function for this problem involves measuring the absolute difference between the two teams weights i.e.
Math.abs( weight_team1 - weight_team2 )
The best pair of teams is the one with the lowest absolute difference, i.e. 0, which means that the two teams weight the same.
Actually, you only need to calculate the weight of one team, since the other team's weight is the total weight of all the players minus the weight of the first team. So the cost function becomes:
Math.abs( 2*weight_team1 - total_weight_of_all_players
)
The solution included here is
just one possible way of getting to an answer. For example, instead of using nested
loops, it's possible to use recursion and backtracking. Also, the
cost function can be varied there's a more useful version which employs the positive/negative
values that are lost by Math.abs().
Example
solution program
Java source code : wrestlingTeams.java
Test Cases
|
Input |
Output |
|
100
data, 101 lines(finput.in,
size 387 bytes) |
1 line |
|
100 256 315 222 302 410 48 335 243 382 160 439 92 261 308 450 213 . |
12248 12248 |
Problem
Setter: Steven & Felix Halim Problem
described in English
Time Limit: 3 seconds
Solved by 1 team First team solver: CU Star08 Chulalongkorn University at 262 minutes
Problem
explanation
Problem in short: given a (family) tree with special trait: vertex values are increasing from root to leaves. Find the vertex closest to root that has value >= a number P.
Naive solution is to do this per query: start from a given vertex, and move up the family tree until we hit the first ancestor with value < P. O(QN), Time Limit (3 seconds) Exceeded as N >= 80K and Q >= 20K (tested on the contest machine) .
A better solution is to store all the 20K queries first O(Q). Then traverse the family tree *just **once* using O(N) DFS(Depth First Search) starting from root. For each vertex that is asked in query perform a O(log N) *binary search* along the path from root to current vertex to get ancestor with desired level of skill. Binary search is possible as the vertices have values in increasing order. Finally, do an O(Q) post-processing to output the results. Complexity = O(Q+N+Q log N+Q), which is manageable. It runs in < 2 seconds.
Example
solution program
C++ source code : ancestor_ac.cpp
Test Cases
|
Input |
Output |
|
(N=80000,Q=20000)x
4 data sets |
4x20000=80000
lines |
|
80000
20000 0
187 1
633 2
1334 3
1855 4
2640 5
3323 6
3412 7
3932 8
4932 9
5747 10
6501 ... |
53209 3311 5800 2805 10503 9553 29366 12193 1974 12818 24589 43418 ... |
Problem
Setter: Jittat Fakcharoenphol
Problem
described in English
Solved by 4 teams First team solver: CU Star05 Chulalongkorn University at 227 minutes
Problem
explanation
. . .
Example
solution program
C++ source code : pbH_space.cc
Test Cases
|
Input |
Output |
|
11
data sets,86 lines(hinput.in
, size 804 bytes) |
11 lines |
|
11 30
30 1 0
15 15 15 30
30 1 1
0 15 30 16 10
10 3 0
4 4 4 1
0 8 5 10 1
8 0 10 5 10
10 6 1
0 0 1 1 1
0 9 1 10 1
9 0 10 1 1
3 3 4 4 1
6 6 7 7 1
9 9 10 10 ... |
18 450 10 30 20 8 60 28 18 6 16 |
Problem
Setter: Jittat Fakcharoenphol
Problem
described in English
Solved by 6 teams First team solver: CU Star03 Chulalongkorn University at 88 minutes
Problem
explanation
. . .
Test Cases
|
Input |
Output |
|
7
data sets, 2041 lines(einput.in
,size 14.1 KB) |
7 lines |
|
7 100 1
86 1
10 1
48 1
29 1
67 1
96 1
77 1
20 1
58 1
39 1
87 1
68 1
11 1
49 1
30 1
97 ... |
To be
updated ... |