You are not logged in. Please login at www.codechef.com to post your questions!

×

HackerEarth Problem- Little Deepu and Array

Problem:

An Array of positive elements. Deepu Wants to reduce the elements of the array. He calls a function Hit(X) which reduces the all the elements in the array which are greater than X by 1.

he will call this array many times . Print the array after many calls to Hit(X).

Input:

n----- no of elements in array 10^5.

n elements ----- 1<=element<=10^9.

x----- no of calls to Hit(X) x elements----- 1<=element<=10^9.

output:

Print The array after call to Hit(X) x times.

Time limit--5 secs.

My solution gave Time Limit Exceeded.

My approach:

  1. keep an Original Array
  2. Create a vector of pairs of array elements and their index in the array
  3. Sort the vector elements [ ascending ]
  4. Do LowerBound() of C++ STL to get the position of element in the vector where elements are equal to give element.
  5. From this element decrease the elements which are greater than x by 1 till end in the original array from the index in the pair.
  6. Repeat step 4 & 5 for every x.
  7. Print the Original array.

I think my solution has complexity n^2.

Can someone Give me an Optimized solution

Thanks

My Code

asked 22 Dec '14, 14:57

bajaj6's gravatar image

2★bajaj6
39135
accept rate: 0%

edited 22 Dec '14, 15:14


Why are you doing so much,its a simple problem,just traverse the array whenever Hit(X) is called and if greater than X,update the value by decrementing it by 1.The time complexity turns out to be O(noofshots*sizeofarray) Here's my code:

include <bits stdc++.h="">

using namespace std;

define ll long long

int main() { ll n; cin>>n; vector<ll> v(n); for(int i=0;i<n;i++) cin="">>v[i]; ll shot; cin>>shot; while(shot--) { ll val; cin>>val; for(int i=0;i<n;i++) {="" if(v[i]="">val) v[i]--; } } for(int i=0;i<n;i++) {="" cout&lt;<v[i]&lt;&lt;"="" ";="" }="" return="" 0;="" }<="" p="">

link

answered 11 Aug '16, 14:16

pada1211's gravatar image

1★pada1211
1
accept rate: 0%

Why are you doing so much,its a simple problem,just traverse the array whenever Hit(X) is called and if greater than X,update the value by decrementing it by 1.The time complexity turns out to be O(no_of_shots*size_of_array) Here's my code:

include <bits stdc++.h="">

using namespace std;

define ll long long

int main() { ll n; cin>>n; vector<ll> v(n); for(int i=0;i<n;i++) cin="">>v[i]; ll shot; cin>>shot; while(shot--) { ll val; cin>>val; for(int i=0;i<n;i++) {="" if(v[i]="">val) v[i]--; } } for(int i=0;i<n;i++) { cout<<v[i]<<" "; } return 0; }

link

answered 11 Aug '16, 14:16

pada1211's gravatar image

1★pada1211
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,600
×1,299
×234

question asked: 22 Dec '14, 14:57

question was seen: 2,869 times

last updated: 11 Aug '16, 14:16