jerseyguy's blog

Needed some hints to this problem
By jerseyguy, history, 5 years ago, In English

Can somebody give some hints? problem name : students council ( from cf edu section)

Regards.

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
  • First of all if we need to build x councils each consists of k students, then from each group we can take atmost x students. So in the end if we get more than (x*k) students from the group we can build x coucils.

*In this problem we need to maximize the number of councils we need to search for that maximum value of x that satifies the given condition.

*In the worst case the total councils may be 0 and in the best case total councils may be (sum of students/k), so we need to search the maximum value between these two numbers.

*the trend its shows will be T,T,T,F,F,F.. we need to find the last true. so I applied binary search and it got accepted.

//sorry for my bad english

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

    how are you checking if x councils are possible or not

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

      To check if it is possible to create x councils, each consists of k students. lets take all possible students from each group I can take maximum of x students at the end if I get >= (x*k) students then x councils can be created.

      bool is(int x,vector &arr,int k) { int sum=0; //to track of maximum students I can take to create x councils

      for(int i=0;i<arr.size();i++) { sum+=min(x,arr[i]);//I can take maximum of x students from each group }

      if(sum>=(x*k)) return true;

      else return false; }

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

You can note that if you can form K > 1 councils, then you can form K — 1. So binary search will help.

possible(m) tell us if is possible to form at least m councils.

To construct possible(m) here is a hint:

sort groups by size, then find out if you can apply a greedy algorithm.

→ Reply