This is the editorial for the Stamford Practice Contest on 21 February 2023 A special thanks to Ahmmed Sakib Noman for creating this wonderful editorial!
Hames Bond
Solution: The input is given in the following ways,
In every row we have the hames bonds, and every column we have the tasks or missions,
Now if a mission is assigned to any hames bond then the probability of completing of the mission is that row ans columns value. And when a mission is assigned to any hames bond then that mission and that hames bond can’t be used any more.
As the limit of N i.e. the number of mission and number of hames bond is 20 i.e. small, we can try all possibility in the following way.
In initial state all the columns are free to use and none of the hames bond are calculated
So in this state the ans is {{ 00…00, 1.00 }},
first value is all 0 in bitwise representation means all columns are available for ans.
Second value i.e. ans for this state is 1.00 because we are going to multiply all the probability.
Now for each row and each column we iterate through the list of current ans pairs and see if current column is available for this this then we transition like this
Suppose current ans’s one of the item is { 100001, 0.3 }
Current row = 3, and column = 2 and this ones probability is 0.7
Then the transition is,
We check if current columns bit of the current ans item.first & ( 1 << column ) if this expression turn out not zero means this column is already taken so we can’t make this transition. But is this value turn out zero then we can make this transition like so
Next ans is { 100001 | ( 1 << column ) , 0.3 * 0.7 } => { 100101, 0.21 }
After all the transitions are completed we will find the ans.
Complexity : as we are going to iterate over all the rows and all the columns this gives us O(N * N ) complexity. And to make the transitions we are going to use map of size 2**20
So the total complexity turns out O ( ( N * N ) + ( N * (2^20) ) )
Code : #include "bits/stdc++.h"using namespace std;// clang-format off#define s - Pastebin.com
Easier Said Than Done
Solution : In this problem suppose the flood does not expand. Then this problem is easy. We can just simply do a bfs form the starting node and find the best solution to the ending node.
For bfs every cell is a node and the found neighbor cells are connected with it. So a simple bfs can solve the problem.
But we need to consider the flood expansions. To do so we can make find out the flood explosion first and save them. Like so.
We can make an big array _cell_content state [ _time ] [ _row ] [ _col ]
Now in the state array for time = 0 we can simply copy the input states.
Now from time 1 … ( N * N ):
Copy the state [ time - 1 ] [ … ] [ … ] to the state [ time ] [ … ] [ … ]
And now expand the current flood locations one of its neighbour.
After doing so we can find out the state of each cell at any given time.
Now we are going to do the same as first i.e. do a bfs but in this bfs we are going to consider the time also. Like if i came into cell { _r, _c } then we will save the time, row, col as { _t, _r, _c }.
To do the next transition we are going to take the next cells states from the big state array with _t + 1 if this cell is available. If a solution is found the we can print that time or print the no solution ans.
Complexity : to create the big state array we need O ( N * N * N * N ) time and space. And for the bfs takes O ( N + ( 4 * N ) )
So the total time complexity is O ( N^4 + N + ( 4 * N ) ).
Code : #include "bits/stdc++.h"using namespace std;// clang-format off#define s - Pastebin.com
Dadagiri
Solution : As the output format is quite simple, first two characters will be formed by a # diamond shape and third character is needed to be formed by a * made a diamond shape.
So for the output we can use an special strings of vector.
[i: .#…#…*…]
[i: #.#.#.#.*.*.]
[i: .X.#.X.*.X.*]
[i: #.#.#.#.*.*.]
[i: .#…#…*…]
In the middle line string, all the character X needed to be replaced by the input characters. And these strings can be concatenated as many times as needed that won’t affect anything. And form the first and the characters X will be replaced with the input characters.
And will print only the needed amount of characters from the strings.
But there is two problems,
- First column of each string is missing. This is missing because we needed to make the string concatenate able. And before printing, first first character will be added.
- Secondly, if the input character count mod 3 is 2 i.e. [ len % 3 == 2 ] we need replace the last character of the middle string
*with#. Thats all.
Complexity: O ( len(input) * 12 * 5 )
Code : #include "bits/stdc++.h"using namespace std;// clang-format off#define s - Pastebin.com
Behold the Fear of Geometry 2
Solution: The first line of output should be the area of the circle in euclidean geometry, and the second line is also the area of the circle using taxicab geometry.
We know the area of the circle is 𝜋R2.
The R is given and for euclidean geometry the value of PI (𝜋) is 3.14159. So the ans for euclidean is directly using the formula.
For the taxicab geometry we can get the value of PI using the formula
=> Ans = 𝜋R2
=> 𝜋 = Ans / R2
This Ans and R can be used form any sample to get the value of PI then all values are found.
Complexity : O ( 1 )
Code : #include <bits/stdc++.h>using namespace std;using ld = long double;int m - Pastebin.com
Modulo 1
Solution : We need to take 10 numbers as input and mod them all by 42 and count the number of distinct modulus. To count the number of distinct modulus we can put all the modulus in a set data structure. And the size of the set is the count of the number of distinct modulus i.e. the ans.
Complexity: modulus is O(1) operations and need to do this for 10 i.e. N elements. This complexity is O(N) and putting all N elements in a set is log2(N). So the total complexity is O(N * log2(N) )
Code: #include "bits/stdc++.h"using namespace std;// clang-format off#de - Pastebin.com