10154 - Weights and Measures

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10154 - Weights and Measures

Post by WanBa »

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:

Post by Maxim »

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:

Post by Dominik Michniewski »

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

Post by Red Scorpion »

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 :lol:

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

An easy problem :)

Post by Maxim »

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
:wink:
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:

Post by Dominik Michniewski »

Thanks Maxim :))
Case, which I miss, was turtle's strength < turtle's weight :)))
I don't thinkabout it before :oops:
I got Acc , so I belive now again in LIS algorithm :D

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

Post by Red Scorpion »

Hehe.... :lol: :lol:
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

Post by b3yours3lf »

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

Thanks in advance.

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

Post by Red Scorpion »

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 :lol:

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

Post by b3yours3lf »

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:

Post by turuthok »

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

Post by farsight »

What's LIS?
Longest Increasing Sequence?
:roll:
Thanks

farsight
New poster
Posts: 7
Joined: Wed Aug 06, 2003 4:51 am

Post by farsight »

What's the algorithmic complexity for solving this problem?
:wink:
Thanks.

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

Post by b3yours3lf »

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

Post by farsight »

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

Post Reply

Return to “Volume 101 (10100-10199)”