kingofnumbers's blog

[GYM] Syrian Collegiate Programming Contest 2014
By kingofnumbers, 10 years ago, In English

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.

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

Comments Comments (39)
| Write comment?
»
10 years ago, # |
  Vote: I like it +10 Vote: I do not like it

congratulations Muslims!!!

→ Reply
»
10 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Eid Mubarak kingofnumbers :)

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

I think it's the first ACM contest which take place in two sites in two different cities!

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ith item, but I am not sure how we can also obey the given rules simultaneously.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My code

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain this -

      FOR(h, 1, n) {

      while(i < items.size() && items[i].st < h) i++;

        if(i == items.size()) break;

        ret = max(ret, h*(amuse[i]));
    }
      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can somebody provide solution to B?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

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

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 5   Vote: I like it +5 Vote: I do not like it

    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.

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

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

    3. 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.

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

    2. 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 :

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

    2. 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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell me how to solve E ?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 3   Vote: I like it -18 Vote: I do not like it

      I have a question on my mind I can't find the answer. taking the XOR between two independent games why can we assume that this number is a number which can the current state get it.

      in other words: let's the grandy numbers of some states when k = 2 are:

      0
      • 0

      ** 1

      *** 1

      **** 2

      ***** 0

      ******
      now if we want to calculate the grandy number of ****** and let's assume we want to choose * [**] **** why is the XOR between Grandy(*) ^ Grandy(****) equal to a state we can get it. I mean from the current state we can go to anther state equal to two. but in fact we are going to two independent games.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"...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:

1
3
aab
abb
acb
2
bxa
bya
→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

404 Not Found

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <time.h>
#define pi acos(-1.0)
#define E 2.71828182845904523536
#define  FOR(i,k,n) for(int i(k); i<n;i++)

#define M 10005
using namespace std;
map <int, int> items;
int nbrSacs,temp;
unsigned long long dpMatrix[M]; //dpMatrix[i] contains the sum of amusement of types 1,2...i
unsigned long long maxi;

int main(){

int t,n,m,c;
    cin>>t;
    FOR(k,0,t){
        int id;
        cin>>m>>n>>c;

        memset(dpMatrix,0,sizeof(dpMatrix));
        items.clear();
        FOR(j,0,m){
            cin>>id;
            items[id]++; //Item is a map which is in form " items[type]= numbers of items of that type"
        }


        maxi=0;
        FOR(i,1,n+1){
            FOR(j,i,n+1){
                if(i==j){
                    dpMatrix[i]=(i*i)%c;;
                    nbrSacs= items[i];
                    maxi=max(nbrSacs*dpMatrix[i],maxi);
                }
                else{
                    dpMatrix[j]=((j*j)%c)+dpMatrix[j-1];
                    nbrSacs=min(nbrSacs, items[j]);
                    maxi=max(maxi, nbrSacs*dpMatrix[j]);
                }
            }
        }
        cout<<"Case "<<k+1<<": "<<maxi<<endl;

    }

return 0;
}
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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 ~~~~~

#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <time.h>
#define pi acos(-1.0)
#define E 2.71828182845904523536
#define  FOR(i,k,n) for(int i(k); i<n;i++)
#define wh(i,k) while(i<k)
#define M 100002

using namespace std;

long long domino[M][2];

int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
long long m,n;
    memset(domino,-1,sizeof(domino));
        domino[1][0]=0;
        domino[1][1]=0;
        long long size=2;
    cin>>t;
    FOR(k,1,t+1){
        cin>>n>>m;
        if(domino[m][0] != -1)
            cout<<"Case "<<k<<": "<<domino[m][0]<<" "<<domino[m][1]<<endl;
        else{
            for(long long i=size; i<=m; i++){
                if(domino[i-1][0] == domino[i-1][1]){
                    domino[i][0]=domino[i-1][0]+1;
                    domino[i][1]=0;
                    cout<<domino[i][0]<<" "<<domino[i][1]<<endl;
                    size++;
                }
                else{
                    domino[i][0]=domino[i-1][0];
                    domino[i][1]= domino[i-1][1] + 1;
                    cout<<domino[i][0]<<" "<<domino[i][1]<<endl;
                    size++;
                }
            }
            cout<<"Case "<<k<<": "<<domino[m][0]<<" "<<domino[m][1]<<endl;

        }
    }





return 0;
}

~~~~~

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

does anyone have the link of the contest?

→ Reply