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. asked 17 Jul '17, 15:17

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 1hot coded binary representation. To convert binary back to base 3,5,7, we can also use this cycling functionality. answered 17 Jul '17, 15:44
So you are converting the input into binary and multiplying? That's so simple... why didn't I think of this :/
(17 Jul '17, 16:17)
1
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
(17 Jul '17, 17:01)
I'll go through your solution and understand it, thanks!
(17 Jul '17, 17:07)

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:
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. answered 17 Jul '17, 19:43

@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. answered 17 Jul '17, 20:21

I've posted the detailed explanation of the approach here: MULDIG  Editorial (Unofficial) answered 21 Jul '17, 15:19
