Hey to everyone!
I've posted some tips, but not so far I've talked to a person, that says
"It is not enough to start programming by yourself".
A lot of beginners visit a lot of courses to be taught programming. Courses, teachers and so on don't teach you how to study. In today's world it is very important to be able to study just everything. You are not good in Java? No problem to start programming on Python.
I find dynamic problems very useful. They make your brain work faster and more correctly, as programming is not just a code, but the algorithms.
Let's start!
Easy level
1. Water lilies
A frog is jumping over water lilies in the pond. The water lilies in the pond are arranged in one row. The frog starts jumping from the first water lily and wants to end on the last one. The frog agrees to jump only forward over one or two water lilies. For example, from water lily number 1, it can only jump to water lilies number 3 or number 4.
Some water lilies have mosquitoes. Namely, A [i] mosquitoes sit on the i-th water lily. When a frog lands on a water lily, it eats up all the mosquitoes sitting on it. The frog wants to plan its route to eat as many mosquitoes as possible. What is the maximum number of mosquitoes she can eat during her trip?
2. No name problem
A matrix A of natural numbers with n rows and m columns is given. For each passage through the cell with indices (i, j), the
fine Ai, j is levied. It is necessary with a minimum fine to pass from any cell of the 1st row to the n-th row, while from the current cell (i, j) you can go to any of the three neighboring cells in the row with a number greater by one: (i + 1, j - 1), (i + 1, j), (i + 1, j + 1) (if they exist).
What is the minimum fine?
Medium level
1. Palindrome
A non-empty string S is entered, which has a length of no more than 7000 characters and consists only of lowercase Latin letters. It is necessary to remove the minimum number of characters from the string so to get a palindrome (a string of characters that is read from left to right and from right to left the same).
What is the length of the resulting palindrome, and what does the palindrome look like?
2. Officials
There is a ministry of n officials. Each of the officials can have both subordinates and bosses, and the rules are:
- my subordinate's subordinates are my subordinates;
- my boss is not my subordinate;
Each official has no more than one immediate superior.
In order to obtain a license for the export of copper, it is necessary to obtain the signature of the first official - the head of all officials (the chief official always has the number 1). The problem is complicated by the fact that each official, generally speaking, can demand a visa, that is, the signatures of some of his immediate subordinates, and bribes - a certain number of dollars in addition to the corresponding visa. Each official knows a set of possible visas and a bribe corresponding to each visa.
An empty set for some official means that he does not require visas in order to put his signature (that is, he puts his signature free of charge). The official puts his signature only after he has been presented with at least one signature from the set of visas required by him (or the list of visas for him is empty).
It is necessary to determine the minimum amount of money an entrepreneur needs to pay in order to obtain a license from a chief official, and indicate the procedure for obtaining signatures corresponding to this amount.
Hard level
1. Huffman coding
Huffman coding (D. A. Huffman) refers to prefix coding, which allows you to minimize the length of the text due to the fact that different characters are encoded with a different number of bits.
Let's recall the process of building the code. First, a Huffman code tree is built. Let the original alphabet consist of n characters, the i-th of which occurs pi times in the input text. Initially, all symbols are considered active nodes of the future tree, the i-th node is marked with pi. At each step, we take two active vertices with the smallest labels, create a new vertex, labeling it with the sum of the labels of these vertices, and make it their parent. The new vertex becomes active, and its two children are removed from the list of active vertices. The process is repeated many times until only one active vertex remains, which is assumed to be the root of the tree.
Note that the symbols of the alphabet are represented by the leaves of this tree. For each leaf (symbol), the length of its Huffman code is equal to the length of the path from the root of the tree to it. The code itself is constructed as follows: for each internal vertex of the tree, consider two arcs going from it to the children. We assign the label 0 to one of the arcs, and to the other 1. The code of each symbol is a sequence of zeros and ones on the path from the root to the leaf.
The task is to calculate the length of the text after it has been Huffman-encoded. The text itself is not given, it is only known how many times each character occurs in the text. This is sufficient for solving the problem, since the length of the code depends only on the frequency of occurrence of symbols. The answer: a single number - the length (in bits) of the encoded text.
2. Hammond organ
Alexander wants to learn how to play Hammond's organ.
He has already found a melody to play. For simplicity, he wrote out a sequence of AA notes of length NN from integers, which represent the number of keys: the higher the number, the more to the right of the key on the keyboard.
Alexander is very smart and understands that the most important thing is the correct fingering, that is, the correct choice of which finger to play which note. If you choose uncomfortable fingers, then you can spend a lot of time trying to learn how to play a melody and still not succeed in the end.
Let's designate the fingers on the hand with numbers from 1 to 5.
Let's call any sequence of BB numbers of fingers by fingering. We call fingering convenient if for any 1 <= i <= N
the following is done:
- If A[i]<A[i+1], then B[i]<B[i+1],
- If A[i]=A[i+1], then B[i]!=B[i+1],
- If A[i]>A[i+1], then B[i]>B[i+1].
Find any convenient fingering. It is guaranteed that it exists.
Conclusion
You will ask me: "Why are there no algorithms and answers?". It is a psychological moment: When you see after the problem its solution, it will be not so effective for your brain, as you peep at the solution of a problem. These problems are not new and are available free on the Internet. Better first to try by yourself and only then to check your solution. The key is in productivity!
Hopefully, it was useful for those who make their first steps.
Good luck in your job!
Written by Andersen