ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
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
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