×

# MULDIG for partial points

 0 1 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 256●7 accept rate: 8%

 10 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. answered 17 Jul '17, 15:44 226●1●3 accept rate: 7% 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. (17 Jul '17, 16:17) meooow ♦6★ 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) meooow ♦6★
 1 For just 20 points: see my code answered 17 Jul '17, 15:23 1.1k●1●10 accept rate: 10%
 1 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. answered 17 Jul '17, 19:43 53●3 accept rate: 0%
 1 @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 672●2●3●13 accept rate: 12%
 1 I've posted the detailed explanation of the approach here: MULDIG - Editorial (Unofficial) answered 21 Jul '17, 15:19 6★lboris 301●4 accept rate: 33%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,051
×331

question asked: 17 Jul '17, 15:17

question was seen: 599 times

last updated: 21 Jul '17, 15:19