Can someone please explain the subtask 1 for muldig. I made a function which multiply on the basis of indexes. So at (0,0) lies 0x0 at (0,1) lies 0x1 and so on…I was able to find 7,8,10 column which are B+4,B+5,B+7 but how to find the 9th column. Because when we calculate 9th column problem is, when we multiply two digit number say 01 and 10 to find the 9th column that is B+6 we have to add two bits ,here (B+4)(B+7)+(B+5)(B+6) but my function only do multiplication so this is the problem that i can do only (B+4)*(B+7) not addition further.
I know editorials will be there but i really want to know what i am missing for 20 points subtask.
Please Help
Thanks.
1 Like
Actually for subtask one I used same matrix…
0 0 1
0 1 2
1 2 2
Now If you see right upper 2x2 matrix, It will give addition between every possible pair that can be formed from 0 and 1, But to use this we will have to shift one digit by 1 which we want to add and bottom row 1 2 2 will help in it…
I am not sure if I was clear but Here is my solution for partial subTask of 20 points:
0 0 1
0 1 2
1 2 2
6
4 6 10
3 5 8
4 5 11
3 6 12
2 12 13
11 13 9
Here first two steps are pretty clear, and in 11 and 12 I am temporarily storing multiplication, and using 2 12 13 to shift digit stored in 12, Then using above top right matrix to digits in 11 and 13 and put it in 9.
Obviously this will not help in other tasks, And I could not build proper answer so I am also waiting for tutorial for perfect answer to solve this…
1 Like
Here is very short editorial for 100 points:
We do our main calculation using boolean logic. We select a NAND or NOR if our inputs are 0 or 1. A combination of NAND or NOR gates can be used for any boolean function. We can build a small ROM or even a binary multiplier using these gates.
So how do we convert between base 3, 5,7 and binary? If our second input is 0 or 1, we just continue to do NAND or NOR and consider values bigger than 1 on the first input as 1. If the second input is 2, we just do (first input+1) % base. With this function we can easily convert the input into a 1-hot coded binary representation. To convert binary back to base 3,5,7, we can also use this cycling functionality.
10 Likes
Yes, This is clear by the example. Thank you.
So you are converting the input into binary and multiplying? That’s so simple… why didn’t I think of this 
I looked up and found a universal gate in ternary logic which I used to get 40 points, but I was unable to do the same in 5-ary or 7-ary logic due to the huge function space.
I guess element(2,2) in matrix 3x3(o based indexing) need not be 2 because it is not used anywhere there will be no query of the form (2,2) until we are on first subtask.
I really feel bad for not thinking about this solution. Was very close to this :(. Thanks again.
yup… there was no use of 2,2… I just assigned random value there… 
I’m not even really multiplying. That can be done, but I did not want to write a digital logic synthesis tool for this task. I just calculated a table and used a PLA like structure with an AND and a OR plane to lookup the result. After all up to 100k gate were allowed, so nothing remotely effective was needed. My solution required 37k gates for base 7. (1.5k for base 3, 10k for base 5, 217k for base 11) https://www.codechef.com/viewsolution/14464079
1 Like
I’ll go through your solution and understand it, thanks!
I think you may find my solution interesting because it solves the task within the operation limit even for base 30, and uses a function that’s easy to describe:
f(a,b)=\begin{cases}a&\quad\text{if }b \ne 0\\a - 1\text{ mod }B&\quad\text{if }b = 0\end{cases}
This function has some useful properties that make it easy to define further building blocks, for example:
- You can define identity: id(n) = f(n,1)=n.
- You can define decrementation: dec(n) = f(n,0)=n - 1 \text{ mod } B.
- By repeated decrementation you can also define incrementation.
- You can define logical negation (sort of): not(n) = f(0,n)=\begin{cases}0&\quad\text{if }b \ne 0\\B - 1&\quad\text{if }b = 0\end{cases}.
- You can define a function that decrements the input only if it is nonzero: f(n, not(n)). This is useful because it lets you create loops of a sort (a variable may gradually go to zero and once it reaches it, it stays there). So with this function you may repeat incrementation a certain number of times, i.e. perform addition. And then addition a certain number of times to perform multiplication.
I’m sure that there are even more efficient choices than this. It was a fun exercise to see what you can define in terms of such a simple function and I highly recommend trying it on your own.
1 Like
@sir_ementaler I use another function
f(a, b) = \max\{a, b\}+1 \bmod B,
and the main idea seems the same to you. However, my approach might be a little complicated.
1 Like