601 - The PATH
You can use DFS... but it is a bit troublesome... A better way is to flood fill from left to right, replacing 'w' with some other character, say '1', and check whether in the rightmost column, there exist a '1', if yes, white already have the winning path.
If no '1' exist in the rightmost column, then do flood fill from right to left (opposite direction), replacing all 'w' with another character, say '2'... then check whether there exist an unfilled cell which have '1' on the left and '2' on the right, which means using one more move, white will win...
Same reasoning for black, but this time from top to bottom...
If nothing can be concluded, output there is no winner.
602 - What Day Is It?
Using the Julian & Gregorian date rule, you are asked to determine the day if valid or print error message otherwise. I can say that this is a complex problem and need sufficient knowledge of calendar system. Good luck.
Anyone want to add more explanation for this problem?
612 - DNA Sorting
If you analyze the problem carefully, you'll then realize that "sortedness" here means "how many bubble sort steps we need". After knowing all "bubble sort steps", we can then rearrange the input according to their "sortedness".
Read all input, store it into an array.
Do a bubble sort for each items in array (use temporary variable, sort that variable, not the original, we need them for the output)
Count how many steps we need to make them sorted.
From ``most sorted'' to ``least sorted'', print them.
614 - Mapping the Route
This problem itself is not difficult, just use the algorithm given in the problem description. The problem is the output format. In my solution, I use a string buffer to store temporary output, modify this output, after everything is ok, I print the string buffer. You must remember that for every movement, you must start from West->North->East->South direction again, not from the last direction.
615 - Is It A Tree?
Check whether the given graph is a tree or not. Refer to your data structures book.
616 - Coconut, Revisited (why WA?)
Just simulate the division process up to sqrt right??... I wonder what's wrong...
617 - Nonstop Travel
Do a brute force complete search from speed 30 mph to 60 mph. To avoid loss precision, use fmod (floating point modulo) instead of mod (integer modulo) and be careful in formatting the output.
620 - Cellular Structure
Do a recursive check of the grammar. Shouldn't be too difficult.
621 - Secret Research
positive result S = 1 or S = 4 or S = 78
negative result S = S35
experiment failed S = 9S4
experiment not completed S = 190S
Actually this problem can be very easy once you know what it means (or when you read this hint). How to know which output we have to give for each input? The answer is simple:
Positive when S is exactly "1","4",or "78"
Negative when the last two digits of S are exactly "35"
Experiment failed if the first digit of S is exactly "9" and the last one digit of S is exactly "4"
Experiment not completed if the first three digits are exactly "190"
622 - Grammar Evaluation
There is no trick in this problem, just recursively check the expression using the given grammar. Check whether these simple test cases are passed:
7
1+2
1++2
1**2
1)(2
(12)
(12)*(12)
(1+2)*(2*3)
3
ERROR
ERROR
ERROR
12
144
18
623 - 500!
A simple factorial problem, and the maximum size is "not 500", but 1000... They said 500 is "too small" :p. If you have your Big Integer library ready, just do it...
624 - CD
Just do an exhaustive backtracking search with effective pruning.
626 - Ecosystem
Max N ?? only 100, simply set a three nested loop i,j,k from 1 to n...
Print the indexes and increase total if ij>k and i eat j, j eat k and k eat i...
Finally output total possibilities accumulated so far.
627 - The Net
Simple Graph Traversal problem. Either BFS or DFS will do. Just make sure you output the path with lowest IDs if there are more than one minimum path...
630 - Anagrams (II)
If you generate all the anagrams of the word first then, compare it one by one with the dictionary, you will get Time Limit Exceeded.
A better approach is to compare each element in dictionary with the word using my checkAnagram() function (see programming section).
636 - Squares (II)
Trial and Error... start from smaller base number one by one until you found the answer.
637 - Booklet Printing
Take two or more pieces of paper and try to make a booklet from these piece of papers manually, then just simulate what human will do to a code.
640 - Self Numbers (by: James Chew)
Dynamic Programming is required here. Prepare a big array of 1,000,000 elements, and then generate all the numbers from bottom up. After that, output the numbers that has no generator (self numbers).
641 - Do the Untwist
Just reverse the formula and decrypt it... straightforward...
642 - Word Amalgamation
This is just an anagram checker problem. Sort the dictionary, record the frequency of each letter in the words. And then when you are given a scrambled word, output all their anagrams, which will be lexicographically sorted by default if you have sort the dictionary.
644 - Immediate Decodability
Brute force... only maximum 8 codes, each code only have at max 10 bits... try all nC2 (n Choose 2) possible pairings and check whether bit i and bit j is a prefix of each other... total brute force...
647 - Chutes and Ladders
My childhood game :). This problem is just a simple but tedious game simulation. You must carefully read the problem description (the game rule), and then simulate it.
654 - Ratio
From a given numerator A and denominator B, construct ratios starting with denominator 1 which closest to the actual value of A/B. Keep computing ratios that are getting closer and closer to the actual value until our approximation equal to A/B.
657 - The die is cast
Tricky flood fill problem. After counting the number in a dice, delete that dice to make sure subsequent counting will not count that dice anymore.
663 - Sorting Slides (by: MD Erfan Hoque)
Construct the following graph:
1 to n nodes for the slides,n+1 to n+n nodes for the numbers.
edge from the slides to the possible numbers.
Now Run your maximum Bipartite matching algorithm and find
all match. For all match edges flip the direction of the edges.
Now start a DFS which start from i node and return back in
again at i node[i.e i=1 to n].If for any i it is not possible
to return at i then it is correct match to choose the jth number
for ith point where i and j is match edge and output this pair.
If no pair found to output then output is none as problem description.
665 - False Coin
A bit similar to problem 608, this problem ask the same question, which one is false/counterfeit coin. If I'm not mistaken you can use the same concept as 608.
670 - The dog task
This problem is a Network Flow (more precise, Maximum Bipartite Matching) problem. Find the best matching for the Bob's positions and interesting places.
You have to construct the bipartite graph first. Add an edge if from Bob's position, the dog can visit the interesting place and go back to Bob without violating the constraint (the dog's round trip distance can't be more 2 times Bob's distance). After that, just pass this graph to your Network Flow or Maximum Bipartite Matching algorithm to get the result.
671 - Spell checker
Very straightforward. Read in the dictionaries (you don't need to sort this...you will have to check all elements anyway...), then read the query words.
If this query word matches any of them, output that this word is correct.
If this query word differs by insert/delete/or change one char, add this to our match list, at the end, output this list.
673 - Parentheses Balance
You have to check whether a given string containing brackets is correct or not. Solution:
1. You can do stack-based solution, pushing every time you encounter open bracket and popping every time you encounter matching close bracket.
2. Or, you can do what I did, Do a looping from 1 to the first occurrence (Forward) of close bracket, then from that point, move backward to the first occurrence of open bracket, then cut that portion of string. Do this until we get empty string (It's a balanced parentheses) or when we cannot do any more search (Unbalanced parentheses).
Example of the second implementation
(()) Original string
(()) First search, found ) at index 3
(()) Go back, found ( at index 2
() Delete that portion of string
() Second search, found ) at index 2
() Go back, found ( at index 1
Empty string, it's a balanced parentheses.
Please note that empty string is by default correct and there are two types of bracket "()" and "[]", each of them must be treated differently.
674 - Coin Change
Another coin changing problem.
Note:
Coin Changing problem also found in problem 147 (Dollars) and problem 357 (Let Me Count The Ways). You can solve 3 problems using one similar source code.
677 - All Walks of length ``n'' from the first node
Simple Depth First Search (bounded to depth ``n''). You don't have to consider the Boolean matrix multiplication given in the problem description, it has no effect. Just don't forget to print "no walk of length n" if there is no walk of length n.
679 - Dropping Balls
A problem that makes you think of efficiency to the limit =). I have to try several times to get this one accepted. Direct simulating the process is impossible since 2^20 is too big for your memory (and even if you have that memory, you don't pass that annoying 10 seconds Time Limit).
After a careful study of Binary Tree properties... I derive the following formula, which is definitely a cheat if you directly copy this without reading below :p
The formula:
P=1;
for (j=0;j
P=I%2!=0 ? 2*P : 2*P+1; /* go to left or right? */
I=(I+1)/2; /* round up */
}
P is the final value that we want to find (one of the leaves of binary tree), so we loop from 0 to D-1 (yes, this means we compute only the non terminal nodes). For each non terminal nodes, we check whether I is multiples of two, if no, we go to the left (remember, in a tree, left index is 2*parent index and right index is 2*parent index+1), if yes, we go to the right. Finally we divide the value of I by 2 (rounded up).
Why this formula is true? The root (1st level) will be toggled (yes, TOGGLED!!!, this is the key for efficiency) I times, Nodes on the 2nd level will be toggled I/2 (rounded up) times, ..., Nodes on kth level will be toggled I/(2^(k-1)) times. And toggles means binary, and binary is related with modulo 2... so we just check whether I is multiples of 2 or not... =)
681 - Convex Hull Finding
As the name suggests... Your task is "simply" find the convex hull... You can't solve this problem unless you have learned at least one of convex hull finding algorithm (Graham Scan, Jarvis March/Gift Wrapping, Divide & Conquer, Quick hull, etc). Knowing the algorithms is also insufficient since it is very hard (at least for me) to produce a 100% bug-free code... This problem will be a perfect testing ground for those who want to try learning computational geometry :). Try it.
686 - Goldbach's Conjecture (II)
4 until 2^15 is small :-), prepare a pre-calculated primes below 2^15. Then for a given n, just find pairs of primes (from prime table) so that the total of this two primes equal to n.
694 - The Collatz Sequence
3n+1 again. It shouldn't be difficult, isn't it? Just simulate it, counting the maximum terms computed.
696 - How Many Knights
There exist a formula to count number of possible placement of knight in M*N board without backtracking at all. You must derive this formula since 500*500 is too big for simulation.
699 - The Falling Leaves
Given a tree with values in the nodes. Flatten them (i.e. put all nodes on the ground), summing their values. And then print from left to right. The key algorithm to solve this problem is your Tree Traversal algorithm.
You can use DFS... but it is a bit troublesome... A better way is to flood fill from left to right, replacing 'w' with some other character, say '1', and check whether in the rightmost column, there exist a '1', if yes, white already have the winning path.
If no '1' exist in the rightmost column, then do flood fill from right to left (opposite direction), replacing all 'w' with another character, say '2'... then check whether there exist an unfilled cell which have '1' on the left and '2' on the right, which means using one more move, white will win...
Same reasoning for black, but this time from top to bottom...
If nothing can be concluded, output there is no winner.
602 - What Day Is It?
Using the Julian & Gregorian date rule, you are asked to determine the day if valid or print error message otherwise. I can say that this is a complex problem and need sufficient knowledge of calendar system. Good luck.
Anyone want to add more explanation for this problem?
612 - DNA Sorting
If you analyze the problem carefully, you'll then realize that "sortedness" here means "how many bubble sort steps we need". After knowing all "bubble sort steps", we can then rearrange the input according to their "sortedness".
Read all input, store it into an array.
Do a bubble sort for each items in array (use temporary variable, sort that variable, not the original, we need them for the output)
Count how many steps we need to make them sorted.
From ``most sorted'' to ``least sorted'', print them.
614 - Mapping the Route
This problem itself is not difficult, just use the algorithm given in the problem description. The problem is the output format. In my solution, I use a string buffer to store temporary output, modify this output, after everything is ok, I print the string buffer. You must remember that for every movement, you must start from West->North->East->South direction again, not from the last direction.
615 - Is It A Tree?
Check whether the given graph is a tree or not. Refer to your data structures book.
616 - Coconut, Revisited (why WA?)
Just simulate the division process up to sqrt right??... I wonder what's wrong...
617 - Nonstop Travel
Do a brute force complete search from speed 30 mph to 60 mph. To avoid loss precision, use fmod (floating point modulo) instead of mod (integer modulo) and be careful in formatting the output.
620 - Cellular Structure
Do a recursive check of the grammar. Shouldn't be too difficult.
621 - Secret Research
positive result S = 1 or S = 4 or S = 78
negative result S = S35
experiment failed S = 9S4
experiment not completed S = 190S
Actually this problem can be very easy once you know what it means (or when you read this hint). How to know which output we have to give for each input? The answer is simple:
Positive when S is exactly "1","4",or "78"
Negative when the last two digits of S are exactly "35"
Experiment failed if the first digit of S is exactly "9" and the last one digit of S is exactly "4"
Experiment not completed if the first three digits are exactly "190"
622 - Grammar Evaluation
There is no trick in this problem, just recursively check the expression using the given grammar. Check whether these simple test cases are passed:
7
1+2
1++2
1**2
1)(2
(12)
(12)*(12)
(1+2)*(2*3)
3
ERROR
ERROR
ERROR
12
144
18
623 - 500!
A simple factorial problem, and the maximum size is "not 500", but 1000... They said 500 is "too small" :p. If you have your Big Integer library ready, just do it...
624 - CD
Just do an exhaustive backtracking search with effective pruning.
626 - Ecosystem
Max N ?? only 100, simply set a three nested loop i,j,k from 1 to n...
Print the indexes and increase total if i
Finally output total possibilities accumulated so far.
627 - The Net
Simple Graph Traversal problem. Either BFS or DFS will do. Just make sure you output the path with lowest IDs if there are more than one minimum path...
630 - Anagrams (II)
If you generate all the anagrams of the word first then, compare it one by one with the dictionary, you will get Time Limit Exceeded.
A better approach is to compare each element in dictionary with the word using my checkAnagram() function (see programming section).
636 - Squares (II)
Trial and Error... start from smaller base number one by one until you found the answer.
637 - Booklet Printing
Take two or more pieces of paper and try to make a booklet from these piece of papers manually, then just simulate what human will do to a code.
640 - Self Numbers (by: James Chew)
Dynamic Programming is required here. Prepare a big array of 1,000,000 elements, and then generate all the numbers from bottom up. After that, output the numbers that has no generator (self numbers).
641 - Do the Untwist
Just reverse the formula and decrypt it... straightforward...
642 - Word Amalgamation
This is just an anagram checker problem. Sort the dictionary, record the frequency of each letter in the words. And then when you are given a scrambled word, output all their anagrams, which will be lexicographically sorted by default if you have sort the dictionary.
644 - Immediate Decodability
Brute force... only maximum 8 codes, each code only have at max 10 bits... try all nC2 (n Choose 2) possible pairings and check whether bit i and bit j is a prefix of each other... total brute force...
647 - Chutes and Ladders
My childhood game :). This problem is just a simple but tedious game simulation. You must carefully read the problem description (the game rule), and then simulate it.
654 - Ratio
From a given numerator A and denominator B, construct ratios starting with denominator 1 which closest to the actual value of A/B. Keep computing ratios that are getting closer and closer to the actual value until our approximation equal to A/B.
657 - The die is cast
Tricky flood fill problem. After counting the number in a dice, delete that dice to make sure subsequent counting will not count that dice anymore.
663 - Sorting Slides (by: MD Erfan Hoque)
Construct the following graph:
1 to n nodes for the slides,n+1 to n+n nodes for the numbers.
edge from the slides to the possible numbers.
Now Run your maximum Bipartite matching algorithm and find
all match. For all match edges flip the direction of the edges.
Now start a DFS which start from i node and return back in
again at i node[i.e i=1 to n].If for any i it is not possible
to return at i then it is correct match to choose the jth number
for ith point where i and j is match edge and output this pair.
If no pair found to output then output is none as problem description.
665 - False Coin
A bit similar to problem 608, this problem ask the same question, which one is false/counterfeit coin. If I'm not mistaken you can use the same concept as 608.
670 - The dog task
This problem is a Network Flow (more precise, Maximum Bipartite Matching) problem. Find the best matching for the Bob's positions and interesting places.
You have to construct the bipartite graph first. Add an edge if from Bob's position, the dog can visit the interesting place and go back to Bob without violating the constraint (the dog's round trip distance can't be more 2 times Bob's distance). After that, just pass this graph to your Network Flow or Maximum Bipartite Matching algorithm to get the result.
671 - Spell checker
Very straightforward. Read in the dictionaries (you don't need to sort this...you will have to check all elements anyway...), then read the query words.
If this query word matches any of them, output that this word is correct.
If this query word differs by insert/delete/or change one char, add this to our match list, at the end, output this list.
673 - Parentheses Balance
You have to check whether a given string containing brackets is correct or not. Solution:
1. You can do stack-based solution, pushing every time you encounter open bracket and popping every time you encounter matching close bracket.
2. Or, you can do what I did, Do a looping from 1 to the first occurrence (Forward) of close bracket, then from that point, move backward to the first occurrence of open bracket, then cut that portion of string. Do this until we get empty string (It's a balanced parentheses) or when we cannot do any more search (Unbalanced parentheses).
Example of the second implementation
(()) Original string
(()) First search, found ) at index 3
(()) Go back, found ( at index 2
() Delete that portion of string
() Second search, found ) at index 2
() Go back, found ( at index 1
Empty string, it's a balanced parentheses.
Please note that empty string is by default correct and there are two types of bracket "()" and "[]", each of them must be treated differently.
674 - Coin Change
Another coin changing problem.
Note:
Coin Changing problem also found in problem 147 (Dollars) and problem 357 (Let Me Count The Ways). You can solve 3 problems using one similar source code.
677 - All Walks of length ``n'' from the first node
Simple Depth First Search (bounded to depth ``n''). You don't have to consider the Boolean matrix multiplication given in the problem description, it has no effect. Just don't forget to print "no walk of length n" if there is no walk of length n.
679 - Dropping Balls
A problem that makes you think of efficiency to the limit =). I have to try several times to get this one accepted. Direct simulating the process is impossible since 2^20 is too big for your memory (and even if you have that memory, you don't pass that annoying 10 seconds Time Limit).
After a careful study of Binary Tree properties... I derive the following formula, which is definitely a cheat if you directly copy this without reading below :p
The formula:
P=1;
for (j=0;j
P=I%2!=0 ? 2*P : 2*P+1; /* go to left or right? */
I=(I+1)/2; /* round up */
}
P is the final value that we want to find (one of the leaves of binary tree), so we loop from 0 to D-1 (yes, this means we compute only the non terminal nodes). For each non terminal nodes, we check whether I is multiples of two, if no, we go to the left (remember, in a tree, left index is 2*parent index and right index is 2*parent index+1), if yes, we go to the right. Finally we divide the value of I by 2 (rounded up).
Why this formula is true? The root (1st level) will be toggled (yes, TOGGLED!!!, this is the key for efficiency) I times, Nodes on the 2nd level will be toggled I/2 (rounded up) times, ..., Nodes on kth level will be toggled I/(2^(k-1)) times. And toggles means binary, and binary is related with modulo 2... so we just check whether I is multiples of 2 or not... =)
681 - Convex Hull Finding
As the name suggests... Your task is "simply" find the convex hull... You can't solve this problem unless you have learned at least one of convex hull finding algorithm (Graham Scan, Jarvis March/Gift Wrapping, Divide & Conquer, Quick hull, etc). Knowing the algorithms is also insufficient since it is very hard (at least for me) to produce a 100% bug-free code... This problem will be a perfect testing ground for those who want to try learning computational geometry :). Try it.
686 - Goldbach's Conjecture (II)
4 until 2^15 is small :-), prepare a pre-calculated primes below 2^15. Then for a given n, just find pairs of primes (from prime table) so that the total of this two primes equal to n.
694 - The Collatz Sequence
3n+1 again. It shouldn't be difficult, isn't it? Just simulate it, counting the maximum terms computed.
696 - How Many Knights
There exist a formula to count number of possible placement of knight in M*N board without backtracking at all. You must derive this formula since 500*500 is too big for simulation.
699 - The Falling Leaves
Given a tree with values in the nodes. Flatten them (i.e. put all nodes on the ground), summing their values. And then print from left to right. The key algorithm to solve this problem is your Tree Traversal algorithm.
