Ok, finally got AC on 10590, its easy if you know the formula, extremely difficult otherwise.
I think most people can figure out a 2D DP formulation for finding the number of ways which incidentally is the same as the number of integer paritions of a number.

Denote f(n,k) by the number of ways to sum to n where each term is at most k then
f(n,k) = f(n-k, k) + f(n, k-1) if k <= n
f(n,k) = f(n, n) if k > n
f(0,k) = 1
f(n,0) = 0

There is a problem with this because we need 5000 * 5000 big integers to store all the values in the DP table. Actually you'll notice that only two rows are necessary to compute f(n,k) so we can reduce the space complexity to linear but this means for each input we need to compute everything again which may lead to TLE.

The safest way to to use a 1D DP formulation based on the following recurrence, where P(n) denote the number of ways to pick the chocoloates
P(n) = P(n-1) + P(n-2) - P(n-5) - P(n-7) + P(n-12) + P(n-15) .... while the n - k term is non negative
P(0) = 1
The terms are obtained using the formula k * (3 * k - 1) for k = 0, +1, -1, +2, -2, +3, -3 ....
The sign goes from +, +, -, -, +, +, -, - ....

Regards,
Melvin
-----Original Message-----
From: Stephanus
Sent: Wed 6/9/2004 4:52 PM

10590: Chocolate Box
I got TLE. Maybe can ask Melvin for formula?

10593: Kites
At last, I got ACC, first time is 5.598 sec, after optimization 4.232 sec. I still don’t get ACC for real contest. Any idea?
My idea :
Do a brute force check, first check the squares then check the kites

for each cell (i,j) I have this array

down[i][j],up[i][j],left[i][j],right[i][j]
It means from i,j how many steps can you go (down/up/left/right).

int count; <-- counter for answer

1.check the squares
I represent square by it’s upper left corner and size(height,width)
xxx
xxx
xxx
is a square with upper left (1,1) and size(3,3), if you can find the largest square with
upper left (1,1) then total number of square with upper left corner (1,1) is (3 – 1=2),
because we don’t want 1x1 square so we subtract 1.

so in general if you find a largest square with upper left (i,j) and size(n,n), you can get
n – 1 squares.

maximum size of square can be formed from cell (i,j) is min(right( i,j) , down( i, j) )
for maxsize downto 2
if square can be formed
count += size – 1; // minus 1 because we don’t want 1x1 square
break; // we have the largest square then break

2. check the rhombus
I represent rhombus by it’s center and it’s size, e.g
.x.
xxx
.x.
will be rhombus formed by it’s center (2,2) with size 2

for each cell (i,j)
assume that (i,j) is the rhombus’ center, then the maximum size of a rhombus is min(down[i][j],up[i][j],left[i][j],right[i][j])
for maxsize downto 2
if square can be formed
count += size – 1; // minus 1 because we don’t want 1x1 rhombus
break; // we have the largest rhombus then no need to count the smaller one


 

> ----- Original Message -----
> From: Teng Junbin
> Sent: Saturday, June 05, 2004 19:42
>
> Questions attempted: 10519 - 10525
> I can't remember who solved which questions, but I can proudly say
> that all questions were solved by someone or other :)
>
> Before I go on, I feel I have to apologise for choosing these very
> very poor questions. In future, I suggest we do not use Bangladeshi questions for practice, the reasons are:
> 1) The english is terrible. Most of the questions are ridiculously
> easy, but because the english is so bad, most people miss out important points.
> 2) The questions don't make sense. For example, asking you to find
> the inverse of a matrix, but only if you can do it without swapping
> rows (and the way they say this condition) is ridiculous.
> 3) The test data is wrong. The test data for 10525 is wrong. Details later.
> 4) The specification is vague. Most (if not all) of the questions
> do not give a specific description of input/output. The most glaring
> one is the matrix question, which doesn't even say that input can be floating point (they can) and output has to be to 6 dp (it does)
> 5) It's too easy.
> 6) Input to your question can contain weird values like 00005
> (10521)
>
>
> 10519: This is a pretty easy question, just have to work out the formula (n^2 - n + 2).
> Special case, for 0, the answer is 1.
>
> 10520: The description is vague, the formula is complicated, but
> just use brute force with memoization and you'll have no trouble with
> it. Note that the specification for the formula is WRONG. If you
> follow the formula strictly, you'll get an infinite loop. The formula
> should have j > 1 instead of j > 0 (since a(4, 1) will call itself
> otherwise)
>
> 10521: Define a function x( p , q ) and do:
>
> print the quotient of p/q (rounded down)
> then call x( q , ( p % q) )
>
> recurse until p is a multiple of q, at which point, just print p/q
>
>
> 10522: This is a mathematical/geometric question. I'm sorry to say
> I haven't figured out the formula, but Zirui has. However, he did not
> managed to finish the question in time. Wailun
> (IOI) mangaed to solve the question, but he had to leave early so he
> didn't have time to explain how he did it. If Zirui/Wailun can enlighten us, that'd be great.
>
> 10523: It is very easy. Just remember to use memoization/DP because
> there is a lot of test cases.
>
> 10524: Simple question, given a matrix, find it's inverse. Use
> gaussian matrix reductrion strategy. Note that you CANNOT swap rows.
> If you cannot find the inverse without swapping rows, then the answer is not possible, even though mathematically, it's possible.
>
> 10525: This is the question that gives me the worst headache. It
> appears that the question is wrong. You have to minimize time before
> you minimize distance (there is one line that says this, but the rest
> of the whole question implies otherwise). Also, when there is more than one road between two points, use the last one in the input, even if this is not the optimise road.
>
>
>
>
> junbin

 

After trying for few days, at last I got it correct =).
My method is memoization

f(i,L,R,last)
seq[] = the sequence given
i = the i-th character of the sequence
L = position of Left foot
R = position of Right foot
last = last foot used

the method is simple : just try all possible L,R position which is UP, LEFT, DOWN, RIGHT

f(i,L,R,last)
min of {
// do nothing
if seq[i] == DOT then f(i+1,L,R,DOT)
// use left foot
for all possible position of left foot LF
f(i+1,LF,R,LEFT)
// use right foot
for all possible position of right foot RF
f(i+1,L,RF,RIGHT)
}


t makes me need few days, because i think when the i-th character is '.' (DOT), I think I need not to try all possible L,R.

regards,
stephanus

How about double-ended BFS?

Each guy has 900 possible locations, so total 810K states which can be hashed with the square of the max possible distance, which can fit in int (30*30).

Then starting from both Houses and both Schools (working backwards), to generate all the states possible without collisions. A collision of a path from Houses and a path from Schools means a possible solution, so choose smaller of the distances.

Double-ended BFS would be about 4x faster than normal BFS. If you can generate the states using priority queue such that no state will be "overwritten" with better values (like Dijkstra), then you can recover the path later, I think. Not very sure on that. Or can do some approximation function also like A* search to close in on the answer faster.

Just some thoughts.

KK

--- Teng Junbin <tengjb@singnet.com.sg> wrote:
> Method discussed:
>
> G = Jill, J = Jack
>
> let min(Jx, Jy, Gx, Gy) = minimum distance between J and G if at some
> point in time, J is at (Jx, Jy) and G is at (Gx, Gy)
>
> Therefore,
>
> min(Jx, Jy, Gx, Gy) =
>
> Minimum of {
>
> Maximum of {
> min(Jx-1, Jy, Gx-1, Gy)
> min(Jx+1, Jy, Gx-1, Gy)
> min(Jx, Jy-1, Gx-1, Gy)
> min(Jx, Jy+1, Gx-1, Gy)
>
> min(Jx-1, Jy, Gx+1, Gy)
> min(Jx+1, Jy, Gx+1, Gy)
> min(Jx, Jy-1, Gx+1, Gy)
> min(Jx, Jy+1, Gx+1, Gy)
>
> ....
> ....
> }
>
>
> ,
>
> Distance(Jx, Jy, Gx, Gy)
>
> }
>
> In words, if J passes through (Jx, Jy) and G passes through (Gx, Gy),
> then
> the cost of (Jx, Jy, Gx, Gy) will be the maximum
> of all possible points
> that can reach (Jx, Jy, Gx, Gy). If this maximum is greater than the
> distance between (Jx, Jy) and (Gx, Gy), then we use the distance
> between (Jx, Jy) and (Gx, Gy) instead.
>
>
> Clearly, this is a DP formulation. However, because the path is not
> fixed and backtracking is allowed (eg: Jack walks EWEWEWEWEWEW),
> there is no fixed sequential way of computing the table as in normal
> DP solutions.
> Instead, we use a method similar to brute force with memoization. The
> actualy recursion is done using loop recursion (instead of
> function/stack
> recursion) since the maximum level is around 900*900, which will
> definitely give you a stack overflow.
>
> This method, in theory, should work, but in practice, is insanely hard
> and complicated to code. Go try it and you'll see. :)
>
>
>
> Another method I came up with, that should be easier to code is using
> Dijkstra's Single Point Shortest Path.
>
> We use a priority queue and prioritise according to the min function
> defined above. At any one time, we consider the point that has the
> MOST cost, ie:
> the one that has the longest distance between Jack and Jill along its
> path and then we branch off from there.
>
>
> I've made a working copy of the second method, however it is extremely
> slow.
> The memory requirement is 32mb, the time given in UVA is TLE ( > 10s).
>
>
> If anyone can come up with another method, or some form of pruning,
> please share. I'm too tired to think right now.. :p
>
>
>
> junbin
>





__________________________________
Do you Yahoo!?
SBC Yahoo! - Internet access at a great low price.
http://promo.yahoo.com/sbc/
 

Hi,

I finally got some time to do 10638. As from the previous discussion, we need to find groups of people whose average is the same as the average of all the people (within 1 cent). Note that there're at most 10 people, so a simple brute force backtracking should do the job.

Note that during the recursion, we can only conclude that a group is 'closed' (i.e. no more people should be added) if that group's average is *exactly* the same as the average. If the average is within one cent's range, you'll fail tests like:

9.55 9.55 9.53

(if 9.55 is considered closed, then 9.53 can never be put in a group, which means you get no answer for this input)

Other than this i found everything else trivial. With a few pruning that seemed too nice and simple to miss, i got a runnig time of 0.01 sec (apparently melvin did a lot better though :P)

Btw, sorry i wasn't at sat's training. The french SEP people had to go out to buy travel insurance today :(



-----Original Message-----
From: Teng Junbin [mailto:tengjb@singnet.com.sg]
Sent: Sat 5/15/2004 7:20 PM
To: Zhou Junyu; Cai Junfu; Guo Yunsong; Junjie Liang; Kah Keng Tay; Li Mengran; Liu Chang; Melvin Zhang; Sing Kiat Oh; Stephanus; Steven Halim; Wang Zirui; You Quan Chong; Leung Ngai-Hang Zachary
Cc:
Subject: Training on 15 May 04 (Sat)

Questions attempted: 10642 - 10650
Questions solved:
10642
10646
10648
10649
10650

Only Zirui, Melvin and myself + the IOI people attended, so there was only 3 teams (ACM + 2 IOI teams)

10650 was an individual question we did while waiting for the IOI people.
Everyone (including the IOI people) solved it.

10642 - TJB
10646 - MZKC
10648 - MZKC
10649 - WZR


Discussion:

10642 - Very simple maths problem. If you realise that all the diagonal paths share equations of the form x + y = c, then solution is trivial

10646 - Simulation problem, pretty trivial

10648 - Probability/combinatorics question. Instead of finding the required answer, find the probability of every box is filled, then take 1 - p.

10649 - Geometry question, the formulation of the answer is pretty easy, but I think precision is a major problem.

10650 - Prime number generation + checking. Again, trivial


Ideas for unsolved:

10643 - Possible DP + Brute force solution. DP for the nodes WITHOUT the root node and brute force to add in the root node
10644 - I think there is a DP formulation. I'll work on it and email you if I can find it. Otherwise, we agree that brute force may work.
10645 - DP solution.
10647 - Use DP to find the cost of putting the house in each interval, then use quadratic maths to determine actual position.



junbin


ps: Zirui, can you please send me your formulation for 10649? I tried many different formulas, all of them worked with every test example I have, but all gave WA :(


Wanna introduce to those C++ guys a technique to do faster string IO and, at the same time, to enjoy the power of STL.

For example, a typical C++ programmer may write:

#include <iostream>
#include <string>

int main() {
string s;
getline(cin, s);
cout << s << endl;
}

But he/she can do better this way:

#include <cstdio>
#include <string>

string readln() {
char c[2000];
gets(c);
return string(c);
}

int main() {
string s;
s = readln();
puts(s.c_str());
}

Two cent, two cent. :)
A word of caution: Though my method improves the IO speed, I don't recommend people who are not familiar with <stdio.h> to use it unless really necessary.

Mixing <stdio.h> and <iostream> results in unexpected runtime error or wrong answers. (I heard the reason is that one of them uses buffer, while the other does not.) This means you have to rely solely on either <stdio.h> or <iostream> for IO. But <stdio.h> is quite different from <iostream>; after making a change (from <iostream> to <stdio.h>), you might experience quite a period of WAs and frustration, like me now.
Hi,

I finally got some time to do 10638. As from the previous discussion, we need to find groups of people whose average is the same as the average of all the people (within 1 cent). Note that there're at most 10 people, so a simple brute force backtracking should do the job.

Note that during the recursion, we can only conclude that a group is 'closed' (i.e. no more people should be added) if that group's average is *exactly* the same as the average. If the average is within one cent's range, you'll fail tests like:

9.55 9.55 9.53

(if 9.55 is considered closed, then 9.53 can never be put in a group, which means you get no answer for this input)

Other than this i found everything else trivial. With a few pruning that seemed too nice and simple to miss, i got a runnig time of 0.01 sec (apparently melvin did a lot better though :P)

Btw, sorry i wasn't at sat's training. The french SEP people had to go out to buy travel insurance today :(



-----Original Message-----
From: Teng Junbin [mailto:tengjb@singnet.com.sg]
Sent: Sat 5/15/2004 7:20 PM
To: Zhou Junyu; Cai Junfu; Guo Yunsong; Junjie Liang; Kah Keng Tay; Li Mengran; Liu Chang; Melvin Zhang; Sing Kiat Oh; Stephanus; Steven Halim; Wang Zirui; You Quan Chong; Leung Ngai-Hang Zachary
Cc:
Subject: Training on 15 May 04 (Sat)

Questions attempted: 10642 - 10650
Questions solved:
10642
10646
10648
10649
10650

Only Zirui, Melvin and myself + the IOI people attended, so there was only 3 teams (ACM + 2 IOI teams)

10650 was an individual question we did while waiting for the IOI people.
Everyone (including the IOI people) solved it.

10642 - TJB
10646 - MZKC
10648 - MZKC
10649 - WZR


Discussion:

10642 - Very simple maths problem. If you realise that all the diagonal paths share equations of the form x + y = c, then solution is trivial

10646 - Simulation problem, pretty trivial

10648 - Probability/combinatorics question. Instead of finding the required answer, find the probability of every box is filled, then take 1 - p.

10649 - Geometry question, the formulation of the answer is pretty easy, but I think precision is a major problem.

10650 - Prime number generation + checking. Again, trivial


Ideas for unsolved:

10643 - Possible DP + Brute force solution. DP for the nodes WITHOUT the root node and brute force to add in the root node
10644 - I think there is a DP formulation. I'll work on it and email you if I can find it. Otherwise, we agree that brute force may work.
10645 - DP solution.
10647 - Use DP to find the cost of putting the house in each interval, then use quadratic maths to determine actual position.



junbin


ps: Zirui, can you please send me your formulation for 10649? I tried many different formulas, all of them worked with every test example I have, but all gave WA :(


 

To deduce whether it's day or night, we only need to examine all the possible valid (race of A, race of B, race of C, race of D, race of E, day/night) tuples. If all these tuples agree that it's day / night, then we have a conclusion. This is exactly the same as the races of A-E, no special handling is required.

Even if there's no human, we possibly can deduce whether it's day or night. E.g. if we are sure that B is lying, and B said it's day, then it must be night.

Liu Chang

-----Original Message-----
From: Stephanus
Sent: 11/5/2004 (星期二) PM 6:49
To: Wang Zirui; Liu Chang; 'Teng Junbin'; 'Zhou Junyu'; 'Guo Yunsong'; Li Mengran; 'Melvin Zhang'; 'Steven Halim'; Leung Ngai-Hang Zachary
Cc:
Subject: Help 592



Hi all,
I want to ask about 592 : Island of Logic, in problem statement (OUTPUT)
...it may be stated whether it is day or night...
does this mean that we may/may not state this?

can we deduce it is night/day if the none of the speakers are human?
if yes,can you give me example?

In sample I/O
3
A: B is human.
B: A is evil.
A: B is evil.

Conversation #4
A is evil.
B is divine.

[My comment:There's no human, so we don't have to state it is day/night]

Do we have to consider only those who are speaking?

What's the answer for these test cases? Can you explain?

6
A: B is human.
A: B is evil.
B: A is human.
C: A is not lying.
B: C is not human.
D: E is not lying.

[My ans/comment]
No facts are deducible
Because we don't know about D and E?

3
A: I am human.
B: I am human.
A: B is lying.

[My ans/comment]
No facts are deducible

7
A: It is night.
B: It is day.
C: I am human.
E: C is human.
C: E is divine.
A: B is lying.
B: C is evil.

[My ans/comment]
No facts are deducible.

Do you have any other test cases?

Thanx in advance.

regards,
stephanus

Hi everyone,

Today we tried to solve 592 - Island of Logic <http://acm.uva.es/cgi-bin/OnlineJudge?Volume:5>. It's a logic programming question. It's a new type of problem for most of us, I guess, and there are new techniques to learn.

The basic method is exhaustive searching, enumerating all possibilities.
But turning the search result into output needs some thought--you might ask questions like "What does inconsistency in the results mean?"

I made a mistake in spelling, taking "devine" for "divine," but I believe you guys won't make this sort of error.

Regards,
Zirui
 

From: Teng Junbin

To: Zhou Junyu ; Cai Junfu ; Guo Yunsong ; Li Mengran ; Liu Chang ; Melvin Zhang ; Stephanus ; Steven Halim ; Wang Zirui ; Zachary Leung

Sent: Wednesday, May 05, 2004 4:36 PM

Subject: Summary for today's training (Wed 5 May)

 

The questions attempted: 10623 - 10627

 

Questions solved:

 

10625 (GNU = GNU'sNotUnix)  :  Everyone.  Method: Brute force

10624 (Super Number)  :  Liu Chang.  Method: Brute force

10626 (Buying Coke)   :   Stephanus, Junbon.  Method:  Brute force, DP

 

Anything wrong with that, please notify me and Yunsong (I think he is keeping score).

 

About 10625:

 

Standard brute force generation/emulation.  Takes around 0.5s  + or - 0.5s

 

 

About 10624:

 

Brute force generation using modulo arithmetic.  Exact details check with Liu Chang.

 

 

About 10626:

 

I think the O(1) method given in the forum may be wrong.. I can't prove it, but it just feels wrong somehow..

 

DP method (with slight brute force type pruning) took 0.7s

Brute force (I think Stephanus used standard brute force pruning techniques as well)  took 0.5s

 

 

About 10623/10627:

 

I think Junfu and Liu Chang were working on a mathematical approach to these questions, but couldn't finished before 1.30pm.  If anyone finds the answer, please share.

 

 

junbin

 

ps: Starting from the 1st training AFTER the release of the results, the CS1102 top students may be joining us.

Nice work on the summary Junbin, I think we should have a roster for this, a different person write a short summary every training session. I managed to do the buying coke question after finally realising I was missing one of the ways to buy a coke which is 1x10 + 3x1 = 1x8 + 1x5 and a hint on reducing the size of the DP from Junbin.

See ya all on Saturday.GNU = GNU Not Unix
Emulation, I think everybody got this

Super Number
Like junbin said, Brute force generation using modulo arithmetic. Exact details check with Liu Chang/Mengran =)

Buying Coke
I don't use any pruning actually, well only one. The difference is how you do brute force and what do you brute force.

Notice to get 8, there are only a few ways (minus means get exchange)
1. 8 = 10 - 1 - 1 (insert 1 coin)
2. 8 = 10 + 1 + 1 + 1 - 5 (insert 4 coin)
3. 8 = 5 + 5 - 1 - 1 (insert 2 coin)
4. 8 = 5 + 1 + 1 + 1 (insert 4 coin)
5. 8 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 (insert 8 coin)

Denote xi, number of times we do the i-th operation, then total coin needed = x1 * 1 + x2 * 4 + x3 * 2 + x4 * 4 + x5 * 8 and x1 + x2 + x3 + x4 + x5 = C (C = number of Coke)

another thing to notice is that we don't have to care about 1 if the input is valid

just brute force :
for x1 = 0 to possible number of n10
for x2 = 0 to possible number of n10 - x1 (notice we get 5 for exchange)
for x3 = 0 to possible number of n5'/2 (n5' = n5 + x2)
for x4 = 0 to possible number of n5' - x3 for x5 we can get easily by above equation,
x5 = C - x1 - x2 - x3 - x4
compute total coin needed
keep track the minimum
output the minimum

maybe you can do further pruning, but doing this is enough

regards,
stephanus
Hi,

Junfu and I juz got 10627 Infinite Race working. The problem was that we used 32-bit ints instead of 64-bits. The method was fine. Juz to restate wat junfu said earlier, we have to calculate three numbers:
1. the number of head-on meets, which occurs when the total distance travelled by A and B is an odd multiple of L 2. the number of overtakes, which occurs when the difference in the distances travelled by A and B is an odd multiple of L 3. the number of double counted cases, which occurs when both A and B have travelled odd multiples of L (simultaneously)

The juz take (1) + (2) - (3). It's a simple O(1), but be careful with all your +1s and -1s.

Liu Chang