Minimum Loss
Problem Statement :
Lauren has a chart of distinct projected prices for a house over the next several years. She must buy the house in one year and sell it in another, and she must do so at a loss. She wants to minimize her financial loss. Function Description Complete the minimumLoss function in the editor below. minimumLoss has the following parameter(s): int price[n]: home prices at each year Returns int: the minimum loss possible Input Format The first line contains an integer n, the number of years of house data. The second line contains n space-separated long integers that describe each price[i].
Solution :
Solution in C :
In C++ :
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define REPD(i,a,b) for (int i = (a); i >= (b); --i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define SZ(x) int((x).size())
#define DBG(v) cerr << #v << " = " << (v) << endl;
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define fi first
#define se second
int n;
ll a[200200];
int main() {
scanf("%d", &n);
FOR(i,n) scanf("%lld", &a[i]);
set<ll> s;
long long res = 1000000000000000000LL;
FOR(i,n) {
auto it = s.lower_bound(a[i]);
if (it != s.end()) {
res = min(res, *it-a[i]);
}
s.insert(a[i]);
}
printf("%lld\n", res);
return 0;
}
In Java :
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner input=new Scanner(System.in);
int n=input.nextInt();
ArrayList<Long> p=new ArrayList();
for(int i=1;i<=n;i++)
p.add(input.nextLong());
long minLoss=Integer.MAX_VALUE;
ArrayList<Long> p2=(ArrayList<Long>)p.clone();
Collections.sort(p2);
for(int i=n-1;i>0;i--){
long a=p2.get(i);
long b=p2.get(i-1);
if(a-b<minLoss && p.indexOf(a)<p.indexOf(b))
minLoss=a-b;
}
System.out.println(minLoss);
}
}
In C :
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef long long ll;
typedef struct treap {
ll v;
int p;
struct treap *l, *r;
}* Treap;
Treap newNode(ll v) {
Treap t = (Treap) malloc (sizeof (struct treap));
t->v = v;
t->p = (rand() << 15) | rand();
t->l = t->r = NULL;
return t;
}
Treap merge(Treap l, Treap r) {
if (!l)
return r;
if (!r)
return l;
if (l->p > r->p) {
l->r = merge(l->r, r);
return l;
}
r->l = merge(l, r->l);
return r;
}
void split(Treap root, Treap *l, Treap *r, ll v) {
if (!root) {
*l = *r = NULL;
return;
}
if (root->v <= v) {
split(root->r, &(root->r), r, v);
*l = root;
}
else {
split(root->l, l, &(root->l), v);
*r = root;
}
}
Treap first(Treap root) {
while (root->l)
root = root->l;
return root;
}
Treap last(Treap root) {
while (root->r)
root = root->r;
return root;
}
int main() {
srand(time(NULL));
int n;
ll mx = 0, mn = 1000000000000000000LL, p;
Treap root = NULL, t, l, r;
scanf("%d", &n);
while (n--) {
scanf("%lld", &p);
if (p < mx) {
split(root, &l, &r, p);
t = first(r);
if ((t->v - p) < mn)
mn = t->v - p;
if (!l || last(l)->v != p) {
t = newNode(p);
root = merge(l, t);
root = merge(root, r);
}
}
else if (p > mx) {
mx = p;
t = newNode(p);
root = merge(root, t);
}
}
printf("%lld", mn);
return 0;
}
In Python3 :
n=int(input())
l = [int(item) for item in input().split()]
l2 = l.copy()
d={}
for i in range(len(l)):
d[l[i]] = i
l = sorted(l)
m = float("inf")
for i in range(len(l)-1):
if d[l[i+1]] < d[l[i]] : m = min(m,l[i + 1] - l[i])
print(m)
View More Similar Problems
Pair Sums
Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v
View Solution →Lazy White Falcon
White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi
View Solution →Ticket to Ride
Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o
View Solution →Heavy Light White Falcon
Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim
View Solution →Number Game on a Tree
Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy
View Solution →Heavy Light 2 White Falcon
White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr
View Solution →