Hasan0540's blog

By Hasan0540, 2 weeks ago, In English,

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!

Read more »

 
 
 
 
  • Vote: I like it  
  • +54
  • Vote: I do not like it  

By Hasan0540, history, 6 months ago, In English,

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!

Read more »

Announcement of 2017 PSUT Coding Marathon
 
 
 
 
  • Vote: I like it  
  • +35
  • Vote: I do not like it  

By Hasan0540, 9 months ago, In English,

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!

Read more »

Announcement of 2017 Hackatari Codeathon
 
 
 
 
  • Vote: I like it  
  • +52
  • Vote: I do not like it  

By Hasan0540, history, 14 months ago, In English,

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!

Read more »

 
 
 
 
  • Vote: I like it  
  • +82
  • Vote: I do not like it  

By Hasan0540, history, 14 months ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +109
  • Vote: I do not like it  

By Hasan0540, history, 19 months ago, In English,

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.

Read more »

Announcement of 2016 PSUT Coding Marathon
 
 
 
 
  • Vote: I like it  
  • +37
  • Vote: I do not like it  

By Hasan0540, 2 years ago, In English,

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;
for (int mask = 1; mask < (1 << n); ++mask){
	int sum = 0, size = 0, minVal = 1e9;
	for (int i = 0; i<n; ++i)
		if((mask>>i)&1){
			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){
	add -= remove[i];
	int curDigit = (digits[i] - '0' + add) % 10;
	int need = (10 - curDigit + D) % 10;
	add += need;
	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)

Read more »

 
 
 
 
  • Vote: I like it  
  • +63
  • Vote: I do not like it  

By Hasan0540, 3 years ago, In English,

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

RTE: http://ideone.com/7UNoVJ

OK: http://ideone.com/fOWbj3

Thanks!

Read more »

 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it