CHOC - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice

Contest

Author: Ranjan Kumar Singh

Tester: Sudipto Roy

Editorialist: Ved Prakash

DIFFICULTY:

EASY

PROBLEM:

Chef is distributing his u varieties of chocolates among N students in a line.

He ditributes kp amount of chocolate of variety up to the students from position i to j.

Now after distribution of chocolates, we have m queries to calculate the no. of choclates to student at position mi.

EXPLANATION:

We need to update the no. of chocolate to student at position i by clever means.

Let the u updatation steps be like:

The no. of chocolate

at starting position as choc[i]=choc[i]+k and

at ending position as choc[j+1]=choc[j+1]-k

After this, to get the number of chocolate at position i, update the array choc[i] as summation of all choc[a] (0<=a<=i)

Pseudo Code:


        for a=0 to N
        choc[a]=0;               //initialisation//
        for a=0 to u
        {
         scan i,j,k
         choc[i]=choc[i]+k;      //updatation at starting position//
         choc[j+1]=choc[j+1]-k;  //updatation at end position//
        }
        for a=0 to N
        {
            sum=sum+choc[a];                
            number_of_chocolate_at[a]=sum;  //final updation for the number of chocolate at position i//
        }

Complexity: O(u+N+m).

SOLUTIONS:

Setter’s solution

Tester’s solution

1 Like
2

saya sedang mencari Voucher Diskon dan belajar Toko Olahraga Online Murah, Lengkap, Aman dan Terpercaya di Franchise Minuman Coklat, Waralaba Minuman, Nyoklat, Nyoklat Super bersama Nissan X-Trail, Mobil SUV Paling Tangguh Dan Nyaman namun akhirnya ketemu all new nissan x trail 2016 Mobil SUV Paling Tangguh Dan Nyaman yang mana ia Info Perumahan