ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1507. Трудное решение

To test makers
Послано Miha Zimin 1 ноя 2006 14:35
What is test 42?
please, give me some hint

10
1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1

In my WA 42 programm output "No"
Re: To test makers
Послано Anton [SUrSU] 1 ноя 2006 17:28
In test#42 n = 1 then print Yes
Re: To test makers
Послано Miha Zimin 1 ноя 2006 21:37
Thanks, but I think you are wrong.
I checked it:

int n;
...
int main()
{
    cin >> n;

    if(n == 1)
    {
        double *f = new double[0xfffffff];

        cout << "Yes";
        return 0;
    }

        ...
}

And this code has WA (on test 42), but not Crash or Memory limit. Therefore n is no 1 in test 42.

I need some hints as before :-)
please :-)
Re: To test makers
Послано Anton [SUrSU] 1 ноя 2006 22:14
I add this code to my last solution and got AC...
  if (n * (n - 1) == 0) {
    cur = e;
    ok = 1; // Yes
  }
Re: To test makers
Послано Miha Zimin 1 ноя 2006 22:46
It's strange, but I have WA 42 as before.
:-(
Who was need rejudge?
It's so strange. My desicion was AC (2 day ago), but now I don't know what can I do with this problem.

WA 42
N=2 in test 42 (-)
Послано Vladimir Yakovlev (USU) 2 ноя 2006 01:47
Re: N=2 in test 42 (-)
Послано Beautiful Mind 2 ноя 2006 20:40

 I got wrong answer at test 33. does it enough to use
 long long as data type.
Re: N=2 in test 42 (-)
Послано Anton [SUrSU] 2 ноя 2006 21:52
Use 0 or 1 to present matrix value's
Re: N=2 in test 42 (-)
Послано Beautiful Mind 3 ноя 2006 09:36
Thank u very much Anton , I got accepted. I don't know why i didn't think about that Still i am quite a stupid.

Edited by author 03.11.2006 09:37

Edited by author 03.11.2006 09:37
And perhaps it's also good to use & for multiplying and | for summing...(-)
Послано SPIRiT 3 ноя 2006 16:18
Time Lmit Exceeded
Послано Hayk 4 ноя 2006 02:10
Hello collegues ! :)

Can you tell me ... are you geting matrix B (with 0 1).
I tried that way and got TLE.
it comes about n*(n+1)*n^3 operatons.
Maybe there are more soft methods...
Re: Time Lmit Exceeded
Послано Olecksandr[LNU] 7 ноя 2006 00:18
Try use express method (for example A^5 = (A^2)^2*A
THANK YOU
Послано Hayk 12 ноя 2006 22:57
Thank you my Friend!
AC.

Ti daril mne RADOST' (I eto v jizni glavnoe)...:)
Re: Time Lmit Exceeded
Послано Neizvestnii 22 июн 2007 21:09
But erection of a matrix in a square borrows n^3. => O(2n*(n^2)*n^3) and this had TL(((
Maybe erection of a matrix in a square can work more quickly?

Edited by author 16.09.2007 14:32
Re: To test makers
Послано Denis Koshman 13 июл 2008 19:31
Anton [SUrSU] писал(a) 1 ноября 2006 22:14
I add this code to my last solution and got AC...
  if (n * (n - 1) == 0) {
    cur = e;
    ok = 1; // Yes
  }

It's strange becanse N>=2 according to problem statement