Page 1 of 1

863 - Process Scheduling

Posted: Tue Sep 07, 2004 4:11 pm
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?

Posted: Wed Sep 08, 2004 9:16 am
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. :)

Posted: Wed Sep 08, 2004 10:34 am
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.

Posted: Wed Sep 08, 2004 11:29 am
by alexg
Yep..that's what I thought. Oh well, I'll wait for clarification or someone to submit an accepted solution.

Posted: Tue Sep 14, 2004 6:32 pm
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.

Posted: Sat Sep 18, 2004 3:43 am
by yiuyuho
wow, you guys actually find an efficient algorithm? very impressive! Do you mind feeding me a hint or so? Thanks! :wink:

Posted: Sat Sep 18, 2004 10:55 am
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.

Posted: Mon Sep 20, 2004 12:17 pm
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?

Posted: Mon Sep 20, 2004 12:48 pm
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).

Posted: Mon Sep 20, 2004 2:03 pm
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

Posted: Mon Sep 20, 2004 3:01 pm
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.

Posted: Mon Sep 20, 2004 9:24 pm
by yiuyuho
hello,
what is semi-reduction?

Posted: Thu Sep 30, 2004 4:52 pm
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.

863 WA

Posted: Sun Nov 13, 2005 5:32 pm
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