This is a DP problem on trees and I tried to solve it using the following approach.

Store a DP state DP[current][mode] = min_cost for sub-tree. mode is equal to 0 if the parent of the current node has not bought a family ticket and 1 if it has.

The recurrence is:

if(mode == 0)
DP[current][mode] = min(cost_of_single_ticket + sum of DP[child][0] for all children, cost_of_family_ticket + sum of DP[child][1] for all children)

else

DP[current][mode] = min(sum of DP[child][0] for all children, cost_of_family_ticket + sum of DP[child][1] for all children)

The algorithm seems right but I am getting a wrong answer. Here is my code but it is very long and confusing. If you have already solved the problem could you provide some tricky test cases?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;


public class Main 
{
    private static MyScanner sc;
    private static PrintWriter out;
  
    private static int single_cost;
    private static int family_cost;
    private static HashMap<String, Integer> map;
    private static ArrayList<String>[] Tree;
    private static HashMap<String, Integer> times;
    private static State[][] DP;
    public static void main(String[] args)
    {
        sc = new MyScanner();
        out = new PrintWriter(System.out);
        single_cost = sc.nextInt();
        family_cost = sc.nextInt();
        int counter = 1;
        times = new HashMap();
        map = new HashMap();
        HashMap<String, ArrayList<String>> data = new HashMap();
        int unique_id = 0;
        data = new HashMap();
        boolean flag = false;
        while(!flag)
        {
            if(single_cost == 0 && family_cost == 0) break;
            String k = sc.nextLine();
           
            
            if(k.length() != 0)
            {
            String[] line = k.split("\\s+");
            if(isNumber(line[0]))
            {
                int nu_s = Integer.parseInt(line[0]);
                int nu_f = Integer.parseInt(line[1]);
                if(nu_s == 0 && nu_f == 0)
                {
                    DP = new State[map.size()][2];
                    Tree = new ArrayList[map.size()];
                    for(int i = 0; i < map.size(); i++) Tree[i] = new ArrayList();
                    for(String parent : data.keySet())
                    {
                        Tree[map.get(parent)] = new ArrayList();
                        for(String child : data.get(parent)) Tree[map.get(parent)].add(child);
                    }
                    
                      for(String parent : data.keySet())
                    {
                        //System.out.println("Adding " + parent);
                        times.put(parent, 1);
                      
                    }
                    
                    for(String parent : data.keySet())
                    {
                        for(String child : data.get(parent))
                        {
                            if(times.containsKey(child)) times.put(child, times.get(child) + 1);
                        } 
                        
                    }
                    
                    ArrayList<String> roots = get_root();
                  //  System.out.println(root + " is the root.");
                    
                    int s = 0;
                    int f = 0;
                    int c = 0;
                       
                    for(String root : roots)
                    {
                        State t = solver(root, 0);
                      s += t.single_qty;
                     f += t.family_qty;
                      c += t.cost();
                    }
                      
                      out.println((counter++) + ". " + s + " " + f + " " + c);
                    flag = true;
                }
                else
                {
                     DP = new State[map.size()][2];
                    Tree = new ArrayList[map.size()];
                      for(int i = 0; i < map.size(); i++) Tree[i] = new ArrayList();
                    for(String parent : data.keySet())
                    {
                        Tree[map.get(parent)] = new ArrayList();
                        for(String child : data.get(parent)) Tree[map.get(parent)].add(child);
                    }
                    
                      for(String parent : data.keySet())
                    {
                        //System.out.println("Adding " + parent);
                        times.put(parent, 1);
                      
                    }
                    
                    for(String parent : data.keySet())
                    {
                        for(String child : data.get(parent))
                        {
                            if(times.containsKey(child)) times.put(child, times.get(child) + 1);
                        } 
                        
                    }
                    ArrayList<String> roots = get_root();
                  //  System.out.println(root + " is the root.");
                    
                    int s = 0;
                    int f = 0;
                    int c = 0;
                       
                    for(String root : roots)
                    {
                        State t = solver(root, 0);
                      s += t.single_qty;
                     f += t.family_qty;
                      c += t.cost();
                    }
                      
                      out.println((counter++) + ". " + s + " " + f + " " + c);
                      // new
                    data = new HashMap();
                    times = new HashMap();
                    map = new HashMap();
                    unique_id = 0;
                    single_cost = nu_s;
                    family_cost = nu_f;
                
                }
            
            }
            
            else
            {
                if(!map.containsKey(line[0])) map.put(line[0], unique_id++);
                if(!data.containsKey(line[0])) data.put(line[0], new ArrayList());
                
                for(int i = 1; i < line.length; i++)
                {
                  //  System.out.println("Parent -->" + line[0]);
                    if(!map.containsKey(line[i])) map.put(line[i], unique_id++);
                    data.get(line[0]).add(line[i]);
                  //  System.out.println("Child " + i + " -->" + line[i]);
                    
                }
            
            }
        
        }
        
        }
        
     
       


        out.close();
    }
    
    private static ArrayList<String> get_root()
    {
        ArrayList<String> L = new ArrayList();
        for(String node : times.keySet())
        {
            
            if(times.get(node) == 1) L.add(node);
        }
        return L;    
    }
    
    private static boolean isNumber(String a)
    {
        try
        {
            int k = Integer.parseInt(a);
            return true;
        }
        catch(Exception e) {return false;}
    
    }
    private static State solver(String current, int mode)
    {
     //   System.out.println(current + " --> " + mode);
        if(Tree[map.get(current)].isEmpty())
        {
            if(mode == 0)
            {
                State t = new State();
                t.single_qty += 1;
               // System.out.println("At " + current + " and sending " + t.cost()+" one single qty up mode 0");
                return t;
            }
            
            else 
            {
                
              //  System.out.println("At " + current + " and sending 0 one single qty up mode 1");
                return new State();
            }
        }
        
        else
        {
            if(DP[map.get(current)][mode] != null) return DP[map.get(current)][mode];
            else
            {
                if(mode == 0)
                {
                    State curr_state_one = new State();
                    curr_state_one.single_qty += 1;
                    State t;
                    for(String child : Tree[map.get(current)])
                    {
                        t = solver(child, 0);
                        curr_state_one.single_qty += t.single_qty;
                        curr_state_one.family_qty += t.family_qty;
                    }
                    
                    State curr_state_two = new State();
                    curr_state_two.family_qty += 1;
                    
                    for(String child : Tree[map.get(current)])
                    {
                        t = solver(child, 1);
                        curr_state_two.single_qty += t.single_qty;
                        curr_state_two.family_qty += t.family_qty;
                    
                    }
                    
                    DP[map.get(current)][mode] = curr_state_one.minimum(curr_state_two);
                 //   System.out.println("At " + current + " and sending "+ DP[map.get(current)][mode].cost() +" one single qty up mode 0");
                    return DP[map.get(current)][mode];
                }
                
                else
                {
                    
                     State curr_state_one = new State();
                     State t;
                    for(String child : Tree[map.get(current)])
                    {
                        t = solver(child, 0);
                        curr_state_one.single_qty += t.single_qty;
                        curr_state_one.family_qty += t.family_qty;
                    }
                    
                    State curr_state_two = new State();
                    curr_state_two.family_qty += 1;
                    
                    for(String child : Tree[map.get(current)])
                    {
                        t = solver(child, 1);
                        curr_state_two.single_qty += t.single_qty;
                        curr_state_two.family_qty += t.family_qty;
                    
                    }
                    
                    DP[map.get(current)][mode] = curr_state_one.minimum(curr_state_two);
                    
                  //  System.out.println("At " + current + " and sending "+ DP[map.get(current)][mode].cost() +" one single qty up mode 1");
                    return DP[map.get(current)][mode];
                
                
                }
                
            
            }
        
        }
    
    }
    private static int max(int a, int b)
    {
        if(a > b) return a;
        else return b;
    }

    private static int min(int a, int b)
    {
        if(a < b) return a;
        else return b;

    }
    
    private static class State
    {
        public int single_qty;
        public int family_qty;
        
        public State()
        {
            single_qty = 0;
            family_qty = 0;
        }
        
        public int cost()
        {
            return (single_qty * single_cost) + (family_qty * family_cost); 
        }
        
        public State minimum(State t)
        {
            if(this.cost() < t.cost()) return this;
            else return t;
        }
        
        public void data_out(int index)
        {
            out.println(index + ". " + this.single_qty + " " + this.family_qty + " " + this.cost());
        }
    }
 public static class MyScanner 
    {
      BufferedReader br;
      StringTokenizer st;
 
      public MyScanner() 
      {
         br = new BufferedReader(new InputStreamReader(System.in));
      }
 
      String next() 
      {
          while (st == null || !st.hasMoreElements()) 
          {
              try 
              {
                  st = new StringTokenizer(br.readLine());
              } catch (IOException e) 
              {
                  e.printStackTrace();
              }
          }
          return st.nextToken();
      }
 
      int nextInt() 
      {
          return Integer.parseInt(next());
      }
 
      long nextLong() 
      {
          return Long.parseLong(next());
      }
 
      double nextDouble() 
      {
          return Double.parseDouble(next());
      }
 
      String nextLine()
      {
          String str = "";
	  try 
          {
	     str = br.readLine();
	  } catch (IOException e) 
          {
	     e.printStackTrace();
	  }
	  return str;
      }

   }
}

Is there any library or well written code for exponentiation of a matrix A to a power b, that is finding A^b efficiently that I can refer to (in Java)?

I am trying to solve this problem on SPOJ using a Trie. However, my code does not pass the time limit. This seems to be a reasonable approach for the given limits as other people seem to have used the same approach and passed the tests. I think that my Trie implementation in Java might be too slow. Could someone help me out by checking it and suggesting improvements or providing their own implementation? (in Java)

Here is my approach: There are two classes, one is Node and the other is Trie.

The Node class has two elements, Node[] arr and a boolean isLeaf.

In this problem, we need to check if any number is a prefix of another so while inserting numbers, I simply check if I am passing any node that is a leaf or if after inserting a word, the chain ends and there is no further branching from this Node.

Here is my code:

private static class Node
    {
        public boolean isLeaf;
        public Node[] arr;
        public Node()
        {
            isLeaf = false;
            arr = new Node[10];
        }
     
    }
    
    private static class Trie
    {
        public Node head;
        
        public Trie(String number)
        {
            head = new Node();
            insert(head, number, 0);
        }
       
        public boolean insert(String number)
        {
            return insert(head, number, 0);
        
        }
        
        private boolean insert(Node curr_node, String number, int curr)
        {
            int displacement = (int) number.charAt(curr) - 48;
         
            if(curr == number.length() - 1)
            {
                if(curr_node.arr[displacement] == null)
                {
                    curr_node.arr[displacement] = new Node();
                    curr_node.arr[displacement].isLeaf = true;
                    return true;
                
                }
                
                else return false;
            }
            
            else
            {
                if(curr_node.arr[displacement] == null)
                {
                    curr_node.arr[displacement] = new Node();
                    return insert(curr_node.arr[displacement], number, curr + 1);
                
                }
                
                else
                {
                    if(curr_node.arr[displacement].isLeaf) return false;
                    else return insert(curr_node.arr[displacement], number, curr + 1);
                 }
            
            
            
            }
            
          
            
        }
    
    
    }

Here is the problem.

Here's my solution for this problem -- Football. It involves printing stuff to the screen and I don't know why its failing the time limit.

I am trying to solve this problem called SCUBADIV on SPOJ. I am getting the NZEC error repeatedly. Could someone help me and tell me which part of my code is causing the error?

T = int(raw_input())


class Cylinder(object):
    def __init__(self, a, b, c):
        self.oxygen = a
        self.nitrogen = b
        self.weight = c
        
    def get_ox(self): return self.oxygen
    def get_nit(self): return self.nitrogen
    def get_weight(self): return self.weight


def solver(cylinders, pos, oxygen, nitrogen, map):
    if pos == len(cylinders) - 1:
        if oxygen - cylinders[pos].get_ox() <= 0 and nitrogen - cylinders[pos].get_nit() <= 0: return cylinders[pos].get_weight()
        else: return float('inf')
        
    else:
        if (pos, oxygen, nitrogen) in map: return map[(pos, oxygen, nitrogen)]
        else:
            #don't take the item
            b = solver(cylinders, pos + 1, oxygen, nitrogen, map)
            #take the item
            if oxygen - cylinders[pos].get_ox() <= 0 and nitrogen - cylinders[pos].get_nit() <= 0: a = cylinders[pos].get_weight()
            else: a = cylinders[pos].get_weight() + solver(cylinders, pos + 1, oxygen - cylinders[pos].get_ox(), nitrogen - cylinders[pos].get_nit(), map)
            map[(pos, oxygen, nitrogen)] = min(a, b)
            return min(a, b)
 
for i in range(T):
    t = raw_input().split()
    o, n = int(t[0]), int(t[1])
    k = int(raw_input())
    cylinders = []
    for j in range(k):
        inp = raw_input().split()
        t, a, w = int(inp[0]), int(inp[1]), int(inp[2])
        cylinders.append(Cylinder(t, a, w))
    print solver(cylinders, 0, o, n, {})
    
    

This is my solution to this problem Restore Graph. I have used an approach which seems similar to that suggested in the editorial (which I translated from Russian) but I can't really understand it. Here's what I have done

1) Created a HashMap that maps distances from roots to nodes. For example, if I put in map[1], it will give me a list of nodes that are at distance 1 from the root.

2) Start from the root vertex for which D[start] = 0. I do a DFS search from the root. For each node, which is at distance dist, I check for neighbours that are at distance dist + 1 and visit only k of them if not already visited. Each time I visit another node, I add (current_node, neighbour) to the answer set.

3) That's about it. At the end, I check if the size of the visited map is not equal to n, then output -1. Otherwise I output the answers.

I am getting TLE on the 7th test case which has a considerable input size and I am using Java 8. Is my algorithm too slow or is it because of the language?

Thanks!

My submission

That is my submission for problem http://codeforces.net/problemset/problem/430/C

My program seems to handle previous inputs of equal size, what might be the problem?