All posts by tarry

Hackerrank week of code 38

Hackerrank week of code 38

Q.1 Which Section?(https://www.hackerrank.com/contests/w38/challenges/which-section)

The school term starts soon, and the students need to be sorted into their respective sections. There are students numbered  to , and  sections numbered  to .

Section  needs to have exactly  students. To simplify the process, the school has decided to assign students to sections in increasing student number, which means the first  students will be assigned section , the next  students will be assigned section , and so on.

Your student number is . Which section will you be assigned to?

Complete the function whichSection which takes in two integers  and  and an integer array  and returns the section number you will be assigned to, assuming you are student number .

Input Format

The first line of input contains , the number of scenarios.

The description of  scenarios follow, each described in two lines. The first line contains three space-separated integers  and . The second line contains  space-separated integers .

Constraints

Output Format

For each scenario, print a single line containing a single integer denoting the section in which student number  will be assigned to.

Sample Input 0

<span class="err">1</span>
<span class="err">470 143 5</span>
<span class="err">11 24 420 6 9</span>

Sample Output 0

<span class="err">3</span>

Explanation 0

There are  students, and there are  sections with sizes . This means that:

  • Students  to  get assigned section .
  • Students  to  get assigned section .
  • Students  to  get assigned section .
  • Students  to  get assigned section .
  • Students  to  get assigned section .

Since you are student , you get assigned section .

Solution:

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

int binarySearch(vector<long> v,int k, int min , int max)
{
// 11 35 455 461 470
// 143

//1 3 6 10 15
//3

int size = max – min; // 2,5
int mid = min + size/2;
if(min == max )
{
return min +1;

}
if(k <= v[mid] && (mid)==0)
return 1;
if(k <= v[mid] && k > v[mid-1])
return mid +1;
else if(k <= v[mid])
return binarySearch(v,k,min,mid);
else //if(k > v[mid])
return binarySearch(v,k,mid+1,max);

}

// Complete the whichSection function below.
int whichSection(int n, int k, vector<int> a) {
// Return the section number you will be assigned to assuming you are student number k.
vector<long> sumV;
long sum=0;
for(int i=0 ; i < a.size();i++)
{
sum += a[i];
sumV.push_back(sum);
}
//11 24 420 6 9
// 11 35 455 461 470
// 143
return binarySearch(sumV,k,0,a.size()-1) ;
}

Q.2  Minute to Win It (https://www.hackerrank.com/contests/w38/challenges/minute-to-win-it/problem)

In a new version of the game Minute to Win It, the math round involves manipulating arrays to meet the given condition. In the challenge, you are given an array of  numbers  and an integer . In one minute, you can change any element of the array to any integer you want. Find the minimum amount of time you have to spend so that the following condition is satisfied: for all  from  to , .

For example, consider the array  and . Then the condition can be satisfied in  minute by replacing the  with a .

image

Complete the function minuteToWinIt which accepts an array  of  integers and an integer  as input and returns the minimum amount of time in minutes.

Input Format

The first line contains two space-separated integers  and .

The second line contains the array in the form of  space-separated integers .

Constraints

Output Format

Print the minimum number of minutes needed to reorder the array.

Sample Input 0

<span class="err">6 2</span>
<span class="err">1 2 5 7 9 85</span>

Sample Output 0

<span class="err">2</span>

Explanation 0

The given array is . If we change  and  at index  and  respectively, we get the desired array .

Solution:

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

set<int> storedinx ;
int minuteToWintItForEveryDiff(vector<int> a , int k , int diff)
{
//int diff =1;
int countM =0 , maxVal=0 , index=0;
int minutes=0;
int n=a.size();
//1 2 5 7 9 85
int j=0;
// 1 2 1 6
for( j=0 ; j < diff ; j++)
{
int i=0 ;
for( i=j ;i < a.size() -diff ; i =i+diff)
{
if(a[i+diff]- a[i] == k)
countM++;
else
{
if(countM > maxVal)
{
maxVal=countM;
index=i;
}
countM=0;
}
}
if(countM > maxVal)
{
index= i;
maxVal=countM;
}
}
k=k/diff;
//1 2 5 7 9 85
if (storedinx.count(index)) {
return INT_MAX;
} else {
storedinx.insert(index);
for(int i=index ; i < a.size()-1;i++)
{
if(a[i+1]-a[i] !=k)
{
a[i+1]= a[i]+k;
minutes++;
}
}
if(index !=0)
{
for(int i=index-1 ; i >= 0;i–)
{
if(a[i+1]-a[i] !=k)
{
a[i]= a[i+1]-k;
minutes++;
}
}
}
return minutes;
}

}
// Complete the minuteToWinIt function below.
int minuteToWinIt(vector<int> a, int k) {
int minVal=INT_MAX;
int n= a.size();
//int j=1;
for(int i=1 ; i < n/i ; i++ )
{
//1 2 1 6
int value=0;
value= minuteToWintItForEveryDiff(a,k*(i),i);
if(value==0)
return 0;
if(value < minVal)
minVal=value;
}
if(minVal != INT_MAX)
return minVal;
else
return 0;
}

Q.3 A Time-saving Affair(https://www.hackerrank.com/contests/w38/challenges/a-time-saving-affair/problem)

Janet is in an Uber on her way to an interview. The driver promises to take her to the venue as soon as possible. The driver is aware that:

  • There are  junctions in the city of Mumbai, numbered from  to .
  • Janet’s interview location is at junction . They are initially at junction .
  • There are  bidirectional roads connecting some pairs of junctions, each one requiring some amount of time to pass through it.

At every junction, there are traffic lights denoting whether they are allowed to go further or to wait. Traffic lights have two colors,  and . The driver can commute through junctions based on these conditions:

  1. At any junction, if the traffic signal’s light is green, then they can go immediately, otherwise, they have to wait until traffic signal becomes green.
  2. Traffic signal changes its color every  seconds of time at all junctions simultaneously.

Initially, at the  second, all traffic lights have changed to green color at all the junctions. If the cab driver reaches a junction at a second when the traffic light changes its color, then he sees the traffic light after the change.

Can you help the driver determine the least amount of time needed to reach the interview location?

Complete the function leastTimeToInterview which takes in three integers ,  and  and returns the least amount of time needed to reach the interview location, in seconds. You need to take the information about the roads from the standard input. They will be specified in  lines, as described in the input format section below.

Input Format

The first line contains an integer , the number of junctions.

The second line contains an integer  denoting the time taken by a signal to change its color.

The third line contains an integer  denoting the number of roads.

The next  lines describe the roads. Each consist of three space-separated integers ,  and  where  and denotes a road between two junctions and  denotes time required to travel through it.

Constraints

  • There can be self-loops, i.e., roads connecting a junction to itself.
  • There is at least one path from junction  to junction .

Output Format

Print a single integer denoting the shortest amount of time required to reach junction .

Sample Input 0

<span class="err">7</span>
<span class="err">4</span>
<span class="err">7</span>
<span class="err">1 2 3</span>
<span class="err">2 3 1</span>
<span class="err">1 4 4</span>
<span class="err">4 6 7</span>
<span class="err">7 5 2</span>
<span class="err">3 5 1</span>
<span class="err">4 5 5</span>

Sample Output 0

<span class="err">11</span>

Explanation 0

  • Junction number : The cab driver can visit any of the adjacent junctions. He chooses to visit junction . Since the traffic signal is  at the  second, He can visit junction  which takes  seconds.
  • Junction number : The traffic signal is still  since traffic signals change color every  seconds. The cab driver now chooses to visit junction  which takes  second, and we are now at the  second.
  • Junction number :  seconds have passed, and the traffic signal has already become . They have to wait for  more seconds until the signal again becomes .
  • Junction number : The cab takes the route to junction  which takes  second. So far,  seconds have passed.
  • Junction number : The traffic signal is still  and the cab can go to junction . It takes  seconds to reach junction .

In total, it takes  seconds to go from junction  to junction . It can be shown that this is the minimum amount of time possible.

image

Solution:

#include <bits/stdc++.h>
#include <climits>
# define INF INT_MAX
using namespace std;
class Graph
{
int V;
list< pair<int, int> > *adj;

public:
Graph(int V);
void addEdge(int u, int v, int w);

long shortestPath(int s, int k);
};

Graph::Graph(int V)
{
this->V = V;
adj = new list< pair<int, int> >[V];
}

void Graph::addEdge(int u, int v, int w)
{
adj[v].push_back(make_pair(u, w));
adj[u].push_back(make_pair(v, w));
}
long Graph::shortestPath(int src, int k)
{

set< pair<int, int> > setdp;

vector<int> dist(V, INF);
setdp.insert(make_pair(0, src));
dist[src] = 0;

while (!setdp.empty())
{

pair<int, int> tmp = *(setdp.begin());
setdp.erase(setdp.begin());

int u = tmp.second;

list< pair<int, int> >::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{

int v = (*i).first;
int weight = (*i).second;

int new_w = dist[u] + weight;

if( (new_w/k)%2==1 )
{
if(v!=(V-1))
new_w = ((new_w/k)+1)*k;
}

if (dist[v] > new_w)
{

if (dist[v] != INF)
setdp.erase(setdp.find(make_pair(dist[v], v)));

dist[v] = new_w;
setdp.insert(make_pair(dist[v], v));
}
}
}

return dist[V-1];
}

long leastTimeToInterview(int n, int k, int m) {

Graph g(n);
for(int i=1;i<=m;i++)
{
int u,v,t;
cin>>u>>v>>t;
g.addEdge(u-1, v-1, t);
}

return g.shortestPath(0, k);

return 0;
}