Блог пользователя amrSamir

Автор amrSamir, 10 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +68
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

Trailer song of the cartoon.

»
10 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

    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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

Basis of an editorial: here

More to be added eventually.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Can we get data set of today contest?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
#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)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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