10154 - Weights and Measures

WanBa · Post by **WanBa** » Tue May 06, 2003 2:40 am

can anybody enlighten me about 10154 ?
thank u very very......if .

Maxim · Post by **Maxim** » Tue May 06, 2003 9:50 pm

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 · Wed May 07, 2003 11:05 am

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

Red Scorpion · Post by **Red Scorpion** » Wed May 07, 2003 11:42 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 · Post by **Maxim** » Wed May 07, 2003 8:54 pm

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

Dominik Michniewski · Post by **Dominik Michniewski** » Thu May 08, 2003 8:35 am

Thanks Maxim

)
Case, which I miss, was turtle's strength < turtle's weight

))
I don't thinkabout it before

I got Acc , so I belive now again in LIS algorithm

Best regards
DM

Red Scorpion · Post by **Red Scorpion** » Fri May 09, 2003 3:34 am

Hehe....

This is just a one dimension LIS.
Thanks maxim, now I got AC.

b3yours3lf · Post by **b3yours3lf** » Fri Aug 01, 2003 11:21 am

I always got WA, could someone give me sample input and output??

Thanks in advance.

Red Scorpion · Post by **Red Scorpion** » Mon Aug 04, 2003 5:42 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 · Post by **b3yours3lf** » Fri Aug 08, 2003 7:50 am

Sorry, I don't get it, how could the output = 8 not 7 ?
Could you give me the sequence??

turuthok · Post by **turuthok** » Fri Aug 08, 2003 6:59 pm

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-

farsight · Post by **farsight** » Sat Aug 09, 2003 7:51 pm

What's LIS?
Longest Increasing Sequence?

Thanks

farsight · Post by **farsight** » Sun Aug 10, 2003 4:17 pm

What's the algorithmic complexity for solving this problem?

Thanks.

b3yours3lf · Post by **b3yours3lf** » Mon Aug 11, 2003 5:33 am

LIS=Longest Increasing Subsequence
This algorithms has complexity O((n*n)/2) if I not wrong.

farsight · Post by **farsight** » Mon Aug 11, 2003 4:02 pm

Thanks...
Could you give me a hint as to the recurrence for the solution?

OJ Board

10154 - Weights and Measures

10154 - Weights and Measures

An easy problem :)