Transcript Team Competition in Mathematics and Informatics “Ugāle

Team Competition in Mathematics
and Informatics “Ugāle”- Finding
New Task Types
Mārtiņš Opmanis
Institute of Mathematics and Computer Science of University of Latvia
IOI Conference 10.08.2009
Basic facts about competition
• Idea by teacher of informatics and
physics of Ugāle secondary school
Aivars Žogla
• National annual competition since 1996
• Team competition (up to three contestants
and one computer)
• Two rounds (on-line semifinal and final for
best teams in Ugāle)
• 5 to 5.5 hours
• Winner team gets a trophy and cake
Tasks (format)
• Short answer format – number, set of numbers,
filled table, text string (on paper) or text file.
Main idea – to avoid long proofs, etc. To minimize
subjective factor and allow to check all solutions
in limited amount of time (approx two hours).
• Not-too-long problem descriptions
• 8-10 for semifinals, 10 for final
• Every task is worth 100 points
• Usually have subtasks ( usually 20/30/50 points)
ACM tasks
Solvable with help of computer
IOI (LIO)
tasks
“Ugāle”
tasks
SUDOKU
WPC tasks
IMO (LMO)
tasks
Solvable by humans
Construction of tasks must start from somewhere…
ACM tasks
Solvable with help of computer
IOI (LIO)
tasks
SUDOKU
WPC tasks
IMO (LMO)
tasks
Solvable by humans
Don’t loose basic things, like:
“find all solutions and prove that there are no other”
Cryptarythms
2PN
 N2P
----NPNP
PPP
N2N
----NN2NP
“ N” - odd,
“ P” - even
KSIM2004

*KSIM*
----------------*********
*********
********
*********
*********
****IR***
----------------***NOTIKUMS***
Combinatorics
Direction of reading can be changed no more than twice.
How much times you can read “ APRICOT” in the given table?
The same task if there are 7 (in picture), 36, 711 and 1492 different letters.
Number theory
Let’s name an n-digit prime p1 p2...pn
as a Ugāle’s prime if and only if all prefixes of this number
p1 , p1 p2 , p1 p2 p3 , … , p1 p2...pn1
also are primes.
For example, 71 and 311 are Ugāle primes (because 71,
7, 311, 31 and 3 are primes), but 27, 43 and 307 – are not
(27, 4 and 30 are not primes). Find one, as large as
possible a Ugāle’s prime!
Score for tasks like this are calculated relatively to
the best achieved or the best known result.
Logic
Answer three questions below by “yes” or
“no” so that all the answers do not
contradict each other:
1.Are the answers to Questions 2 and 3
equivalent?
2.Is “no” the answer to Queston 1?
3.Is it true that there are two consecutive
questions with the same answer?
Geometry
Regular hexagon. Midpoints and vertices are connected.
Calculate the gray area.
Answer is one number (non-integer!)
Geometry
87
146
„The intersection of two
triangles is hexagon with
inner angles (in this order):
87, 141, 105, 137, 104
and 146.
Calculate the angles of
these triangles!”
141
104
137
105
Where is the trick?
You must find all solutions!
Sad result: All teams in
this round get for this
task just 25 points.
Geometry (construction)
„Let’s say that a convex pentagon is „elegant” if the following
conditions are satisfied:
• it can be inscribed in circle,
• the length of all sides and radius of the circumscribed circle
can be expressed in whole centimetres,
• all sides and radius of the circumscribed circle are of different
length.
Let’s say that a convex pentagon is ”partly elegant” if only the
first two conditions are satisfied. Your task is to construct either
an elegant (100 points) or partly elegant (30 points) pentagon.”
Answer consists of six integers.
Easy to check correctness of the answer.
Geometry in the nature
Find the distance (in ropes)
between lampposts without
destruction of school building
I am from the XX century
(thePAST) …
• It is not obvious what types of puzzles and
games are known to youth
• Are they playing table games? What games?
• Do they play chess? Know basic rules?
• Do they know what is pentamino?
Draw all 12 pieces in short amount of time?
• Do they know rules of SUDOKU?
REVERSE SUDOKU
Create SUDOKU puzzle with less as possible filled cells so that it will have
unique given solution.
If solution will not be unique or differs from the given, you will get no
points.
9
8
1
6
2
4
7
5
3
6
5
2
9
3
7
1
8
4
7
3
4
5
8
1
2
6
9
5
4
6
1
7
2
9
3
8
2
9
3
4
6
8
5
1
7
8
1
7
3
9
5
4
2
6
3
7
8
2
1
9
6
4
5
4
2
9
8
5
6
3
7
1
1
6
5
7
4
3
8
9
2
Dominoes
• Are chosen as simple and well-known model
to build different tasks
• Ordinary set of 28 pieces
• All pieces must be
placed in the given field
• If two pieces share
common edge, number
of points in the
corresponding halves
must be the same
• Sum of points in the
rows marked by arrows
must be the same
• It is enough to find one
solution
Fill a rectangle consisting of 8×7 squares with the
numbers from 0 to 6 (in each square there must
be one number) so that this rectangle can be
covered by pieces of one set of dominoes (every
square is covered by half of one dominoe, all
squares are covered) in as many ways as
possible.
Best known result is arrangement with 793648 different
coverages (found eight years after competition by former IOI
gold medalist Jānis Sermuliņš).
Represent integers by dominoes from one set
1 2 0 5
and ask to create number(s) with particular
properties
ACM tasks
Solvable with help of computer
IOI (LIO)
tasks
SUDOKU
WPC tasks
IMO (LMO)
tasks
Solvable by humans
Find something interesting in programming beyond
usual tasks
Algorythm analysis
In the file SORT.PAS an algorithm is given that sorts
the elements of number array A[0..n–1] from position
low till position high in non- decreasing order. By taking
low = 0 and high = n – 1, the entire array will be sorted.
Your task is to find an array containing each of the
numbers from 1 to 20 exactly once, for which sorting
by calling procedure sort(A,0,19), uses the maximum
number of array element comparison operations (these
rows are marked by {*}) For example, sorting the array
A={3,4,1,2,5}, uses 7 comparison operations.
Different programming task
(last task in this presentation)
Write a program in Pascal, C or BASIC, which
• outputs on the monitor the number 1998 only once;
• if the program code is modified by replacing one
symbol by another in such a way that program still
compiles and executes, it still only once outputs the
number 1998.
How to check correctness of the solution?
Wrong solution
var aa:integer;
Begin
aa:=1998;
if aa=1998 then writeln(aa) else writeln(1998);
End.
var aa:integer;
Begin
aa:=1998;
10
if aa=1998 then writeln($a) else writeln(1998);
End.
Wrong solution
var aa:integer;
Begin
aa:=1998;
if aa=1998 then writeln(aa) else writeln(1998);
End.
var aa:integer;
Begin
aa:=1998;
1998
1998
if aa=1998 then writeln(aa) else;writeln(1998);
End.