Delete Them Softly

[huimeich]

You have a list, aa, containing nn elements. You must choose all elements of the list in some order. Selections should be made according to the following rules:

At each step, you must choose element xx that was not chosen in the one of previous steps and perform ax←0ax←0. Your score for this step is ∑x−1i=1ai∑i=1x−1ai points (it might be negative). There are some dependencies between elements. Dependencies are pairs of two elements (α,β)(α,β) such that α≠βα≠β. If there is an active dependency (α,β)(α,β), you can not choose element ββ. After each step, all dependencies (α,β)(α,β) such that min{α,β}≤x≤max{α,β}min{α,β}≤x≤max{α,β} become inactive. Initially, all dependencies are active. Given a set of mm dependencies, find the order of removing all elements from the list using the above rules such that your score is as large as possible. Your score is the sum of the points for each step.

Input Format

The first line contains a single integer, nn, denoting the size of the list. The second line contains nn space-separated integers, a1,…,ana1,…,an, describing the elements of the list. The third line contains a single integer, mm, the number of dependencies. The mm subsequent lines each contain two-space-separated integers, xx and yy, denoting the dependencies.

Note: All the dependencies are distinct.

Constraints

1≤n≤1501≤n≤150 −107≤ai≤107−107≤ai≤107 0≤m≤n⋅(n−1)0≤m≤n⋅(n−1) 1≤x,y≤n1≤x,y≤n; x≠yx≠y Output Format

Print the maximum possible score; if it is not possible to choose all elements of the list according to the rules, print ImpossibleImpossible on a new line.

Sample Input 0

5 -1 1 -1 1 -1 0 Sample Output 0

4 Sample Input 1

5 -1 1 -1 1 -1 3 3 1 5 3 5 1 Sample Output 1

1 Sample Input 2

3 100 100 100 3 1 2 2 3 3 1 Sample Output 2

Impossible
Explanation

Sample Case 0: N=5N=5 list={−1,1,−1,1,−1}list={−1,1,−1,1,−1} m=0m=0 You must take elements in the order {1,3,5,4,2}{1,3,5,4,2}.

Sample Case 1: N=5N=5 list={−1,1,−1,1,−1}list={−1,1,−1,1,−1} m=3m=3 dependencies={3,1},{5,3},{5,1}dependencies={3,1},{5,3},{5,1} You must take elements in the order {5,3,1,4,2}{5,3,1,4,2}.

Sample Case 1: N=3N=3 list={100,100,100}list={100,100,100} m=3m=3 dependencies={1,2},{2,3},{3,1}dependencies={1,2},{2,3},{3,1} You cannot take any element at the first step.

[huimeich]

There are nn cities numbered from 11 to nn, and they are connected by n−1n−1 roads. It's possible to travel between any pair of cities via the road system.

Jessica's work travel regularly requires her to visit some of the cities. To make travel easier, she wants to improve the quality of the roads so that she can travel between any pair of regularly-visited cities using improved roads.

Jessica can make a request to improve all roads on the path between any two cities, and each road can be improved more than once. As Jessica is not quite sure where her work will take her, help her find the minimal number of such requests for all given subsets of cities independently.

Input Format

The first line contains nn, the number of cities. The n−1n−1 subsequent lines each contains 22 space-separated integers, uiui and vivi, describing a road directly connecting the respective cities uiui and vivi. The next line contains the number of subsets, qq. Each of the qq subsequent lines one or more space-separated integers; the first integer is jj, followed by jj integers describing kjkj:

jj: The size of the subset. kjkj: Integers representing cities in the subset.

All cities in the subset are different. Constraints

1≤n≤5×1051≤n≤5×105 1≤ui,vi≤n1≤ui,vi≤n 1≤q≤1061≤q≤106 kjkj 1≤kj≤n1≤kj≤n ∑Kj≤106∑Kj≤106 Output Format

Print qq lines. For each subset, print the minimal number of requests required.

Sample Input

6 1 3 3 2 3 4 4 5 4 6 5 1 1 2 1 6 3 1 3 6 3 1 2 6 4 1 2 5 6 Sample Output

0 1 1 2 2 Explanation

In the first case, there is no need to make requests.

In the second and the third cases, the only possible path is 1−61−6.

In the fourth and the fifth cases, the paths could be 1−61−6 or 2−52−5.

[huimeich]

import java.io.*;
import java.util.*;

public class Solution {

    public static class Node{
        long val;
        double index;
        Node left;
        Node right;
        public Node(long val){
            this.val = val;
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long prev = in.nextInt();
        Node head = new Node(prev);
        head.index = 1.0;
        System.out.print("1");
        for (int i = 1; i < n; i++){
            long curr = in.nextLong();
            Node node = new Node(curr);
            Node prevNode = head;
            while ((prevNode.val < curr && prevNode.right != null) || 
                   (prevNode.val >= curr && prevNode.left != null)) {
                if (prevNode.val < curr && prevNode.right != null) {
                    prevNode = prevNode.right;
                } else {
                    prevNode = prevNode.left;    
                }
            }
            if (prevNode.val >= curr && prevNode.left == null) {
                prevNode.left = node;
                node.index = prevNode.index * 2;
            } else {
                prevNode.right = node;
                node.index = (prevNode.index * 2) + 1;
            }
            System.out.print(" ");
            StringBuffer buf = new StringBuffer("");
            double d = node.index;
            while (d>=1) {
                int current = (int) (d % 10);
                d /= 10;
                d = Math.floor(d);
                buf.append(current);
            }
            System.out.print(buf.reverse().toString());
        }
    }
}

[huimeich]

https://www.hackerrank.com/contests/womens-codesprint/challenges/mars-and-the-binary-search-tree/editorial

Approach 2(Intelligent):

For each position where a new number can be inserted, we can define a range of valid numbers that can be inserted at that poisition. For example, in this BST: 5 / \ 2 8 \ 19 / 10 For left child of 2, the range is (−inf,2)(−inf,2) where (a,b)(a,b) denotes all valid integers in range aa to bb(excluding both aa and bb). Similarly, for right child the range is (2,5)(2,5). For left child of 8, the range is (5,8)(5,8). For right left child of 10, the range is (8,10)(8,10) and for right child the range is (10,19)(10,19). For right child of 19 the range is (19,inf)(19,inf). So, all the ranges are (−inf,2)(−inf,2), (2,5)(2,5), (5,8)(5,8), (8,10)(8,10), (10,19)(10,19), (19,inf)(19,inf). Another interesting observation is that all these ranges are disjoint and the break points of these ranges are the values that already exist in the BST. Now, with these ranges we can also associate the new index a number will have if it's inserted into the tree. So, in this case, the mappings from ranges to indexes will be: inf, 2 : 4 2, 5 : 5 5, 8 : 6 8, 10 : 28 10, 19 : 29 19, inf : 15 Now, let's say you want to insert x=9x=9, in the BST. You know that it occurs in the range (8,10)(8,10) so, index of xx will be 29. Now, this range has been destroyed and two new ranges (8,9)(8,9) and (9,10)(9,10) have been created with indexes 2∗282∗28 and 2∗28+12∗28+1, respectively.

Implementation: How do we actually implement this? We maintain a map from ranges to indexes as shown in example above. Let's say we get a value xx, how do we find the range in which it lies. Since break points of ranges are the values already existing in the BST and all ranges are disjoint, the range of xx is (x1,x2)(x1,x2), where x1x1 is the largest number smaller than xx in the BST and x2x2 is the smallest number larger than xx in the BST. These two values can be easily found via a set in C++. Now, we search for the range in the map, print the answer for xx and remove the existing range and update two new ranges in the map.

Overall complexity is O(NlogN)O(NlogN). Set by darkshadows

#include<bits/stdc++.h>
#define assn(n,a,b) assert(n<=b && n>=a)
using namespace std;
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,b) for(i=0;i<b;i++)
#define rep1(i,b) for(i=1;i<=b;i++)
#define pdn(n) printf("%d\n",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%d",&n)
#define pn printf("\n")
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define MOD 1000000007ll
LL mpow(LL a, LL n) 
{LL ret=1;LL b=a;while(n) {if(n&1) 
    ret=(ret*b)%MOD;b=(b*b)%MOD;n>>=1;}
return (LL)ret;}
int main()
{
    //map of ranges
    map <pair<int,int> , LL > mymap;
    map <pair<int,int> , LL >::iterator itt;

    //set of values inserted into BST
    set<int> myset;
    set<int> myn;
    set<int>::iterator it;

    int n;

    //define range for root
    mymap[mp(INT_MIN,INT_MAX)]=1;

    //scan n
    sd(n);
    assert(n>=1&&n<=300000);
    for(int i=0; i<n; i++){
        int x,l,r;
        //scan A_i
        sd(x);
        assert(x>=1&&x<=1000000000);
        //find the range in which it lies ie. (x1, x2)
        myset.insert(x);
        it=myset.find(x);
        if(it==myset.begin())l=INT_MIN;
        else{
            it--;
            l=*it;
            it++;
        }
        it++;
        if(it==myset.end())r=INT_MAX;
        else r=*it;

        //search for the range in map
        itt=mymap.find(mp(l,r));
        assert(itt!=mymap.end());

        //insert two new ranges into the map
        mymap[mp(l,x)]=(2ll*itt->S)%MOD;
        mymap[mp(x,r)]=(2ll*itt->S+1ll)%MOD;

        //output answer
        cout << itt->S;
        if(i!=n-1)cout << " ";
        else cout << endl;

        //erase existing range from the map
        mymap.erase(itt);
    }
    return 0;
}

[huimeich]

Wrong:

import java.io.*;
import java.util.*;

public class Solution {

    public static class Range implements Comparator<Range>, Comparable<Range>{
        double index;
        int left;
        int right;
        public Range() {
            left = Integer.MIN_VALUE;
            right = Integer.MAX_VALUE;
            index = 1;
        }
        public Range(int left, int right){
            this.left = left;
            this.right = right;
        }
        public void moveIndexLeft(Range parent) {
            this.index = parent.index*2;
        }
        public void moveIndexRight(Range parent) {
            this.index = parent.index*2+1;
        }
        public void printIndex() {
            StringBuffer buf = new StringBuffer("");
            double d = this.index;
            while (d>=1) {
                int current = (int) (d % 10);
                d /= 10;
                d = Math.floor(d);
                buf.append(current);
            }
            System.out.print(buf.reverse().toString());
        }

        public int compareTo(Range other){
          return compare(this, other);
        }

    @Override
        public int compare(Range r1, Range r2){
          if (r1.left >= r2.right) return 1;
          if (r1.right <= r2.left) return -1;
          return 0; 
        }
    }
    public static void main(String[] args) {

        Range range = new Range();
        TreeSet<Range> setRange = new TreeSet<Range>();
        setRange.add(range);

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int n_i = 0; n_i < n; n_i++){
            int val = in.nextInt();
            range = new Range(val,val);
            Range oldRange = setRange.ceiling(range);

            setRange.remove(oldRange);
            if (n_i > 0) {
                System.out.print(" ");
            }
            oldRange.printIndex();
            Range rangeLeft = new Range(oldRange.left, val);
            rangeLeft.moveIndexLeft(oldRange);
            Range rangeRight = new Range(val, oldRange.right);
            rangeRight.moveIndexRight(oldRange);
            setRange.add(rangeLeft);
            setRange.add(rangeRight);
        }
    }
}