Maximum with a catch

Computer Science Level 5

A function is given by f ( x ) = x 3 + 3 f(x)=x^{3}+3

N N line separated lists are given in the text file, and let S = ( f ( x 1 ) + f ( x 2 ) + … + f ( x n ) ) m o d 123 S=(f(x_{1})+f(x_{2})+\ldots +f(x_{n})) \bmod {123} where x i x_{i} is an element picked from the i i th's list. What is the maximum possible value of S S ?

Contest problem.


The answer is 122.

View wiki
Beakal Tiliksew by Beakal Tiliksew , 24, Ethiopia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Bill Bell
Sep 8, 2015 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
from itertools import product

X=[
[868344, 5702470, 4164686, 6909034, 9938057, 2325752, 2873259],
[3281382, 6656834, 2949466, 8313351, 1693510, 7965124],
[6170425, 3484246, 2039180, 761139, 2069051, 3570668, 2348921],
[9698787, 37364, 8030130, 6391829, 6969085, 1247325],
[8416661, 9855125, 6534506, 9285004, 8073946, 3215543, 6194037],
[8012002, 1583648,  7049465, 4639438],
[6407988, 3097441, 2604562, 5094765, 6581687, 7160093, 5855903],
[5678899, 3457932, 1234793, 1298400]
]

f=lambda x: x**3+3

f_values=[]
for x in X:
    f_values.append([f(item) for item in x])

max_S=0
for poss in product(*f_values):
    S=sum(poss)%123
    max_S=max(max_S,S)

print max_S

2 Helpful 0 Interesting 0 Brilliant 0 Confused

The maximum possible value of y m o d 123 y \mod 123 is 122 122 . Used that fact and the general logic that with a large data set, this possibility is bound to occur. Hence, answered 122 without looking at the data file.

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Abdelhamid Saadi
Sep 15, 2015

A one line solution in python 3.4: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
 
from itertools import product
lists=[
    [868344, 5702470, 4164686, 6909034, 9938057, 2325752, 2873259],
    [3281382, 6656834, 2949466, 8313351, 1693510, 7965124],
    [6170425, 3484246, 2039180, 761139, 2069051, 3570668, 2348921],
    [9698787, 37364, 8030130, 6391829, 6969085, 1247325],
    [8416661, 9855125, 6534506, 9285004, 8073946, 321554, 6194037],
    [8012002, 1583648,  7049465, 4639438],
    [6407988, 3097441, 2604562, 5094765, 6581687, 7160093, 5855903],
    [5678899, 3457932, 1234793, 1298400]
    ]

def solve():
    "Maximum with a catch"
    return max(sum(x)%123 for x in product(*[[(1+z**3)%123 for z in y] for y in lists]))

print(solve())

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...