ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1805. Chapaev and a Cipher Grille

any algo
Posted by Ibragim Atadjanov (Tashkent U of IT) 12 Nov 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
O(N^4) simple algo exists.
Re: any algo
Posted by Ibragim Atadjanov (Tashkent U of IT) 13 Nov 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
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
Posted by svr 7 Nov 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
Posted by Strekalovsky Oleg [Vologda SPU #1] 8 Nov 2011 00:01
svr wrote 7 November 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
Posted by ARK (***AESC_USU***) 15 Jan 2018 14:22
I suppose that O(n^2) algorithm is even more simple. Both in inventing and coding.
Re: any algo
Posted by Harkonnen 10 Aug 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'