[Community Puzzle] Simple Load Balancing

Puzzles
#1

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

Created by @BleedingWithin,validated by @Sasso_Stark and @FredericLocquet.
If you have any issues, feel free to ping them.

#2

Hello, how can I more optimize my code to succed last test pls ?

I’m in c# and I used several function with list like .min and .InstanceOf to find the min more faster but it’s not enough
I can show my code if you want.

#3

Guess i am a bit late.

However, if you tried a solution searching for the min in the vector and adding +1 to it, it will run k times, k being the number of tasks to distribute, and this number can be very high.

Maybe some tricks could help your solution work for big k tests, but i suggest to you to find “shortcuts” in the task distribution to avoid doing k runs of your code :slight_smile:

#4

Aaargh! What is Validator 4? :rofl: I think I have a pretty good load balancing algorithm, and I pass all testcases, but I can’t get past Validator 4. Any hints?

#5

Sorry, we can’t give out validators like this :slight_smile:
Maybe tell us what are the steps of your algorithm and we will try to help.

P.S.: i suspect a timeout in your solution, because validator 4 has the highest number of servers

1 Like
#6

I created script in python3. In IDE validator 4 did not pass. I gave up to provide better solution and decided to submit code. Then, it turned out all tests passed and I got 100%.

My solution makes use of dictionary holding information how many executors runs 0, 1 … num of jobs. So, in first scenario I create dictionary {0: 1, 1: 1, 2: 1, 3: 0, 4:0, 5:1}.
I do not do any sorting, just O(1) dictionary operations and additions.

#7

After realizing, I can’t just run it k times it really became a challenge.
I figured it out though. (The only one in GoLang, that has shared the code so far :rofl:)

I basically did, what you would do, if you would run those kind of tasks by hand.
Only had to sort the vector once at the beginning and turned the number of loops down to around .02k in the final Test.

Thank you to the creators.

1 Like
#8

Hi, I wonder whether this puzzle or your solution is related to binary search. I think the right time complexity is O(N log K) or something.

#9

I solved this with binary search with time complexity of O(N log K). I do not do sorting too.

General steps:

  1. Find min_load with binary search by checking whether K is enough ( Consider if every server holds jobs more than min_load, do you really have that much jobs to distribute ? ). Search range is set to [0, K].
  2. Distribute them in such a way that every server holds jobs more than min_load. and find the max_load.
  3. Print max_load - min_load.

This figure may be helpful when implementing the binary search.

662Ă—589 33.7 KB