JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums News, Programs & Events Discussions 2012 TopCoder Open Wildcard problems
 Wildcard problems | Reply [250]Problem Statement    You are a knight of the Integerland. You are located at (0, 0) and you want to go to (x, y). You move in a way that is similar to a chess knight. You can be described by a int d. In each step, you may move to any point such that both its coordinates are integers, and its Euclidean distance from your current point is precisely sqrt(d). You are given the ints d, x, and y. Return "YES" if you can arrive at (x, y) in a finite number of moves, and "NO" otherwise.Definition    Class:KnightOfIntegerlandMethod:ableParameters:int, int, intReturns:StringMethod signature:String able(int d, int x, int y)(be sure your method is public)    Notes-In the problem statement, sqrt(d) denotes the square root of d.-The Euclidean distance between two points (x1, y1) and (x2, y2) is equal to sqrt((x1-x2)^2 + (y1-y2)^2).-There is no limit on the coordinates of points visited during your journey. In particular, they are allowed to be outside of the rectangle with corners (0, 0) and (x, y).Constraints-d will be between 1 and 1,000,000,000, inclusive.-x will be between -1,000,000,000 and 1,000,000,000, inclusive.-y will be between -1,000,000,000 and 1,000,000,000, inclusive.Examples0)    2510Returns: "YES"The distance covered by each of your steps must be sqrt(25)=5. You can reach (1, 0) in this way: (0, 0) -> (3, 4) -> (6, 0) -> (1, 0).1)    252276-9059Returns: "YES"From any point (x, y) we can reach (x+1, y) as shown in Example 0. Also, from any point (x, y) we can reach (x, y-1) using a similar sequence of moves. Hence, it is possible to get from (0, 0) to (2276,-9059) by repeating the first sequence of moves 2276 times and then the second sequence of moves 9059 times.2)    55858585885858585Returns: "YES"For d=5 you move like a chess knight. It is well known that the chess knight can reach any cell on an infinite chessboard.3)    44747474774747474Returns: "NO"It's easy to see that for any point (x, y) you can reach, x and y must be both even.4)    16920Returns: "YES"One of the solutions is: (0, 0) -> (13, 0) -> (1, 5) -> (14, 5) -> (2, 0).5)    311Returns: "NO"In this case you can't achieve any integer point other than (0, 0).6)    300Returns: "YES" 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)2003, TopCoder, Inc. All rights reserved.
 Re: Wildcard problems (response to post by [[rng_58]]) | Reply [1000]Problem Statement    NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet. Farmer John and Eel Brus are studying string theory at the university. One day John found a very interesting sequence of strings s1, s2, ..., sK and told Brus about it. Brus only remembers the following information:Each string in the sequence consists of lowercase letters only.The sequence starts with A. In other words, s1 = A.The sequence ends with B. In other words, sK = B.For each i between 1 and K-1, inclusive, si+1 can be obtained by inserting one lowercase letter to si. For example, if s1 is "tco", valid options for s2 include "qtco", "trco", "tcso", and "tcot", but not "xco", "txoc", or "srm".Return the number of sequences that match Brus's information, modulo 1,000,000,007. Brus's memory is always correct, so it is guaranteed that at least one such sequence exists.Definition    Class:StringSequencesMethod:countSequencesParameters:String, StringReturns:intMethod signature:int countSequences(String A, String B)(be sure your method is public)    Constraints-A will contain between 1 and 49 characters, inclusive.-Each character in A will be a lowercase letter ('a'-'z').-B will contain between N+1 and 50 characters, inclusive, where N is the number of characters in A.-Each character in B will be a lowercase letter ('a'-'z').-There will be at least one sequence that matches Brus's information in the problem statement.Examples0)    "oxoxox""foxfoxfox"Returns: 6The following six sequences match Brus's information:"oxoxox", "foxoxox", "foxfoxox", "foxfoxfox""oxoxox", "foxoxox", "foxoxfox", "foxfoxfox""oxoxox", "oxfoxox", "foxfoxox", "foxfoxfox""oxoxox", "oxfoxox", "oxfoxfox", "foxfoxfox""oxoxox", "oxoxfox", "foxoxfox", "foxfoxfox""oxoxox", "oxoxfox", "oxfoxfox", "foxfoxfox"1)    "aaaaa""aaaaaaaa"Returns: 1Only the sequence "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa" matches Brus's information.2)    "tco""tcotco"Returns: 183)    "a""alnfrlrealjnsliejsraijneroav"Returns: 1359257504)    "ppmtmtttppmtmpppmtmtmp""ppmmmpmtmpttmttptpmttptmtmppmppttpmtpppppmmtmmmptp"Returns: 856841145 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)2003, TopCoder, Inc. All rights reserved.
 Re: Wildcard problems (response to post by [[rng_58]]) | Reply [500]Problem Statement    In this problem, we consider 26 variables A, B, C, ..., Z, each of which represents a (possibly empty) string consisting of lowercase letters. You are given a String[] equations. Each element of equations is formatted as "VAR1 = VAR2 + VAL", where VAR1 and VAR2 will each be an uppercase letter representing a variable, and VAL is a non-empty string consisting of lowercase letters. This equation claims that variable VAR1 is equal to the concatenation of variable VAR2 and string VAL (in this order). If there is no (A, B, C, ..., Z) satisfying all given equations, return -1. Otherwise, return the minimum possible sum of the lengths of A, B, C, ..., Z.Definition    Class:StringEquationsMethod:getMinimumParameters:String[]Returns:intMethod signature:int getMinimum(String[] equations)(be sure your method is public)    Constraints-equations will contain between 1 and 50 elements, inclusive.-Each element of equations will contain between 9 and 50 characters, inclusive.-Each element of equations will be formatted as "VAR1 = VAR2 + VAL", where VAR1 and VAR2 will each be an uppercase letter, and VAL will be a non-empty string consisting of lowercase letters.Examples0)    { "B = A + top", "C = B + coder", "C = A + topcoder" }Returns: 11If we assign B = top, C = topcoder and the empty string to each of the other variables, these three equations are satisfied and the sum of the lengths is minimized.1)    { "B = A + coder", "C = B + top", "C = A + topcoder" }Returns: -1The first two equations imply "C = A + codertop", which contradicts the third one.2)    { "A = B + p", "C = A + q", "D = F + r", "E = B + x", "G = A + y", "H = F + z" }Returns: 83)    { "X = X + a" }Returns: -14)    { "Y = X + a", "Y = X + b" }Returns: -1 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)2003, TopCoder, Inc. All rights reserved.
 Forums News, Programs & Events Discussions 2012 TopCoder Open Wildcard problems Previous Thread  |  Next Thread