shahianshu's blog

Spoj RRSCHED WA HELP PLEASE !!
By shahianshu, history, 6 years ago, In English

hello , i am getting wa for my code of the problem round robin scheduling , I have tried many test case I couldn't come up with a test case where my code fails.

MY APPROACH :- i have made an observation that for each task Ti it will become zero only at an iteration equal to Ti . For example, suppose Ti = 9 then this element will become zero at the 9th iteration irrespective of all the other tasks . So i thought that i need to just sort the array based on the value of Ti and then the smallest value Ti will be the one going 1st and then all the Ti's whose values are greater than it . So , i kept two values in the vector , first :- value of Ti , and second :- index of particular Ti . Now i sorted the vector , if values of some element a and b are equal then i sort them in increasing order of index. I also maintained a binary indexed tree denoted by bit[] , this is used to tell me how many total tasks are still present before a particular element.

MY SOLUTION( i have commented each and every part ) :- link

UPDATE :- MY EDITED SOLUTION :- link

  • Vote: I like it
  • -12
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

The following is a C++14 map-based solution that was accepted for the SPOJ problem. Suppose that the tasks are enumerated as 1, 2, ..., n. The elapsed time for any task with processing time equal to 1 second is equal to the task number, as its requested execution time is completed in the first iteration. A pending task map is used to store all pending tasks whose processing time is greater than 1 second, where the key is equal to the processing time, and the value associated with such key is a sorted vector of the pending task number whose processing time is equal to that key. The pending task numbers are also stored in a sorted vector. Iterating through the map, the elapsed time of each pending task is recorded according to the order of such task in the present pending tasks. Then, all these pending tasks are removed from the pending tasks vector, and the time as well as the number of elapsed cycles are updated. The number of iterations M to schedule all the pending tasks is equal to the number of distinct processing times larger than 1. Binary search is used to find the order of each pending task, and to remove the pending task from the sorted vector after recording its elapsed time. This is another alternative to using a binary indexed tree.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You code with unpleasant anti-symmetric formatting, so I won't read your code.

Next time, do it properly. Like this...

// This is readable and aesthetic

void function_or_whatever(type parameter...)
{
     // do something here

     return;
}
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i have edited my code , is it fine or should i make some more changes

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The code is more readable now. Your code gives correct output for the tests I tried. Might be some kind of sorcery trick.

      → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I agree with other fellows that it wasn't a pleasant experience to read YOUR SOLUTION, and this may explain to you why I had to solve the problem from scratch. Nonetheless, the following is a MAJOR update to YOUR SOLUTION based on the previous comment.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorry for the inconvenience, could you please point out the test case where my solution fails and also how to correct it .

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 19   Vote: I like it 0 Vote: I do not like it

      Please trace the scheduling loop in solution1() and solution2() functions of the following code using the automatically generated counterexample to find out where exactly your solution produces different elapsed time for some task(s). You may run the same code to find more counterexamples if you wish.

      Note that starting with the set of tasks { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } in the shown counterexample

      10

      6 10 1 7 6 10 1 10 2 1

      the set of pending tasks after the Round-Robin scheduling iterations should be:

      1. After iteration 1: { 1, 2, 4, 5, 6, 8, 9 }, as tasks { 3, 7, 10 } would have just been completed.

      2. After iteration 2: { 1, 2, 4, 5, 6, 8 }, as task { 9 } would have just been completed.

      3. After iteration 6: { 2, 4, 6, 8 }, as tasks { 1, 5 } would have just been completed.

      4. After iteration 7: { 2, 6, 8 }, as task { 4 } would have just been completed.

      5. After iteration 10: { } "an empty set", as tasks { 2, 6, 8 } would have just been completed.

      After iterations 3, 4, 5, 8 and 9, the size of the pending task set should not change, as no tasks have been completed during any of these iterations. Therefore, the following sequence is the size of pending task set after Round-Robin scheduling of this counterexample.

      7, 6, 6, 6, 6, 4, 3, 3, 3, 0

      Note also that in each iteration, the rank of processing some particular task may be decrement if other tasks which precede it have been completed in the previous iteration, and have therefore been removed from the set. For example, the rank of processing task 4 should be:

      1. 4 in iteration { 1 }, the initial rank
      2. 3 in iterations { 2, 3, 4, 5, 6 }, as task 3 has been completed in iteration 1
      3. 2 in iterations { 7 }, as task 1 has been completed in iteration 6

      The rank of each task in the last iteration in which its processing time is completed determines exactly the elapsed time of this task relative to the starting time of such iteration.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanks man i finally got ac in the problem , my mistake was in the call to update function i was not updating index for each of the index where the values were equal , i wonder with such major mistake how does my solution ran till the 9th test case. hey buddy , could you please look into another question which i posted link and again thanks for solving my query.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          With pleasure, decent fellow. And thanks for sharing the good news about your accepted solution.

          RE: the other question

          I have just had a quick look into your blog, and hope to have enough time to read the tutorial as well as the referred comment and source thoroughly before sharing any conclusion.

          → Reply