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 » Tue May 06, 2003 2:40 am

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

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

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by 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
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 » 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 :lol:

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

An easy problem :)

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
: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 » 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 :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 » Fri May 09, 2003 3:34 am

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 » Fri Aug 01, 2003 11:21 am

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

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

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
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

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-
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 » Sat Aug 09, 2003 7:51 pm

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

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

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

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 » Mon Aug 11, 2003 5:33 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

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

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

Post Reply

Return to “Volume 101 (10100-10199)”