Форум Всеукраїнської інтернет-олімпіади NetOI

TheEvilOfTheDay написав:

От мені хотілось би дізнатись від журі декілька відповідей (але я розумію, що я їх не отримаю).

Мені от цікаво який в них стоїть проц? Pentium 1, чи що?
В мене перша задача максимальний тест проходить на проці 2.4Ггц, за 0.07с, а тут ТЛ на 0.34, тобто по співвдношенню це виходить приблизно 0.5Ггц на тестуючій машині.

Чи це так важко написати в умові не "без округлення", а "з максимальною точністю", враховуючи, що вже був такий випадок з Нейтером, в правилах не сказано, що я маю перечитати весь форум для участі в олімпіаді.

Чому неможна вимкнути сервер від мережі буквально на 80 * 6 * 1 * 30 сек = 14400 сек = 4 год (це вже якщо на кожну задачу по 30 тестів і ТЛ по 1 секунді), щоб протестувати рішення.
Чи серверу так краще думати, коли одночасно надсилають на онлайн перевірку?
При онлайн перевірці іноді різниця виходить в 5+ балів, чому тоді не ставиться найвища?

Якщо ж тестується розвязок на машині в 0.5Ггц, то можете пояснити, будь-ласка, яка в цьому мета? Привчити олімпіадників (у майбутньому розробників та кібернетиків) програмувати на ЕВМ? Навіть на всеукрі тестували на 2х ядерному проці.

Я просто не можу зрозуміти цих пунктів....

І чесно кажучи на одній з найкращих олімпіад, на мій погляд, ТопКодері на одних і тих самих тестах, программа працює приблизно в 5 разів швидше ніж на Core-2-Quad 2.5Ghz, 4.00GB RAM, тому можливо журі треба зробити якісь логічні висновки звідси?

Чому ж, отримаєте...
1. Для перевірки використовується потужна програмно-апаратна платформа, але спроектована таким чином, щоб відділяти повільні розв'язки від швидких. Ваше намагання знайти пропорційність між часом проходження РІЗНИХ тестів і частотою різних процесорів, ще й без врахування умов переврки недолуге.

2. Не важко. В цьому зауваженні є певний сенс. Але "без округлення" якраз і буде максимально можлива точність компілятора. Але , повторю, певний сенс в вашому зауваженні є.

3. Мережу вимкнути можна. Але тоді журі не зможе відлагодити тести. Воно в сервері не сидить. :-)

4. Різниця при жорстких тайм-лімітах вивнкає в випадку часу проходження теста "на грані". Але якщо врахувати, що час проходження теста виставлено в 2 ( а інколи і в 3) рази більший, ніж час кращого розв'язку, що його має журі то однозначно, тестований розв'язок повинен мати меншу кількість балів.

5. Мета одна. Навчити  учасників гарно думати, а не швидко топтатися по кнопках  на клавах швидких машин. Для майбутніх розоробників, як ви слушно відмітили, це ДУЖЕ корисна навичка.  ОСЬ ЧОМУ В НАШІЙ ОЛІМПІАДІ ТРИВАЛІ ТУРИ І ЖОРСТКІ ТАЙМ-ЛІМІТИ.
Те, що хтось робить не так... як уміють і розуміють, так і роблять. Там, найчастіше, головна мета - знайти чемпіона-самородка, який переможе на міжнародній оліпміаді, і це оправдано. У нас мета інша- створити умови, за яких цей самородок зможе навчитися бути самородком.

В этой теме про лампочки ничего толкового не сказано, потому расскажу свое решение(60/60).
Пусть f(i,j) это количество способов получить за i операций j включеных лампочек, если всего их N. Получим:
f(i,j)=f(i-1,j-1)*(n-j+1)+f(i-1,j+1)*(j+1)
Это верно, потому что мы можем либо зажечь одну лампочку, т.е. из f(i-1,j-1) перейти в f(i,j), но сделать это мы можем (n-j+1) способами, т.к. ровно столько лампочек не горело на предыдущем шагу, либо мы можем потушить одну лампочку, т.е. перейти из f(i-1,j+1) в f(i,j) ровно (j+1) способами.
Первым числом из ответа будет f(k,n).
Для второго числа следует заметить, что N переключений должны быть сделаны в первой половине, остальные же могут быть сделаны как в первой, так и во второй половине. Следовательно, k-n переключений могут быть сделаны как в левой, так и в правой половине. Не трудно убедиться, что второе число из ответа равно f(k,n)*2^(k-n), где операция ^ это возведение в степень.

Вот код:

#define _CRT_SECURE_NO_DEPRECATE
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <iterator>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <ctime>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
#define pb push_back
#define ppb pop_back
#define pi 2*acos(0.0)
#define mp make_pair
#define x first
#define y second
#define sqr(a) (a)*(a)
#define D(a,b) sqrt(((a).x-(b).x)*((a).x-(b).x)+((a).y-(b).y)*((a).y-(b).y))
#define pii pair<int,int>
#define pdd pair<double,double>
#define sz(x) int((x).size())
#define INF 1000000000
#define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define rep(i,n) FOR(i,1,(n))
#define rept(i,n) FOR(i,0,(n)-1)
#define L(s) (int)((s).end()-(s).begin())
#define C(a) memset((a),0,sizeof(a))
#define val(ch) (int)(ch)-(int)('0')
#define toch(a) (char)((int)(a)+(int)('0'))
#define VI vector <int>
#define ll long long
const int LN=50;
class lng
{
public:
    int n[LN+1];
    inline void tol(int a)
    {
        C(n); n[0]=1; n[LN]=a;
    }
    inline void toc(int a)
    {
        n[0]=1; n[LN]=a;
    }
};
inline lng operator +(const lng &a,const lng &b)
{
    lng res; C(res.n);
    int len=max(a.n[0],b.n[0]);
    FORD(i,LN,LN-len+1)
    {
        int m=res.n[i]+a.n[i]+b.n[i];
        res.n[i]=m%10000; res.n[i-1]=m/10000;
    }
    (res.n[LN-len]!=0)?res.n[0]=len+1:res.n[0]=len;
    return res;
}
inline lng operator *(const lng &a,const lng &b)
{
    lng res; C(res.n);
    if (a.n[0]==0 || b.n[0]==0) return res;
    int p=0;
    int npos=INF;
    FORD(i,LN,LN-b.n[0]+1)
    {
        FORD(j,LN,LN-a.n[0]+1)
        {
            int m=res.n[j-p]+a.n[j]*b.n[i];
            res.n[j-p]=m%10000;
            if (m%10000) npos=min(npos,j-p);
            res.n[j-p-1]+=m/10000;
            if (m/10000) npos=min(npos,j-p-1);
        }
        p++;
    }
    while (npos<=LN && res.n[npos]==0) npos++;
    while (npos>1 && npos<=LN && res.n[npos-1]!=0) npos--;
    res.n[0]=LN-npos+1;
    return res;
}
inline void out(const lng &a)
{
    FOR(i,LN-a.n[0]+1,LN)
    {
        if (i==LN-a.n[0]+1) printf("%d",a.n[i]); else
        if (a.n[i]<10) printf("000%d",a.n[i]); else
        if (a.n[i]<100) printf("00%d",a.n[i]); else
        if (a.n[i]<1000) printf("0%d",a.n[i]); else
        printf("%d",a.n[i]);
    }
}
int a,b,c,d,i,j,n,m,k,now,last;
lng mas[52][2],tmp;
int main()
{
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    scanf("%d%d",&n,&k);
    if (n>k) 
    {
        printf("0 0\n");
        exit(0);
    }
    now=0; 
    mas[0][0].tol(1);
    tmp.tol(0);
    rep(i,k)
    {
        last=now; now^=1;
        rept(j,n+1)
        {
            mas[j][now].tol(0);
            tmp.toc(j+1);
            if (j!=n) mas[j][now]=mas[j+1][last]*tmp;
            tmp.toc(n-j+1);
            if (j!=0) mas[j][now]=mas[j][now]+mas[j-1][last]*tmp;
        }
    }
    out(mas[n][now]);
    printf(" ");
    if (mas[n][now].n[0]==0 || (mas[n][now].n[0]==1 && mas[n][now].n[LN]==0)) 
    {
        printf("0\n");
        exit(0);
    }
    tmp.tol(1);
    lng tmp1;
    tmp1.tol(2);
    rep(i,k-n)
    {
        tmp=tmp*tmp1;
    }
    tmp=tmp*mas[n][now];
    out(tmp);
    printf("\n");
}

astor

Во-первых у тебя немного некорекктный тон по отношению к жюри.
Во-вторых тайм-лимит может быть связан с делением на 0 (runtime error, но программa не обрывалась). То есть возможно у тебя какие то случаи в этой задаче прописаны неправильно. Проверь свое решение на тесте: 5 5 0 5.

Відредаговано Seyaua (2009-01-23 19:13:22)

А когда ты считаешь пересечение отрезков, ты учитываешь то что они могут быть параллельными?

тесты:

#1: 5 5 0 0
#2: 8 3 2 5

Значит не знаю где ошибка (трудно её искать не зная даже алгоритма).
Но все равно думаю, что скорее всего где-то возникает RE.

1. Дякую  за "вельмишановного". Відповісти взаємністю мені, схоже, важкувато.
2. Це ви повинні пояснити собі, чому у вас вийшов таймаут. Я ж цього зробити не можу, тому що не знаю, хто ви. Якби ви  написали, як годиться, листа з темою АПЕЛЛЯЦІЯ на адресу олімпіади, вказали свій код і суть проблеми, то обов'язково отримали б вичерпну відповідь, а якщо є наша помилка, то й вибачення. Але помилок в тестах до цієї задачі, схоже, немає. До того ж працює он-лайн перевірка ... А шукати в протоколі офіційної  перевірки кількох сотень розв'язків той, в якого не пройшли  "задачі" (очевидно, мова йде про тести  №№1,7,12,17) мені (sorry) "впадлу", та й де гарантія, що ви один такий кмітливий?

ну ок. але на сайті я не знайшов інформації про апеляцію. чекайте мого листа.
+ 16 пропустили.

Відредаговано astor (2009-01-23 20:05:05)

Мне больше сняли