amrSamir's blog

By amrSamir, 11 years ago, In English

Hello from Egypt!

Welcome to 2013-2014 CT S01E010: Codeforces Trainings Season 1 Episode 10. The training duration is 5 hours, to be held on Wednesday, 13th of November, 16:10. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be available as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

The registration will be available on the Gym page and will be opened until the end of the training. Be careful registering team: please, choose only whose members who will take part in the contest.

This time it is special, because this problem set will be the Egyptian Collegiate Programming Contest — ECPC 2013. The theme of this contest is Bakkar, a famous cartoon character from one of the first and most memorized cartoons in Egypt!

This contest is the result of the hard work of many people: Islam Al-Aarag (islam-al-aarag), Mostafa Saad (mostafa.saad.fci), Amr Mahdi (amr_mahdi), Amr Mesbah (Amr_Mesbah), Ahmed Abd Rabo (ahmed.abdrabo), Ahmed Hamza (Hamzawy), Ahmed Thabet (ahmed_thabet), Yasser Yehia (Yasseryahia) and me (amrSamir). Special thanks to Ahmed Aly (ahmed_aly) for his help.

This is the first time to publish the ECPC contest online and we really appreciate your feedback on the contest.

We hope you will enjoy the contest, as we enjoyed making it.

EDIT: An excellent editorial by Xellos can be found here.

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

| Write comment?
»
11 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Trailer song of the cartoon.

»
11 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Don't let the problems affect on loving BAKAR :)

»
11 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Good to see that the problems are un-googlable. But I found the scoreboard already :D

Well, the problems are expected to be reasonably easy, since it's quite a local-level contest. It's that way most of the time in these trainings, and it's usually solved by adding hard CodeJam problems...

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Just FYI, there are 12 problems, 8 only were solved in the contest, and the first solved 7.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    I think the problems are interesting, original and not that easy. Some problems are harder than Codeforces Div2 E problems. Sometimes this contest is harder than the regional contest itself.

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

      In reply to both comments above:

      The top teams that do these trainings are kind of on a different level, though. The difficulty I'm talking about is "how much trouble the best team competing would have", which is usually very different here than in the local contest.

      I don't really hope to solve more than those 7 problems, but there may be people who do. That's whom the additional problems are for.

»
11 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I got WA1 3 times because I printed space at the end of line >(

»
11 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Basis of an editorial: here

More to be added eventually.

»
11 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Can we get data set of today contest?

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm getting "judgement failed", what about this?

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how can i see the testcases? atleast the one i failed or i carnt?

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    In Gym, you can't see the testcases (or others' solutions) of a problem until you solve it.

»
11 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
#include<algorithm>
#include<vector>
#include<iostream>
#include<cstdio>
#include<stdio.h>
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define REP(i,n) for(i=0;i < n;i++)
#define pll pair<long long, long long>
#define DEBUG 0
typedef long long ll;
using namespace std;
const long maxn = 100000, maxm = 100000;
const long long  maxv = 100000000;
long n, m;
long ii, t;
struct sEdge {
	int a, b, w;
	bool operator<(const sEdge &A) const {
		return w < A.w;
    }
};
vector< sEdge > edges;
ll pre[2*maxn+3], sum[2*maxn+3], valueArr[2*maxn+3], root[2*maxn+3];
long solve(){
    long i;
    long nPart = n, nsize = n;
    REP(i,2*n)  pre[i] = -1, sum[i] = -maxv, root[i] = -1;
    for(int it = 0; it < edges.size(); it++){
        long u,v,w;
        u = edges[it].a;
        v = edges[it].b;
        w = edges[it].w;
        vector<long> fauv;
        while (root[u] >= 0){
            fauv.pb(u);
            u = root[u];
        }
        while (root[v] >= 0){
            fauv.pb(v);
            v = root[v];
        }
        if (u == v) continue;
        nPart--;
        valueArr[u] = -pre[v]*w;
        valueArr[v] = -pre[u]*w;
        valueArr[nsize]  = 0;
        pre[nsize] = pre[u]+pre[v];
        pre[u] = nsize;
        pre[v] = nsize;
        while (!fauv.empty()){
            root[fauv[0]]=nsize;
            fauv.erase(fauv.begin());
        }
        root[v] = nsize;
        root[u] = nsize;
        nsize++;
        if (nPart == 1) {
            sum[nsize-1] = 0;
            break;
        }
    }
    REP(i,n){
        if (sum[i] != -maxv) continue;
        vector<long> trade;
        long u = i;
        while (sum[u] == -maxv){
            trade.insert(trade.begin(),u);
            u = pre[u];
        }
        long j;
        for (j=0;j < trade.size();j++)
            sum[trade[j]]=sum[pre[trade[j]]]+valueArr[trade[j]];
    }
    cout << "Case " << ii+1 << ":" << endl;
    REP(i,n)
        if ((ii == t-1)&&(i==n-1))
            cout << sum[i];
        else
            cout << sum[i] << endl;
    return 1;
}
int main(){
    freopen("road.in","r",stdin);
    scanf("%d",&t);
    REP(ii,t){
        scanf("%d%d", &n, &m);
        long i;
        edges.clear();
        REP(i,m){
            sEdge u;
            scanf("%d%d%d", &u.a, &u.b, &u.w);
            u.a--; u.b--;
            edges.pb(u);
        }
        sort(all(edges));
        solve();
    }
    return 1;
}

Why do my code get Runtime error on test 1? Plzz help me out!!! (Ps: I did run Xellos's code and got the result)

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

    Maybe because you return 1. Signal 1 seems to mean "you closed the terminal while the process was still running in it". A program must exit with signal 0, any other will just lead to RE.

    You should probably read some info about how to write programs acceptable by contest sites...