863  Process Scheduling
Moderator: Board moderators
863  Process Scheduling
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?
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?

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
As far as I know, there is no efficient algorithm known for this problem, but I don't think it is known to be NPcomplete (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 NPcomplete for three processors.
So backtracking is the way to go here.
So backtracking is the way to go here.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
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?
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?
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:Well, that explains my WA. I used greedy with some prioritising heuristics, but that doesn't work then.
Yup, though you could "semireduce" 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).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.
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.
Thanks, it was nice to be able to go home an hour earlier than expected.little joey wrote:BTW. Congratz Per on winning Waterloo! Is it you alone, or do you work as a team?
This was as a team (though there were only two of us for the first 30 or so minutes).

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Hmm. Semi reduction wouldn't work for a case like this (if I understand it correctly):
Which would give something like:
While the optimal solution is:
Code: Select all
5 5
11
2
4 2
1 3
2 4
Code: Select all
1 1 1 1 1
2 2 1 1 1
3 3 3 3 1
4 1 1
5 5
Code: Select all
2 2 1 1 1
3 3 3 3 1
4 1 1 1 1
5 5 1 1 1
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.
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.
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.
hello,
what is semireduction?
what is semireduction?
Last edited by yiuyuho on Wed Sep 22, 2004 8:11 am, edited 1 time in total.
SemiReduce(low, hi, mod, n) ::= n >= lo ? n <= hi ? n : SemiReduce(low, hi, nmod, 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.
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.
863 WA
Please, help. On
I give
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
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
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