ITU ACM Student Branch Contest 3 Editorial
Posted on 16 September, 2018 in Algorithm
Hello there,
We are going to analyze each question from ITU ACM Contest 3. You can check the questions from this link.
You can find ITU ACM Contest 2 in this link. You can find ITU ACM Contest 1 in this link.
Question One - Marvelous Mathematician Yalcinkaya - O(1)
The question asks us to calculate the area of the circle. Hence, We will use the following formula
$$ Area = π•r^2 $$
#include <cmath>
#include <cstdio>
#include <utility>
#include <vector>
#include <iostream>
#include <climits>
#include <limits>
#include <algorithm>
#include <iostream>
#include <set>
#include <fstream>
#include <istream>
#include <ostream>
#include <queue>
#include <bitset>
#include <map>
#include <stack>
#include <ctype.h>
using namespace std;
int main() {
int t,r;
scanf("%d", &t);
while(t--){
scanf("%d", &r);
printf("%d\n", r*r*3);
}
return 0;
}
Question Two - Oğuz and His New Job 3 - O(N)
The question has several test cases. Each test case has two strings. Let's call the first string with A and second string with B. We need to check if A ends with B or not. We label the communication correct if A ends with B.
#include <cmath>
#include <cstdio>
#include <utility>
#include <vector>
#include <iostream>
#include <climits>
#include <limits>
#include <algorithm>
#include <iostream>
#include <set>
#include <fstream>
#include <istream>
#include <ostream>
#include <queue>
#include <bitset>
#include <map>
#include <stack>
#include <ctype.h>
using namespace std;
int main() {
int t;
string a,b;
scanf("%d", &t);
while(t--){
cin >> a >> b;
int aSize = a.size(), bSize = b.size();
// Input-b should have fewer characters than input-a.
if(aSize < bSize){
printf("Wrong Communication\n");
continue;
}
// Mark the communication as correct.
bool flag = true;
// Check characters one by one. If characters are not equal, change the flag to false.
for(int i=0;i<bSize;i++){
flag = (b[i] == a[aSize-bSize+i]);
if(!flag) break;
}
printf(flag ? "Correct Communication\n" : "Wrong Communication\n");
}
return 0;
}
Question Three - Yavuz and His Brilliant 3ncrypt10n Technique 3 - O(N*M)
The question gives us a matrix created with letters. We need search IEEE word by mapping I and E with another letter. We have two strict rules.
- I is not mapped with I - E is not mapped with E
- I and E should mapped with different letters.
We can encapsulate the input with asterisk. This event gives us the ease of navigating the matrix.
We have 4 different for loops.
- The first loop is for selecting a letter for I. It is from A to Z.
- The second loop is for selecting a letter for E. It is from A to Z.
- The third loop is for navigating in the matrix. It is from 0 to N.
- The third loop is for navigating in the matrix. It is from 0 to M.
For each letter in the matrix, we can go with 8 possible directions. We need to check each of them.
#include <cmath>
#include <cstdio>
#include <utility>
#include <vector>
#include <iostream>
#include <climits>
#include <limits>
#include <algorithm>
#include <iostream>
#include <set>
#include <fstream>
#include <istream>
#include <ostream>
#include <queue>
#include <bitset>
#include <map>
#include <stack>
#include <ctype.h>
using namespace std;
int main() {
int t;
scanf("%d",&t);
while(t--) {
int n, m;
scanf("%d%d",&n,&m);
vector<string> input(n + 6, string(m + 6, '*'));
// Reading the encapsulated input.
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> input[i + 3][j + 3];
int counter = 0, currentCounter = 0;
char cI = ' ', cE = ' ';
for (int i = 0; i <= 25; i++) { // This loop is for selecting a letter for I.
cI = (char) (i + 65);
if (cI != 'I') {
for (int j = 0; j <= 25; j++) { // This loop is for selecting a ltter for E.
currentCounter = 0;
cE = (char) (j + 65);
if (cE != cI && cE != 'E') {
// Move in the matrix.
for (int z = 3; z < n + 3; z++) {
for (int v = 3; v < m + 3; v++) {
if (input[z][v] == cI) { // If the current letter in the matrix is the mapped-I start to count all possibilities.
// UP
currentCounter += (input[z + 1][v] == cE && input[z + 2][v] == cE && input[z + 3][v] == cE);
// UP-LEFT
currentCounter += (input[z + 1][v + 1] == cE && input[z + 2][v + 2] == cE && input[z + 3][v + 3] == cE);
// LEFT
currentCounter += (input[z][v + 1] == cE && input[z][v + 2] == cE && input[z][v + 3] == cE);
// DOWN-LEFT
currentCounter += (input[z - 1][v + 1] == cE && input[z - 2][v + 2] == cE && input[z - 3][v + 3] == cE);
// DOWN
currentCounter += (input[z - 1][v] == cE && input[z - 2][v] == cE && input[z - 3][v] == cE);
// DOWN-RIGHT
currentCounter += (input[z - 1][v - 1] == cE && input[z - 2][v - 2] == cE && input[z - 3][v - 3] == cE);
// RIGHT
currentCounter += (input[z][v - 1] == cE && input[z][v - 2] == cE && input[z][v - 3] == cE);
// UP-RIGHT
currentCounter += (input[z + 1][v - 1] == cE && input[z + 2][v - 2] == cE && input[z + 3][v - 3] == cE);
}
}
}
}
counter = max(counter, currentCounter);
}
}
}
printf("%d\n", counter);
}
return 0;
}
Question Four - Adventures of Bugrul - O(N+M)
The question asks us to find the minimum roads to construct. The rule is reaching every single node by using just two roads from Node-1. Therefore, we are going to build roads from Node-1.
The question can be solved by using the DFS technique.
- Mark every single node is not reachable.
- While moving on the three with BFS mark node reachable if the counter is smaller than 2.
- When we come to the leaf node, construct the road to the parent of the leaf and mark every single node as reachable, if we can access from the parent of the leaf.
- While going up from the tree (End of the DFS) do the same. Mark nodes' parent as reachable if the current node is not reachable.
#include <cmath>
#include <cstdio>
#include <utility>
#include <vector>
#include <iostream>
#include <climits>
#include <limits>
#include <algorithm>
#include <iostream>
#include <set>
#include <fstream>
#include <istream>
#include <ostream>
#include <queue>
#include <bitset>
#include <map>
#include <stack>
#include <ctype.h>
#define ll long long
#define maxn 500005
using namespace std;
int visited[maxn];
bool isReachable[maxn];
ll counter = 0;
vector<vector<int>> tree;
void dfs(int currentNode, int currentCount, int parentNode){
// If the current count is smaller than two, we can always access that node.
if(currentCount <= 2) isReachable[currentNode] = true;
// Moving on the tree
for (int t : tree[currentNode]) {
if(visited[t] == 0){
visited[t] = 1;
dfs(t, currentCount+1, currentNode);
}
}
// When we are returning from the leaf node. Check if we can reach that node.
// If we can not reach, construct a road to its' parent.
if(!isReachable[currentNode]){
isReachable[parentNode] = true;
for(int t : tree[parentNode]) isReachable[t] = true;
counter++;
}
}
int main() {
int n,m,a,b;
scanf("%d%d", &n, &m);
tree.resize(maxn);
for(int i=0;i<n-1;i++){
scanf("%d %d", &a, &b);
tree[a-1].push_back(b-1);
tree[b-1].push_back(a-1);
}
visited[0] = 1;
dfs(0, 0, 0);
ll output = (ll)m*(ll)counter;
printf("%lld\n", output);
return 0;
}
Question Five - Eylül and Her New Job - O(M•log(N))
The question asks us to find the time between costumers and cashiers.
The costumer is in a line. They come one by one. Moreover, they will go to the smallest indexed number cashier if there are many cashiers available. Hence, we can handle cashier-costumer relationship by using min-heap. We can do the following for solving this question.
- Assign each customer to each available cashier. Put each of them(\(N_i • M_i\)) into min-heap.
- Pop from min-heap to access the first cashier that is available. Assign that cashier to the new costumer. The important part in here is calculating the total time. Hence we always sum the past time with the new time, that will spend with the new costumer.
- Pop everything from min-heap. The last value is our answer.
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
// The first element in the pair represents the time taken
// The second element represents the index number.
typedef pair<long long int, long long int> llp;
const int MAXN = 2e6+26;
int N, M;
long long int ar[MAXN];
priority_queue<llp, vector<llp>, greater<llp>> pq;
int main(){
scanf("%d%d", &N, &M);
// Reading the input and pushing the index number to min heap.
for(int i=1 ; i<=N ; i++ ){
scanf("%lld", ar + i);
pq.push(llp(0, i));
}
long long int tmp;
for( int i=0 ; i<M ; i++ ){
scanf("%lld", &tmp);
// Poping the accessible cashier
llp nx = pq.top();
pq.pop();
// Assigning accessible cashier to the new costumer.
pq.push(llp(nx.first + tmp * ar[nx.second], nx.second));
}
// Pop until the last element since we want to have the taken time for all costumers.
while( pq.size() != 1 )
pq.pop();
printf("%lld\n", pq.top().first);
return 0;
}
Special thanks to Burak Bugrul for the implementation of this question.
Question Six - Solut and Linux Kernel - O(M+N)
A file can have many dependencies. Hence, we need to process all the dependencies before the main file.
If we draw the dependency graph, we can see that we need to find topological sort of the graph.
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1e5+15;
int N, M;
bool visited[MAXN];
long long int ans;
long long int ar[MAXN];
long long int res[MAXN];
vector<int> graph[MAXN];
long long int dfs( int node ){
visited[node] = true;
res[node] = ar[node];
// Traverse the graph by using DFS.
for( int adj : graph[node] ){
if( !visited[adj] )
dfs(adj);
// When going back from the nodes, update time of the current node.
res[node] = max(res[node], res[adj] + ar[node]);
}
return res[node];
}
int main(){
scanf("%d%d", &N, &M);
for( int i=1 ; i<=N ; i++ )
scanf("%lld", ar + i);
for( int k, f, t, i=1 ; i<=N ; i++ ){
scanf("%d%d", &k, &t);
while(k--){
scanf("%d", &f);
graph[t].push_back(f);
}
}
printf("%lld\n", dfs(M));
return 0;
}
Special thanks to Burak Bugrul for the implementation of this question.
Question Seven - Blackbeard Rgzi 2 - O(\(N•log(N*MaxN_i)\))
We need to find the optimal T value that makes DealtDamage the smallest. To solve this we can do the following
- Find all mean values of \(N_i\), let's call it meanVector, and create an array with all \(N_{ij}\) values, let's call it valuesVector.
- Sort meanVector and valuesVector. this allows us to do the binary search.
- Create sumValuesVector from ValuesVector. Each index of sumValuesVector represents the summed values until the current index.
- Find the location of the currentMeanValue by using binary search. Now, we know the location of currentMeanValue. This allows us to recognize smaller values and bigger values.
- After finding the location of currentMeanValue, we can total sum until currentMeanValue and after currentMeanValue by using sumValuesVector
- Since we know the totalSum of the values that are smaller than currentMeanValue and number of values that are smaller currentMeanValue. We can calculate the currentMeanValue - \(N_{ij}\) for smaller values.
- Since we know the totalSum of the values that are bigger than currentMeanValue and number of values that are bigger currentMeanValue. We can calculate the currentMeanValue - \(N_{ij}\) for bigger values.
- The total sum will be the biggerSum + smallerSum. We need fin the smallest totalSum among the all mean values.
#include <cmath>
#include <cstdio>
#include <utility>
#include <vector>
#include <iostream>
#include <climits>
#include <limits>
#include <algorithm>
#include <iostream>
#include <set>
#include <fstream>
#include <istream>
#include <ostream>
#include <queue>
#include <bitset>
#include <map>
#include <stack>
#include <ctype.h>
using namespace std;
#define ll long long
ll calcualteSum(vector<double> m, vector<double> s){
// Sorting both meansVector(m) and valuesVector(s)
sort(s.begin(), s.end()); sort(m.begin(), m.end());
// Creating sumVector from s. Each index represents the summed values until the index.
vector<double> summedS(s.size()); summedS[0] = s[0];
for(int i=1;i<s.size();i++) summedS[i] = summedS[i-1]+s[i];
double minVal = 1.7e300;
for(auto currentM : m) {
// Find the location of the currentMean in s.
// This allows us to find which values are bigger and which are them are smaller.
int locationOfCurrentM = lower_bound (s.begin(), s.end(), currentM) - s.begin();
double smallerSum, biggerSum;
// Finding the sum of values that is smaller and bigger than currentM
if(locationOfCurrentM == 0) smallerSum = 0, biggerSum = summedS[s.size()-1];
else smallerSum = summedS[locationOfCurrentM-1], biggerSum = summedS[s.size()-1] - summedS[locationOfCurrentM-1];
// We know that sum of the smaller values will be smaller than currentM*locationOfB.
// Therefore, we can find the sum by simply extracting smallerSum from currentM*locationOfB
double smallerMainSum = currentM*locationOfCurrentM - smallerSum;
// We know that sum of the bigger values will be bigger than currentM*locationOfB.
// Therefore, we can find the sum by simply extracting (s.size()-locationOfB) * b from biggerSum.
double biggerMainSum = biggerSum - (s.size()-locationOfCurrentM)* currentM;
minVal = min(minVal, smallerMainSum+biggerMainSum);
}
return round(minVal);
}
int main() {
int n;
vector<double> means, values;
scanf("%d", &n);
for(int t,i=0;i<n;i++){
scanf("%d", &t);
double sum = 0, a;
for(int j=0;j<t;j++){
scanf("%lf", &a);
values.push_back(a);
sum += a;
}
means.push_back(sum/(double)t);
}
ll output = calcualteSum(means, values) + 1;
printf("%lld", output);
return 0;
}
Question Eight -Bekci and His Machine Learning Experience 2 - O(N•M•M)
The question asks us to find the all submatrixes with the biggest sum. The crucial thing is storing the locations. Because we need to change those submatrixes.
For solving this question, we should have 2 pointers to the columns of the matrix. Each of them starts from index 0. We need to increase pointer-2 until the last column. When pointer-2 hits the last column. We increment the pointer-1 and start pointer-2 from the location pointer-1. While we moving with those pointers. We need to fill an array with numbers in those columns.
For each movement of pointers, we will call Kadane’s Algorithm. This will give us the maximum submatrix.
#include <cmath>
#include <cstdio>
#include <utility>
#include <vector>
#include <iostream>
#include <climits>
#include <limits>
#include <algorithm>
#include <iostream>
#include <set>
#include <fstream>
#include <queue>
#include <bitset>
#include <map>
#include <ctype.h>
#define ll long long
using namespace std;
struct Node {
int upLoc, downLoc, leftLoc, rightLoc;
};
vector<Node> gLocations;
ll globalSum = -LONG_LONG_MAX;
void findMaximumSum(vector<ll> &array, int left, int right){
ll currentSum = 0;
Node currentLocation = Node();
currentLocation.leftLoc = left, currentLocation.rightLoc = right, currentLocation.upLoc = 0;
for (int i=0;i<array.size();i++) {
currentSum += array[i];
currentLocation.downLoc = i;
if(currentSum < 0) currentLocation.upLoc = i+1, currentSum = 0;
if(currentSum == globalSum) gLocations.push_back(currentLocation);
if(currentSum > globalSum){
gLocations.clear();
gLocations.push_back(currentLocation);
globalSum = currentSum;
}
}
}
void maxSumSubmatrix(vector<vector<ll>> &matrix) {
// Column-1 pointer
for(int i=0;i<matrix[0].size();i++) {
vector<ll> sumArray(matrix.size(), 0);
// Column-2 pointer
for (int j = i; j < matrix[0].size(); j++) {
// Increamenting the sumArray.
for (int k = 0; k < matrix.size(); k++) sumArray[k] += matrix[k][j];
// This function runs the Kadane's Algorithm.
findMaximumSum(sumArray, i, j);
}
}
}
void changeMatrix(vector<vector<ll>> &matrix){
for (auto &gLocation : gLocations) {
int u = gLocation.upLoc,d = gLocation.downLoc;
for(int i=u;i<=d;i++){
int l = gLocation.leftLoc, r = gLocation.rightLoc;
for(int j=l;j<=r;j++) matrix[i][j] = globalSum;
}
}
}
void transposeWrite(vector<vector<ll>> &m){
for(int i=0;i<m[0].size();i++){
for(int j=0;j<m.size();j++){
printf("%lld ", m[j][i]);
}
printf("\n");
}
}
int main(){
int t;
scanf("%d", &t);
while(t--){
gLocations.clear();
globalSum = -LONG_LONG_MAX;
int n,m;
scanf("%d%d",&n,&m);
vector<vector<ll>> matrix(n,vector<ll>(m,0));
for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%lld", &matrix[i][j]);
maxSumSubmatrix(matrix);
// Change element of the matrix with maximum sum submatrixes.
changeMatrix(matrix);
// Print the transpose of the matrix.
transposeWrite(matrix);
if(t) printf("--\n");
}
return 0;
}