## 10154 - Weights and Measures

Moderator: Board moderators

WanBa
New poster
Posts: 14
Joined: Mon Apr 28, 2003 11:21 am

### 10154 - Weights and Measures

can anybody enlighten me about 10154 ?
thank u very very......if .
destiny conditioned by past

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:
There are many problems similar to this one. Here are some of them: 111, 231, 497, 10051, 10131. Try solving 231 first.

Maxim

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Hmmm ... I solved all this problems, but I got WA with this problem
Could anyone tell me what's wrong with this code ? Elements in els table are sorted increasing by weight of turtles and increasing by strength if weight are the same ...

DM

Code: Select all

``````SPOILER WAS CUTTED OFF
``````
Last edited by Dominik Michniewski on Thu May 08, 2003 8:35 am, edited 1 time in total.
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Hi!
I Have solved all problem that Maxim said. (except 10051).
But I don't have any idea how to solve this problem. It is like an LIS with two dimension. There are weights and strenght.
Can anybody tell me the basic idea how to solve this problem.

Thanks.
RS

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

### An easy problem :)

Hi.

Red Scorpion: it's not two-dimensional LIS, but as usual, one-dimensional.
Dominik: to be certain, I've set hs = 1 only if strength of turtle is larger or equals turtle's weight. Also, when searching for LIS, check if both hs and hs[j] differ from zero.

Here is how I've solved this problem:

Code: Select all

``Sorry, but I have to cut it out because it's not fair to give complete algorithm with every step description``

This is how I check if I can stack i-th turtle and all on it to j-th:

Code: Select all

``  If(weight_stack[i] + weight[j] <= strength[j]) then...``
Maxim
Last edited by Maxim on Fri May 09, 2003 9:35 am, edited 2 times in total.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Thanks Maxim )
Case, which I miss, was turtle's strength < turtle's weight ))
I got Acc , so I belive now again in LIS algorithm

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Hehe....
This is just a one dimension LIS.
Thanks maxim, now I got AC.

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am
I always got WA, could someone give me sample input and output??

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
try this

100 101
200 300
10 500
1 1000
20 30
40 40
500 901
152 199
1 2
3 40
2 1000

output:
8

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am
Sorry, I don't get it, how could the output = 8 not 7 ?
Could you give me the sequence??

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
Sequence for RedScorpion's input ...

Code: Select all

``````[2 1000]
[1 1000]
[500 901]
[10 500]
[152 199]
[3 40]
[20 30]
[1 2]
``````
-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

farsight
New poster
Posts: 7
Joined: Wed Aug 06, 2003 4:51 am
What's LIS?
Longest Increasing Sequence?

Thanks

farsight
New poster
Posts: 7
Joined: Wed Aug 06, 2003 4:51 am
What's the algorithmic complexity for solving this problem?

Thanks.

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am
LIS=Longest Increasing Subsequence
This algorithms has complexity O((n*n)/2) if I not wrong.

farsight
New poster
Posts: 7
Joined: Wed Aug 06, 2003 4:51 am
Thanks...
Could you give me a hint as to the recurrence for the solution?