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

Обсуждение задачи 1805. Чапаев и шифровальная решётка

any algo
Послано Ibragim Atadjanov (Tashkent U of IT) 12 ноя 2010 10:57
Who know how to solve it. I think all the varians will be
4^(9 + 7 + 5 + 3 + 1) = 4^25 when n = 10. So i cannot count from 1st to kth variant
Re: any algo
Послано Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 12 ноя 2010 13:56
O(N^4) simple algo exists.
Re: any algo
Послано Ibragim Atadjanov (Tashkent U of IT) 13 ноя 2010 18:52
Can you tell anything else? I mean is the algo search(Binary Search or smth else). Please give me a clue
Re: any algo
Послано Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 13 ноя 2010 22:49
Suppose you have already built a part of a grille and is thinking what symbol is to put in the following cell. Can you count the number of grilles which can be built with such a beginning and symbol?
Re: any algo
Послано svr 7 ноя 2011 14:34
Given advices too weak to be helpfull.
For me key idea was forming n*n/4 classes with 4 cell in each and working
with level, where 1<=level<=n*n;
We counting all combinations under level in each classes exept whose are used already.
Re: any algo
Послано Strekalovsky Oleg [Vologda SPU #1] 8 ноя 2011 00:01
svr писал(a) 7 ноября 2011 14:34
Given advices too weak to be helpfull.
For me key idea was forming n*n/4 classes with 4 cell in each and working
with level, where 1<=level<=n*n;
We counting all combinations under level in each classes exept whose are used already.
My algo was same as Vedernikoff 'Goryinyich' Sergey (HSE: АОП) said.
Algo is very simple and wasn't too hard to implement.

Edited by author 08.11.2011 00:01
Re: any algo
Послано ARK (***AESC_USU***) 15 янв 2018 14:22
I suppose that O(n^2) algorithm is even more simple. Both in inventing and coding.
Re: any algo
Послано Harkonnen 10 авг 2022 11:56
That's right. I track amount of remaining variations for every cycle and their total product. This information is enough at each of N^2 steps to decide if it should be '0' or '1'