JOIN
Get Time

   Problem Statement  

 Problem Statement for ShoutterDiv1

Problem Statement

    

A group of freshman rabbits has recently joined the Eel club. No two of the rabbits knew each other. Yesterday, each of the rabbits went to the club for the first time. For each i, rabbit number i entered the club at the time s[i] and left the club at the time t[i].

Each pair of rabbits that was in the club at the same time got to know each other, and they became friends on the social network service Shoutter. This is also the case for rabbits who just met for a single moment (i.e., one of them entered the club exactly at the time when the other one was leaving).

In Shoutter, each user can post a short message at any time. The message can be read by the user's friends. The friends can also repost the message, making it visible to their friends that are not friends with the original poster. In turn, those friends can then repost the message again, and so on. Each message can be reposted in this way arbitrarily many times. If a rabbit wants to repost multiple messages, he must repost each of them separately.

Today, each of the rabbits posted a self-introduction to Shoutter. Each rabbit would now like to read the self-introductions of all other rabbits (including those that are currently not his friends). Compute and return the minimal number of reposts necessary to reach this goal. If it is impossible to reach the goal, return -1 instead.

As the number of rabbits can be greater than what the TopCoder arena supports, you are given the times s[i] and t[i] encoded in the following form: You are given String[]s s1000, s100, s10, and s1. Concatenate all elements of s1000 to obtain a string S1000. In the same way obtain the strings S100, S10, and S1. Character i of each of these strings corresponds to the rabbit number i. More precisely, these characters are the digits of s[i]: we obtain s[i] by converting the string S1000[i]+S100[i]+S10[i]+S1[i] to an integer. For example, if S1000[4]='0', S100[4]='1', S10[4]='4', and S1[4]='7', then s[4]=to_integer("0147")=147. You are also given String[]s t1000, t100, t10, and t1. These encode the times t[i] in the same way.

 

Definition

    
Class:ShoutterDiv1
Method:count
Parameters:String[], String[], String[], String[], String[], String[], String[], String[]
Returns:int
Method signature:int count(String[] s1000, String[] s100, String[] s10, String[] s1, String[] t1000, String[] t100, String[] t10, String[] t1)
(be sure your method is public)
    
 

Constraints

-s1000, s100, s10, s1, t1000, t100, t10 and t1 will each contain between 1 and 50 elements, inclusive.
-s1000, s100, s10, s1, t1000, t100, t10 and t1 will contain the same number of elements.
-Each element of s1000, s100, s10, s1, t1000, t100, t10 and t1 will contain between 1 and 50 characters, inclusive.
-For each i, the i-th elements of all input variables will all contain the same number of characters.
-Each character in the input variables will be a digit ('0'-'9').
-For each i, t[i] will be greater than or equal to s[i].
 

Examples

0)
    
{"22", "2"}
{"00", "0"}
{"11", "1"}
{"21", "4"}
{"22", "2"}
{"00", "0"}
{"11", "1"}
{"43", "6"}
Returns: 2
After parsing the input, you will get the following information: Rabbit 0 will enter the room at 2012 and leave the room at 2014. Rabbit 1 will enter the room at 2011 and leave the room at 2013. Rabbit 2 will enter the room at 2014 and leave the room at 2016. Therefore, Rabbit 0 and Rabbit 1 will be friends, and Rabbit 0 and Rabbit 2 will be friends too, but Rabbit 1 and Rabbit 2 won't be friends.



Rabbit 0 can already see the self-introductions of all rabbits, but rabbits 1 and 2 cannot see each other's self-introduction. Two actions are needed: First, Rabbit 0 reposts the self-introduction of Rabbit 1, and then Rabbit 0 reposts the self-introduction of Rabbit 2. Now everybody can read everything.
1)
    
{"00"}
{"00"}
{"00"}
{"13"}
{"00"}
{"00"}
{"00"}
{"24"}
Returns: -1
If it is impossible to achieve the goal, return -1.
2)
    
{"0000"}
{"0000"}
{"0000"}
{"1234"}
{"0000"}
{"0000"}
{"0000"}
{"2345"}
Returns: 6
The following pairs will be friends: Rabbit 0 and 1, 1 and 2, and 2 and 3. One of the optimal strategies is as follows:
  • Rabbit 1 shares introductions of Rabbit 0 and 2.
  • Rabbit 2 shares introductions of Rabbit 1 and 3.
  • Rabbit 1 shares introduction of Rabbit 3 (this is possible because now Rabbit 3's introduction is shared by Rabbit 2, who is a Rabbit 1's friend).
  • Rabbit 2 shares introduction of Rabbit 0 (this is possible because now Rabbit 0's introduction is shared by Rabbit 1, who is a Rabbit 2's friend).
3)
    
{"0000000000"}
{"0000000000"}
{"0000000000"}
{"7626463146"}
{"0000000000"}
{"0000000000"}
{"0000000000"}
{"9927686479"}
Returns: 18
4)
    
{"00000000000000000000000000000000000000000000000000"}
{"00000000000000000000000000000000000000000000000000"}
{"50353624751857130208544645495168271486083954769538"}
{"85748487990028258641117783760944852941545064635928"}
{"00000000000000000000000000000000000000000000000000"}
{"00000000000000000000000000000000000000000000000000"}
{"61465744851859252308555855596388482696094965779649"}
{"37620749792666153778227385275518278477865684777411"}
Returns: 333

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 580 Round 1 - Division I, Level Two