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 .
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:
- 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.
- 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.
#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;
}