863 - Process Scheduling

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

Moderator: Board moderators

Post Reply
alexg
New poster
Posts: 5
Joined: Wed Sep 01, 2004 11:24 am
Location: London, UK

863 - Process Scheduling

Post by alexg »

OK...finished my program but it always returns WA

I've tried making lots of test input but still can't find a problem.

Anyone else tried this and want to share some I/O?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

It's probably very difficult to get AC now since there's no special judge and no specifications about which solution should be printed, but a special judge is on its way, so just hang in there. :)

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

It also looks as if it is a multi input problem. I verified with asserts that the first line of the input file contains just one number. And if I treat it as a multi input file, my program reads all the input, not too much, not too little. It is obvoius that there should be a special judge.

alexg
New poster
Posts: 5
Joined: Wed Sep 01, 2004 11:24 am
Location: London, UK

Post by alexg »

Yep..that's what I thought. Oh well, I'll wait for clarification or someone to submit an accepted solution.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

The new data and judge is online now, but noone else has gotten AC.

And the problem statement has been fixed (there are multiple test cases), but joey, since you already had figured that out it's a bit strange that you didn't get AC.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho »

wow, you guys actually find an efficient algorithm? very impressive! Do you mind feeding me a hint or so? Thanks! :wink:

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

As far as I know, there is no efficient algorithm known for this problem, but I don't think it is known to be NP-complete (because the number of processors is quite small). For the special case when all processes have length 1, it is (or at least was a few years ago) an open question whether the problem is NP-complete for three processors.

So backtracking is the way to go here.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Well, that explains my WA. I used greedy with some prioritising heuristics, but that doesn't work then.
If backtracking is the only way, I can't see a way to cut the zillions of different possiblities. Reducing the proces times modulo the number of processors will obviously give WA.

BTW. Congratz Per on winning Waterloo! Is it you alone, or do you work as a team?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

little joey wrote:Well, that explains my WA. I used greedy with some prioritising heuristics, but that doesn't work then.
I actually forgot to make sure that greedy solutions would fail on the test data, so it's nice to hear that they do. :)
little joey wrote:If backtracking is the only way, I can't see a way to cut the zillions of different possiblities. Reducing the proces times modulo the number of processors will obviously give WA.
Yup, though you could "semi-reduce" them to the range [1..2N]. Not sure it would help though; as it turns out, the hard cases (at least for my solution) occurs when the process times are quite small (smaller than N).

The input is not as mean as it could have been, so give it a try. It is relatively easy to construct test cases where my solution fails miserably to deliver a solution within any reasonable time.
little joey wrote:BTW. Congratz Per on winning Waterloo! Is it you alone, or do you work as a team?
Thanks, it was nice to be able to go home an hour earlier than expected. :)
This was as a team (though there were only two of us for the first 30 or so minutes).

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Hmm. Semi reduction wouldn't work for a case like this (if I understand it correctly):

Code: Select all

5 5
11
2
4 2
1 3
2 4
Which would give something like:

Code: Select all

1 1 1 1 1
2 2 1 1 1
3 3 3 3 1
4 1 1
5 5
While the optimal solution is:

Code: Select all

2 2 1 1 1
3 3 3 3 1
4 1 1 1 1
5 5 1 1 1

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

Yeah, sorry, you're right. And on a related issue, I realised that I have made another faulty assumption in my solution, so that I actually produce suboptimal solutions. :oops:

I'll try to fix it as soon as possible. If you have an optimal solution, you should still get accepted (the only problem is that suboptimal solutions may be allowed). On the other hand, I'm not sure if it is possible to have an optimal solution which solves the current judge data within the time limit.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho »

hello,
what is semi-reduction?
Last edited by yiuyuho on Wed Sep 22, 2004 8:11 am, edited 1 time in total.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

SemiReduce(low, hi, mod, n) ::= n >= lo ? n <= hi ? n : SemiReduce(low, hi, n-mod, mod) : SemiReduce(low, hi, n+mod, mod) :)

I've fixed the data now, but still no AC. The result mainly seemed to be that some TLEs were transformed into WAs and RTEs. If anyone has a solution they'd like me to check, feel free to send it to me.

event
New poster
Posts: 2
Joined: Sat Oct 29, 2005 12:54 pm

863 WA

Post by event »

Please, help. On

Code: Select all

2

3 5
4
3
2 4 2
2 1
1 3

5 5
11
2
4 2
1 3
2 4
I give

Code: Select all

 1  1  1
 1  2  2
 2  4  4
 3  3   
 5      

 2  2  1  1  1
 3  3  3  3  1
 4  1  1  1  1
 1  1  1  5  5

I do nothing for 0 test cases. So it should work well for me. But WA:( May be anybody has more test cases for the problem

Post Reply

Return to “Volume 8 (800-899)”