SHOW:
|
|
- or go back to the newest paste.
1 | // Author : Saurav Kalsoor | |
2 | - | // K Unique String - JAVA |
2 | + | // Count Coins - KOTLIN |
3 | ||
4 | import java.util.*; | |
5 | ||
6 | - | public class Test { |
6 | + | var sc = Scanner(System.`in`) |
7 | - | static Scanner sc = new Scanner(System.in); |
7 | + | |
8 | - | public static void main(String[] args) { |
8 | + | class Edge(var u: Int, var v: Int) |
9 | - | String s = sc.next(); |
9 | + | |
10 | - | int k = sc.nextInt(); |
10 | + | fun main() { |
11 | val n = sc.nextInt() | |
12 | - | System.out.println(kUniqueString(s, k)); |
12 | + | val m = sc.nextInt() |
13 | val coins = ArrayList<Int>() | |
14 | for (i in 0 until n) { | |
15 | - | public static int kUniqueString(String s, int k) { |
15 | + | coins.add(sc.nextInt()) |
16 | - | HashMap<Character, Integer> freq = new HashMap<>(); |
16 | + | |
17 | val arr: ArrayList<Edge> = ArrayList<Edge>() | |
18 | - | for(int i = 0; i < s.length(); i++){ |
18 | + | for (i in 0 until m) { |
19 | - | freq.put(s.charAt(i), freq.getOrDefault(s.charAt(i), 0) + 1); |
19 | + | val u = sc.nextInt() |
20 | - | } |
20 | + | val v = sc.nextInt() |
21 | arr.add(Edge(u, v)) | |
22 | - | Set<MyPair> st = new TreeSet<>(new Comparator<MyPair>() { |
22 | + | |
23 | - | @Override |
23 | + | println(coinsCount(arr, coins, n)) |
24 | - | public int compare(MyPair a, MyPair b) { |
24 | + | |
25 | - | if(a.frequency == b.frequency) |
25 | + | |
26 | - | return a.ch - b.ch; |
26 | + | fun coinsCount(arr: ArrayList<Edge>, coins: ArrayList<Int>, n: Int): Int { |
27 | - | return a.frequency - b.frequency; |
27 | + | val tree = ArrayList<ArrayList<Int>>() |
28 | - | } |
28 | + | for (i in 0 until n) tree.add(ArrayList()) |
29 | - | }); |
29 | + | for (e in arr) { |
30 | tree[e.u].add(e.v) | |
31 | - | for(Map.Entry<Character, Integer> x : freq.entrySet()){ |
31 | + | tree[e.v].add(e.u) |
32 | - | st.add(new MyPair(x.getKey(), x.getValue()) ); |
32 | + | |
33 | - | } |
33 | + | val mp = HashMap<Int, Int>() |
34 | return uniqueCount(tree, mp, coins, 0, -1) | |
35 | - | int distinct = freq.size(), changes = 0; |
35 | + | |
36 | ||
37 | - | for(MyPair x : st){ |
37 | + | fun uniqueCount( |
38 | - | if(distinct <= k) |
38 | + | tree: ArrayList<ArrayList<Int>>, |
39 | - | break; |
39 | + | mp: HashMap<Int, Int>, |
40 | coins: ArrayList<Int>, | |
41 | - | changes += x.frequency; |
41 | + | node: Int, |
42 | - | distinct--; |
42 | + | parent: Int |
43 | - | } |
43 | + | ): Int { |
44 | var res = 0 | |
45 | - | return changes; |
45 | + | mp[coins[node]] = mp.getOrDefault(coins[node], 0) + 1 |
46 | for (child in tree[node]) { | |
47 | - | |
47 | + | if (child == parent) continue |
48 | res = Math.max(res, uniqueCount(tree, mp, coins, child, node)) | |
49 | } | |
50 | - | class MyPair{ |
50 | + | res = Math.max(res, mp.size) |
51 | - | public char ch; |
51 | + | mp[coins[node]] = mp[coins[node]]!! - 1 |
52 | - | public int frequency; |
52 | + | if (mp[coins[node]] == 0) mp.remove(coins[node]) |
53 | return res | |
54 | - | public MyPair(char ch, int frequency){ |
54 | + | |
55 | - | this.ch = ch; |
55 | + |