### Hasan0540's blog

By Hasan0540, 4 months ago, ,

A. Two Fashillows

If w + m ≤ d or w > d, we print "good luck". Otherwise, we print "see you next semester".

Complexity: O(1).

Solution

B. Two Palindromes

We can always build a palindrome if we have at most one letter with odd frequency. Since both strings are palindromes, all letters have even frequencies, except he middle letter when the length of the string is odd. So the answer is NO only when both strings are of odd length and the middle letters are different.

Complexity: O(|s1| + |s2|) for reading, and O(1) to check.

Solution

C. Forest (A) — Egg

The number of trees is equal to the number of components in the graph. Initially, the number of components is n. Adding an edge will always decrease the number of components by 1 as the constructed graph doesn't have cycles.

We add an edge at node i if there's a value greater than valuei to its left. So we can solve the problem by reading values and keeping the maximum value updated. We add an edge when currentValue < maxValue and decrease the answer.

Complexity: O(n).

Solution

D. Forest (B) — Chicken

If we have multiple trees in the forest, it is clear that the value at the root of the second tree must be greater than all values before it, otherwise it will have a parent.

Also, removing the root of a tree produces zero or more trees, the root of each of these trees must have a value greater than all values before it other than the removed root.

We can build the array as follows:

Let the sizes of the trees be s1, s2, ....

Pick the first tree, assign the value s1 to the root, and give each child v of the root a consecutive range of values of size equal to the subtree at v. Then recursively, a child will be assigned to the maximum value in the given range, and the remaining range will be diveded over its children.

So the first tree is built using values [1, s1], the second tree using values [s1 + 1, s1 + s2], and so on.

Complexity: O(n).

Solution

E. Forest (C)

To increase the number of trees, some nodes must become roots. Roots don't have parents, so the values of these roots must be greater than all values to their left.

Can we make node i a root by removing at most one element before it? If vi is greater than all values before it, we don't need to remove any element as i is already a root. Otherwise, we can make i a root if and only if it has only one value greater than it before i. Removing that value will leave i without a parent.

So we need the maximum value and the second maximum value before an element to decide if we can make it a root or not. And in case we can, we also need the indices of these maximums to know which element should be removed.

We can count for each index j the value fj, the number of indices that need j to be removed to become a root. We also decrease fj by one if j is a root, as we will lose one root by removing j.

For each starting element of a subarray i, we increment the end of the subarray j while updating the array f. As values in f are initially 0 or -1, then only increase, it is easy to keep the maximum value in f while increasing some elements.

Complexity: O(n2).

Solution

F. World Mug (A)

We can simulate the process recursively or using two vectors and swapping them. The first vector will represent the strengths of the teams in the current round, and the second vector will represent the winners of the current round.

Complexity: O(n).

Solution

G. World Mug (B)

Let k be the height of the tree, that is, 2k = n.

The winning team of the tournament will face k teams and beat them all, therefore contributing to the answer by k × s1st.

The second-place team will also face k teams, winning k - 1 times and losing the last one. This will contribute to the answer by (k - 1) × s2nd - s2nd for a total of (k - 2) × s2nd.

Through our previous observation of how much each team's individual strength contributes to the final answer, it is clear now that the first-place team should be assigned to the team with the maximum strength, and the second-place team to the team with the second maximum strength.

The next two teams in 3rd and 4th place each will win k - 2 times and lose once. 5th to 8th place will win k - 3 times and lose once, and so on. We should keep assigning places in decreasing order of strength for these teams.

Complexity: O(nlogn), as we need to sort the strengths.

Solution

H. Cylindrical Graphs

Note that in a cylinder, the degree of each node is 3. If we choose one of the vertical edges, mark one end in blue and the other in red, then do a multi-source BFS marking each adjacent node with the color if its parent, we will get one cycle colored in blue and the other colored in red! Check the following animated GIF:

Since we don't know if an edge is vertical or not, we can try all of the three edges of a node, if one of them produced two cycles of size , and those two cycles are connected using vertical edges, then we found a solution. Note that sometimes you need to reverse one of the cycles to align the vertical edges.

Complexity: O(n).

Solution

I. Tree Generators

The main idea is to build a weighted tree that contains only the nodes mentioned in the operations and/or the queries, plus few other nodes that can be the result of the LCA of some pairs.

We will keep a sorted list of the IDs that will be needed in the operations and the queries.

Each time we activate a generator, we know the number of nodes and the range of IDs that will be generated, if we number the required nodes of each generator in DFS order and sort them, then during our LCA operations we may need those nodes or the LCA of some consecutive nodes. So we add all these nodes to a weighted tree, where the weight of an edge is the number of edges between the two nodes. To find the weight of an edge, we can initially build a sparse table for each generator and store the depths of the nodes. We need the sparse tables for finding the LCAs too.

Finally, we build a sparse table for the weighted tree to answer the queries.

The total number of nodes in the weighted tree won't exceed 2 * (k + q). Multiplied by 2 because we add the LCA of consecutive nodes in DFS order.

Complexity: O(TlogT + NlogN), where T = 2 * (k + q) and N is the total number of nodes in all generators.

Solution

J. Complete the Square

Drawing a side of a square that already has 3 drawn sides will get us one point and allow us to draw another edge.

Count for each square the number of missing sides, put all squares with 1 missing side in a queue and process them one by one by filling the missing side, increasing the answer by 1, and decreasing the number of missing sides of the adjacent square by 1. If the adjacent square now has one missing side, add it to the queue.

Be careful with your implementation. It is possible for an edge to complete two squares at the same moment. If the other square is already in the queue, you should not process it or increase the answer by 1.

Complexity: O(R × C).

Solution

•
• +45
•

By Hasan0540, 4 months ago, ,

Hello Everyone!

The problem set of PSUT Coding Marathon 2018, which was held last Saturday, will be available in Codeforces Gym tomorrow, May/16/2018 19:35 (Moscow time).

Previous problem sets:

2017 PSUT Coding Marathon

2016 PSUT Coding Marathon

2015 PSUT Coding Marathon

Contest length is 4 hours, with 10 problems to solve. Difficulty of the contest is similar to Codeforces Div.2 rounds. Contest is more suitable for individual participation.

Problems were prepared by me and linkinu. Thanks to Maram Tuffaha for reviewing the statements and to Vendetta. for preparing the tests of one of the problems.

UPD: Contest starts in less than 15 minutes.

Please note that the memory limit for problem C should be 4 MB according to the problem statement. However, I couldn't set it to 4 MB because Java solutions won't run (initial heap size > 4). The memory limit is there to make you think a little bit more and write less.

UPD1: As Codeforces was down, the contest will start at May/16/2018 19:35 (Moscow time).

Good luck and have fun!

UPD2: Tutorial

Announcement of 2018 PSUT Coding Marathon

•
• +57
•

By Hasan0540, 4 months ago, ,

Hello again,

Thank you for participating. It was a great experience for me and I learned a lot. Hope you learned something as well! I'll try to avoid the issues some of you complained about, next time.

The tutorial of problems [A-C] was written by Motarack, [D-E] by Light, and all were reviewed by 1am. Thank you guys!

Solution: https://ideone.com/EEORpR

•
• +59
•

By Hasan0540, 5 months ago, ,

Hello everyone!

I would like to invite you to participate in Codeforces Round #480 (Div. 2), it will take place tomorrow, May/08/2018 18:05 (Moscow time).

The round consists of 6 problems and you will have two hours to solve them.

The problems were prepared by me with great help from linkinu and 1am. I would like to thank KAN for his great efforts in reviewing the problems and for his suggestions, it is really amazing to see the work done behind every round. Also thanks to Tommyr7, Livace and mike_live for testing the problems, and to arsor for translating the statements into Russian.

This is my first round on Codeforces, I hope that you will find some interesting problems for you.

Note that the round is rated for everyone with rating below 2100.

Good luck and have fun!

UPD: Congratulations to the winners:

Div. 2:

Div. 1+2:

UPD1: Editorial

•
• +314
•

By Hasan0540, 10 months ago, ,

Hello Everyone,

The problem set of 2017 ACM Jordanian Collegiate Programming Contest will be available in Codeforces Gym on Saturday, Nov/11/2017 18:00.

The problems were prepared by Hasan0540, justHusam, Alaa_AbuHantash, and Maram Tuffaha. Thanks to ahmed_aly for reviewing the statements and giving some suggestions.

Note that your solution should read the input from file and write to the standard output. You can find the input file name below the title of the problem.

Hope you like the problems. Any feedback is appreciated!

Good luck!

•
• +54
•

By Hasan0540, history, 16 months ago, ,

Hello Everyone,

The problem set of the 2017 PSUT Coding Marathon will be available in Codeforces Gym today at 17:00.

You will have 10 problems and 5 hours to solve them (prepared to be an individual contest).

The problem set was prepared by Hasan0540, Vendetta., SaMer, and Maram Tuffaha.

UPD: Please note that the description of part B (and C) of each problem depends on part A.

Good luck!

Announcement of 2017 PSUT Coding Marathon

•
• +35
•

By Hasan0540, 19 months ago, ,

Hello Everyone,

The problem set of the 2017 Hackatari Codeathon will be available in Codeforces Gym tomorrow, Monday Feb/13/2017 19:00.

You will have 9 problems and 5 hours to solve them. However, the problems' difficulty is similar to Div.2 contests, so you might only need half of that time to solve them.

The problem set was prepared by Hasan0540, linkinu, and Maram Tuffaha.

Thanks to AmrMahmoud and Deadwing for testing the problem set.

Good luck!

Announcement of 2017 Hackatari Codeathon

•
• +52
•

By Hasan0540, history, 2 years ago, ,

Hello Everyone,

The problem set of 2016 ACM Amman Collegiate Programming Contest will be available in Codeforces Gym on Tuesday, Sep/27/2016 10:00.

The problem set was prepared by 2Nodes, SaMer, and AU.Bahosain.

Thanks to AmrMahmoud for testing one of the problems (in case he participated), and to Rezira for helping me preparing the contest on Polygon.

I hope more orange and red coders will participate than in the last contest I've prepared :(

Good luck!

•
• +82
•

By Hasan0540, history, 2 years ago, ,

Hello Everyone,

ACM SCPC 2015 (Syrian Collegiate Programming Contest) problem set will be available in Codeforces Gym on Sunday, Sep/11/2016 21:00.

The problem set was prepared by 2Nodes, hoa_2alk_fain, SaMer, au.bahosain, Fegla, Nicole Hosh, and Mohammad Asaad.

Thanks to AmrMahmoud, AmirNasr, eagle93, TahaMahmoud, ghooo, osamahatem, and hossameldeenfci for testing.

Good luck, and I hope you can enjoy the problem set as much as we enjoyed creating it.

Update: The contest was shifted 11 hours (Sunday, Sep/11/2016 21:00) in order for it not to intersect with the Mirror of Bubble Cup Finals.

•
• +109
•

By Hasan0540, history, 2 years ago, ,

Hello Competitors,

I would like to invite you all to participate in the follow up of Third Coding Marathon of Princess Sumaya University for Technology. The contest was originally held on April 30, and it will launch in Codeforces Gym tomorrow; May/07/2016 10:00.

The problems were prepared by 2Nodes, SaMer, and Dr. Ibrahim (earlgray).

The contest will be held with extended ACM ICPC rules. You'll be given 14 problems to solve within 270 minutes. Some of the problems have two parts (A and B), where A is easier than B, and the statement of B depends on the statement of A. The difficulty of the contest is similar to Codeforces Div. 2 contests.

Good luck to you, and I hope you can enjoy the problemset.

Note: Don't forget to use fast I/O methods.

Announcement of 2016 PSUT Coding Marathon

•
• +37
•

By Hasan0540, 3 years ago, ,

#### A. Who Is The Winner

We can keep the name of the winner team while reading the input, if the current team solved more problems than the current winner, or solved the same number of problems but with less penalty, we set the current team as the winner:

cin >> curTeam >> curSolved >> curPenalty;
if (curSolved > winSolved || curSolved == winSolved && curPenalty < winPenalty){
winTeam = curTeam;
winSolved = curSolved;
winPenalty = curPenalty;
}


Complexity: O(N)

#### B. Rock-Paper-Scissors

Let's start with the brute force solution, we can try all possible pairs (X, Y), if we know X and Y, then Z = N - X - Y.

The number of times Bahosain wins depends on the number of Scissors in the first X rounds, the number of Rocks in the next Y rounds, and the number of Papers in the last Z rounds.

We can find the number of times he will lose in a similar way.

int res = 0;
for (int X = 0; X <= N; ++X)
for (int Y = 0; Y <= N; ++Y){
int winCount = countInRange(0, X - 1, 'S')	 //     Rock > Scissors
+ countInRange(X, X + Y - 1, 'R')   //    Paper > Rock
+ countInRange(X + Y, N - 1, 'P');  // Scissors > Paper
int loseCount = countInRange(0, X - 1, 'P')      //     Rock < Paper
+ countInRange(X, X + Y - 1, 'S')  //    Paper < Scissors
+ countInRange(X + Y, N - 1, 'R'); // Scissors < Rock
if(winCount > loseCount)
++res;
}


This solution works in O(N3) if the function countInRange works in O(N), we can improve it using prefix sum (cumulative sum).

Create 3 arrays: rockSum, paperSum, and scissorsSum. We set rockSum[i] = 1 if there is a rock at index i. We fill the other two arrays in a similar way.

After calculating the prefix sums, we can modify countInRange to work in O(1). For example, to find the number of rocks in a range [L, R], we can use rockSum[R] - rockSum[L - 1] (watch out when L > R or L = 0).

Complexity: O(N2)

#### C. Street Lamps

If we don't have any asterisk *, then for each 3 dots we need one lamp, so the answer is , where D is the number of dots.

We can solve the problem by creating a copy of the given string, and for each asterisk in the first string we place an asterisk at it's adjacent indices in the second string. So if the given string is ...**.., the second one will be ..****..

After that, we count the number of dots in each block of consecutive dots and find the number of needed lamps for that block.

Complexity: O(N)

#### D. Alternating Strings

This problem can be solved using dynamic programming.

Let dp[i] be the minimum number of partitions needed for the suffix that starts at i, we try all possible cuts [i...j]. A cut is possible if i = j, or the substring S(i...j) is not alternating and j - i + 1 ≤ K.

dp[s.length()] = 0;
for (int i = s.length() - 1; i >= 0; --i){
bool isAlter = true;
dp[i] = 1e9;
for (int j = i; j - i + 1 <= k && j<s.size(); ++j){
if (j>i && s[j] == s[j - 1])
isAlter = false;
if (i == j || isAlter == false)
dp[i] = min(dp[i], 1 + dp[j + 1]);
}
}


Finally, the answer will be dp[0] - 1, because dp[0] represents the number of partitions, not cuts.

Complexity: O(NK)

#### E. Epic Professor

Let M be the maximum mark of a student, then the maximum possible bonus marks will be 100 - M.

We can find the maximum mark in one loop, and then count the number of students such that Markstudent + 100 - M ≥ 50.

Complexity: O(N)

#### F. Travelling Salesman

We can greedily keep adding the edges with the minimum length to the graph until we have one component, then the answer is the length of the last added edge.

This can be done using disjoint-sets data structure. The number of components in the graph will decrease by 1 after merging two components.

Note that the answer is the same as the maximum length of an edge in a minimum spanning tree.

Complexity: O(MlogM)

#### G. Heavy Coins

We need to find the maximum size of a subset such that the sum of it's values sum ≥ S and the minimum value in the subset is greater than sum - S.

Since N is small, we can try all possible subsets recursively, or iteratively using a bitmask.

int res = 0;
int sum = 0, size = 0, minVal = 1e9;
for (int i = 0; i<n; ++i)
sum += val[i];
++size;
minVal = min(minVal, val[i]);
}
if (sum >= s && minVal > sum - s)
res = max(res, size);
}


Complexity: iterative solution O(2NN), recursive solution O(2N)

#### H. Bridges

After removing bridges from the graph, we will have one or more components with no bridges.

Imagine each component as one big node, and connect those big nodes using the removed bridges:

The resulting graph is a tree, each edge in this tree is a bridge in the original graph, we need to remove the maximum possible number of bridges by adding one edge.

Adding an edge between two nodes will remove a number of bridges equal to the number of edges on the unique path between them, so we need to remove the longest path in this tree.

The final answer is the number of bridges in the graph minus the longest path in the tree.

Mapping each component into one node can be done using disjoint-sets. It is possible to solve the problem without actually building the tree, check I_love_Tanya_Romanova's comment.

Complexity: O(N + M)

#### I. Bahosain and Digits

We can try all possible K, we also try all possible digits D, that is we want to make all digits in the string equal to D.

To check if that's possible, we add the needed value to the first digit to make it equal to D (mod10), we should add the same value to the next K - 1 digits, some contestants did this using segment tree and got TLE.

To do this efficiently, we can keep a variable add that represents the total added value, and an array remove to mark that when we are at index i, we should subtract remove[i] from add, please check the code if that wasn't clear:

int add = 0, remove[251] = {};
for (int i = 0; i + k <= digits.length(); ++i){
int curDigit = (digits[i] - '0' + add) % 10;
int need = (10 - curDigit + D) % 10;
remove[i + k] = need;
}
// after that we need to check that we won't need more
// operations to make the last K digits equal to D.


Complexity: O(10|digits|2)

#### J. Candy

Let's create two frequency arrays, one for ages and one for packet sizes, after that we can match ages with packet sizes greedily.

We keep matching the minimum age i with the minimum possible packet size j such that freqAge[i] ≤ freqSize[j]. Note that we can't use sizes less than j after that because the problem says that older students must get more candies.

bool yes = true;
for (int age = 5, size = 1; age <= 15; ++age){
if(freqAge[age] == 0)
continue;
while (size <= 50 && freqAge[age]>freqSize[size])
++size;
if (size == 51){
yes = false;
break;
}
++size;
}


Complexity: O(15 + 50)

#### K. Runtime Error

Many contestants got runtime error in this problem because of dividing by zero.

We can solve the problem in O(N) using an array that tells us if we have some number or not.

bool have[100001] = {};
int X = 1e9, Y;
for (int val, i = 0; i<n; ++i){
cin >> val;
if (val>0 && k%val == 0 && have[k / val]){
int curX = min(val, k / val);
int curY = k / curX;
if (curX<X){
X = curX;
Y=curY;
}
}
have[val] = true;
}


There are other solutions that use frequency arrays or binary search. Be careful in case K is a square number like 25 and there is one 5.

Complexity: O(N)

#### L. Alternating Strings II

Let's go back to the solution of problem D, notice that once the substring is not alternating, it won't be alternating again, so we just choose the minimum value in the range [x, i + k - 1], where x is the first position after i such that S(i...x) is not alternating. In other words, Sx - 1 = Sx.

We can use segment tree to get the minimum value of dp in the required range.

Complexity: O(NlogN)

•
• +63
•

By Hasan0540, 4 years ago, ,

Can anyone explain why does the first code get Runtime Error?

Thanks!

•
• -1
•