idonthatephy's blog

Can anyone tell me what's wrong with my approach for this problem
By idonthatephy, history, 2 years ago, In English

1578E - Easy Scheduling--this is the problem

here is my code. basically wont the total time be-- for i =0 to h-1 summation of ceil(2^i/p) is this observation wrong? For some reason the link is'nt working , so here is the code-

#include <bits/stdc++.h>
#define ll long long int
#define endl "\n"
 

using namespace std;
 
int main(){
 ios_base::sync_with_stdio(false);
    cin.tie(NULL);
int t;
cin>>t;
while(t--){
    double h,p;
    cin>>h>>p;
    ll pow=1;
    ll time=0;
    
    for(int i=0;i<h;i++){
       
        time+=ceil(pow/p);
        
        pow*=2;
        
    }
    cout<<time<<endl;
}
return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

On the input

1
6 3

Your code produces 24 but the answer is 22.

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

    I know that it produces the wrong output for some input, i just wanted to know whats wrong with my logic?

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

      Do the case by hand. Your code also fails on 4 3 which should be easier.

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

        What is the output for 4 3? is it 7?

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          ← Rev. 3   Vote: I like it -10 Vote: I do not like it

          Your code is wrong because it fails to recognize the fact that there can be ready tasks in different levels. One example is you have a height of 4 with 3 processors, your code calculates ceil(1/3) + ceil(2/3) + ceil(4/3) + ceil(8/3) which gives 7 in total. However, your code goes wrong in the third level when there are four nodes. after one moment, there will be one ready node in level 3 left, however, there will also be 6 ready nodes on level four (the children of the three ready tasks that were performed in the previous moment). So here, only one processor will be working while the others aren't doing anything when they in fact could be. This is why you are receiving higher answers than the correct. Instead, you should increment time while the number of tasks in one level is smaller than the number of processors you have. Then calculate the amount of uncompleted tasks afterwards (which is a simple geometric sum) and then calculate ceil(uncompletedTasks/processors). Then add this value to time. This is my code: Note: it does give TLE but it gives correct answers

          #include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int t, h, p, total, count, moments, left;
    cin >> t;
    while (t--)
    {
        cin >> h >> p;
        total = 1;
        count = 1;
        moments = 0;
        while (count <= h && total <= p)
        {
            count++;
            moments++;
            total*=2;
        }
        left = pow(2, h) - pow(2, count-1);
        moments += ceil(left/(float)p);
        cout << moments << endl;
    }
}
          → Reply