Hello,

Syrian Collegiate Programming Contest 2014 (SCPC) was held as a multisite contest in both Damascus and Latakia between 21st and 23rd of September , I think it's the first ACM contest which take place in two sites in two different cities!

Forty four teams from eleven universities participated in the contest beside three other unofficial teams

I've uploaded the contest to GYM and I invite you to participate in this contest which I choosed this time for it , I hope I chose the time which suits as many coders as possible.

most problems may be easy for yellow and red coders but at least one problem will interest you.

it's the first time that I upload a contest to GYM so I hope everything is technically ok!

if you have coach rights please don't enter the contest before it starts.

By the way, today is the third day of Eid al-adha festival so Happy feast to all Muslims :D

**UPD:** Contest is finished , thanks for participation and Cogratulations to winners.

problem H is a traditional dynamic programming but allowing negative values tricked a lot of contestants because they didn't initialize the corner values of dp to -INF (i.e dp[i][0]=-INF and dp[0][i]=-INF)

problem I is very simple implementation problem the fault of many participants is not considering the case when there's no 5 different letters in the song.

congratulations Muslims!!!

Eid Mubarak kingofnumbers :)

Certainly it's not the first. NEERC used for years to be held in St. Petersburg and Barnaul. I'm almost sure there have been earlier cases, though.

Also, as I know, SEERC is held in Vinnytsia and Bucharest.

And NEERC is held in St. Petersburg, Barnaul, Tbilisi and Tashkent:)

The Latin America Regional Contest is held in Argentina, Bolivia, Brazil, Chile, Colombia, Cuba, Mexico, Peru, Dominican Republic and Venezuela. I believe the qualification rules are different for the Brazilian site and the rest of them, though.

What is the solution for problem C? Can someone also post their code for that problem?

My idea was to find the maximum possible amusement possible uptil

i^{th}item, but I am not sure how we can also obey the given rules simultaneously.My code

Can you explain this -

`FOR(h, 1, n) {`

`h`

is amount of backpacks. If you take`h`

backpacks, you need at least`h`

items of each type you put in. Types — pair(amount, type id) — are sorted in`items`

w.r.t their quantity.`amuse[i]`

is a sum of amusement of types from`i`

to`n`

in`items`

.Can anybody help me please? With problem c (giveaways) I got a time limit exceeded with this code, and I don't really see how to improve my algorithm complexity.

Can somebody provide solution to B?

I don't know whether it will be of any help. But here is My Code.

First you need to calculate sum of all the numbers, then check if it's divisible by n. if it's not divisible then there is no way to unlock the door. if it's divisible then our goal is to build sum/n for each row.

Now fix one slider for example first one. then our goal for each row change to goal[i]=goal[i]-slider[0][i].

There are n different rotations for last slider and goal.

slider[3][0]->goal[0] , slider[3][1]->goal[1] , ... , slider[3][n-1]->goal[n-1].

slider[3][0]->goal[1], slider[3][1]->goal[2], ... , slider[3][n-1]->goal[3][0].

slider[3][0]->goal[2], slider[3][1]->goal[3], ... , slider[3][n-1]->goal[3][1].

.

.

.

We calculate all of these n rotations then we calculate sum of second and third slider for each of these rotations. for example for the first rotation :

Sum_of_second_third[0] = goal[0]-slider[3][0];

Sum_of_second_third[1] = goal[1]-slider[3][1];

and so on.

For reducing time complexity of checking to o(1), we need to hash Sum_of_second_third for all of these n rotations.

Now we can build all of n rotations for second and third slider and calculate sum for each of them.

slider[1][0]->slider[2][0] , slider[1][1]->slider[2][1] , ... , slider[1][n-1]->slider[2][n-1].

slider[1][0]->slider[2][1] , slider[1][1]->slider[2][2] , ... , slider[1][n-1]->slider[2][0].

For firs rotation :

Sum[0] = slider[1][0]+slider[2][0];

Sum[1] = slider[1][1]+slider[2][1];

Sum[2] = slider[1][2]+slider[2][2];

and so on.

We need to hash these numbers too.

Finally we need to calculate n rotations of n rotations of slider 1 and 2 !!!

For first rotation :

slider[1][0]->slider[2][0] , slider[1][1]->slider[2][1] , ... , slider[1][n-1]->slider[2][n-1].

slider[1][1]->slider[2][1] , ... , slider[1][n-1]->slider[2][n-1], slider[1][0]->slider[2][0].

With a little trick you can get new hash for each of these rotations. you just need to use binary search to check if this hash exist in hash of Sum_of_second_third. time complexity of this solution is O(n^2 * log n).

Here is my code : B

People who didn't solve B. cannot view your submission. Can you post to a public link?

Sure, Here is my code : B

what if there is collision?

Looks like he is using 2 hash codes to reduce probability of collision.

Here is my solution for problem using hashing

first notice that the sum of all elements need to be divisible by n

if it is divisible than the required sum for each row is sum/n

now we want to know if a rotation exist so that all the rows have required sum. if we used meet in the middle we can first try get all possible rotations from the first two columns in o(n^2) by fixing the first column.

however to save it if we saved the vector as a hole we will get TLE so we need to hash it first and store it's hash value in a map

now the search part we do the same for the third and fourth cols we get a new vector v that we want to search if it exist in the map from part a

after getting the hash value of v notice that we can have the same vector in the map but with different start idx

example

saved :1 2 3 4 5

current: 3 4 5 1 2

so we need to do n rotation to the current vector and each time search if it exist.

accepted sol

There is a small mistake in the problem A. In the statements "The length of each string in the input will not exceed 1,000 letters", but there definitely are some tests where the length exceeds 1000 (but not 10000). Just in case)

I checked it and found that the correct constraint is 10000. I've added a broadcast about it, but I prefer authors will change the statements.

I'm very sorry about that , the statement and testcases are official so I didn't expect that there may be a mistake with constraints , but the organizers faced a problem just before the onsite contest begin forced them to change the official test cases for problem A , and maybe since there was no time before the contest start causing them to change it quickly making the mistake.

The statement has been fixed

Can anyone please tell me how to solve E ?

It can be solved using dp and basic game theory.(Sprague Grundy Theorem) Refer to my code. http://pastebin.com/kgtVMjn2

J: Why I was trying to read data from "bye.in"?

"...the fault of many participants is not considering the case when there's no 5 different letters in the song."

The problem says: "count the frequency of each character of the English letters [A-Z] in the given song", why should we count the frequency only for the letters in the song?

Also, one of the accepted solutions — O(n*m) — for problem A prints player2 for this simple test case:

Agreed about I.

How to solve G?

404 Not Found

So, I was trying to solve B using hashing.

I think the complexity of my solution is around O(n*n*logn). Is it too slow, because I got TLE using that.

How to solve problem A ? Will it be solve by bitmasking ?

Please, can anybody help me with problem C? I got a time limit exceeded, here's my code:

Complexity of your algorithm is O(N * N) for each test with N = 1e4.

thankx alot. I just realised I've tried the bad dp solution.

Please, can anybody help me? I got an "runtime error" with problem D, which seems a very simple problem at first. I don't rellay understrand where's the wrong ~~~~~

~~~~~

You mean problem F, right?

well, your solution is O(M), and M can be really huge(1e18), so even if your concept is right, your solution will TLE.

and here you're getting RE because your array has a size of just 100002, while as I said M can go larger than that.

Please, I need help on problem D,

I get an runtime error: Here is my source code:

what is the solution of G :Swell Foop can someone tell that,thanks

Nice problem set...

But I think the test cases for A don't cover some of the cases, for example I saw a some of the accepted solutions output "Player2", for this test case:

1

3

aa

bb

bb

2

ab

bb

while clearly the correct answer is player1.

How to solve problem A ... ? Any idea.. ?

does anyone have the link of the contest?

here it is