1000000000D WORLD

Statement

Goal

You are in 1000000000D World!
In 1000000000D World all vectors consist of exactly one billion integers.

People of 1000000000D World are quite smart and they know that due to low entropy and "curse of dimensionality" most of their billion-dimensional vectors have a lot of consequent repetitions. So they always store their vectors in a compressed form.


For example consider a vector in canonical form: 

[1 1 1 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ... (999999995 times 3)]

In compressed form it will become just:

[3 1 2 2 999999995 3]    (which stands for 3 times 1 and 2 times 2 and 999999995 times 3)

Given two 1000000000D vectors A and B in compressed form.
Find a dot product of two vectors

Dot product definition:
For two vectors a = [a_1 a_2 ... a_n] and b = [b_1 b_2 ... b_n] dot product "a • b" = a_1 * b_1 + a_2 * b_2 + ... + a_n * b_n

Input

Line 1 Compressed Vector A
Line 2 Compressed Vector B

Output

Dot product of A and B

Constraints

The absolute values of the final result and all intermediate results are less than 2^40

Example

Input

500000001 1 499999999 -1
1000000000 1

Output

Tags

Linear algebra, Two pointers, Merge sort

Difficulty

Easy

Test cases

Test 1 Test

Input

500000001 1 499999999 -1 1000000000 1

Output

Validator 1 Validator

Input

500000000 1 500000000 -1 1000000000 1

Output

Test 2 Test

Input

5 1 5 2 999999990 0 3 1 3 2 3 1 999999991 0

Output

Validator 2 Validator

Input

5 1 5 2 999999990 0 3 1 3 2 4 1 999999990 0

Output

Test 3 Test

Input

1000000000 1 1000000000 -1

Output

-1000000000

Validator 3 Validator

Input

1000000000 2 1000000000 -2

Output

-4000000000

Test 4 Test

Input

1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 999999945 -1 999999945 2 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1

Output

-1999999395

Validator 4 Validator

Input

1 -1 2 2 3 -3 4 4 5 -5 6 6 7 7 8 8 9 9 10 10 999999945 -1 999999945 2 10 10 9 9 8 -8 7 7 6 6 5 5 4 4 3 3 2 2 1 1

Output

-1999999407

Test 5 Test

Input

61293583 -5 60141391 -10 30705144 6 18209987 8 3623360 -5 3715666 4 18252771 -5 24739354 7 107410335 -1 18585831 1 37735014 9 4459884 -3 10163437 -6 67811650 10 49967223 3 29661998 1 34417955 8 5997538 -5 12037693 0 12536915 1 35929119 10 17059584 -4 10232854 7 13870276 6 3519983 6 55936984 7 72768589 2 29183804 -3 33351647 7 20893540 5 17190111 1 27370514 5 17869452 -3 1811597 10 31545217 -10 29853135 2 7370169 0 9807376 -5 90278577 -7 27976028 -3 131519266 1 68154 -9 2173005 -9 40036660 5 63310669 9 25674306 -10 24212637 -3 29203142 2 79327039 2 18493184 -9 1854019 1 47335765 -5 38838995 10 49608857 1 13201908 3 85586590 4 30040431 -10 30620504 6 16642661 2 52716485 5 31264011 -5 22986427 -5

Output

9221165894

Validator 5 Validator

Input

2366176 8 71377928 -10 32772583 10 57875124 7 11629003 -9 26737542 8 8548324 -9 26709456 9 11121230 -8 22746505 -9 10800416 -10 4930342 -1 71986727 -7 53459598 1 26565189 -4 22300864 3 17328405 -1 44853197 3 32155933 -9 22922767 -7 12386628 -1 19738681 -8 9209761 -6 40447831 2 1357193 -1 80924538 1 327737 -4 40952905 -6 22245681 -5 61124458 0 11621681 -6 11621951 10 1759404 4 107094242 0 60878406 -1 4307009 -10 123193 -1 33645079 -7 14746536 9 823039 -7 34337910 2 1219909 -9 3668483 -1 18220784 5 74839315 7 849416 1 103226984 -2 10591598 -3 48245076 -3 30142692 7 38132988 10 80406200 -10 55940901 -5 3420548 7 38560897 -2 39134336 3 742599 -4 10301979 5 4198585 -1 6921186 -2 36632814 -5 47009554 6 75428389 2 52980482 8 14007981 9 5791541 -8 50523591 2

Output

7153742050

Test 6 Test

Input

100000000 1 100000000 1 100000000 1 100000000 1 100000000 1 100000000 1 100000000 1 100000000 1 100000000 1 100000000 1 100000000 1 100000000 -1 100000000 1 100000000 -1 100000000 1 100000000 -1 100000000 1 100000000 -1 100000000 1 100000000 -1

Output

Validator 6 Validator

Input

100000000 1 100000000 -1 100000000 1 100000000 -1 100000000 1 100000000 -1 100000000 1 100000000 -1 100000000 1 100000000 -1 100000000 1 100000000 1 100000000 1 100000000 1 100000000 1 100000000 1 100000000 1 100000000 1 100000000 1 100000000 1

Output

Test 7 Test

Input

26751891 1 12423842 0 24697032 -1 75825948 0 16058842 -1 5056344 -1 14781040 -1 48256886 0 37330872 1 68962932 1 37555307 1 2970721 0 26201429 1 48967194 -1 17837665 0 74719356 -2 17461041 -2 20765736 0 15044838 1 6518283 -2 10432178 -2 15225674 -2 6160520 0 32060077 0 52545144 0 3848757 -2 91480452 -1 99032044 1 89501141 1 1526814 0 40312847 1 84841395 -2 43849784 1 3228664 -1 98445257 -1 22318921 0 42672597 0 4577041 0 5240860 -2 31151717 1 30451395 -2 35469153 -2 25313187 -2 40128193 1 15893237 1 6369211 1 3672509 -1 22259551 0 25942846 -2 12180032 1 4202901 0 68816164 1 520373 -2 107835622 1 50661951 -2 67145499 0 88144650 -1 18354443 -1

Output

-213982941

Validator 7 Validator

Input

7830260 1 16181324 -1 13703364 0 78566009 0 23935019 -1 157526 -1 132927622 0 15500881 -2 112094285 -2 13670058 -2 15816147 -1 3016168 -2 546634 1 116394701 -1 31169703 -2 21885624 1 16599623 -1 31075845 -2 42026568 -1 10780567 0 73584595 0 2571837 -1 103659864 -1 20690248 -2 57630814 0 2161612 -1 35823102 1 160403975 -1 140375 -2 7674556 -2 4451017 -2 91536282 -2 68261179 1 6429715 -2 28490164 0 17356238 1 12037697 1 20639036 1 25013048 -2 2227940 0 31733185 -1 5208896 -1 32404595 -1 32609531 0 26101592 1 35348955 -1 29963445 1 5383555 -1 250031 1 11108478 0 303124 0 11466325 0 23430117 -1 135661540 0 3821960 0 7740419 -1 12634501 -2 50408217 0 58036866 -1 25420857 1 16302589 -1

Output

-54223215

Solution language

Solution

Stub generator input

Comments

12 Comments

chabes Unnamed CodinGamer

about 3 years ago

✅ Approved the contribution. Comment: I like it. Indeed it is between Simple and Medium. Still, about 5min to solve it so I would keep Simple

codybumba Unnamed CodinGamer

✅ Approved the contribution. Comment: Pretty Cool Puzzle. Can we increase the difficulty level to Medium since normal brute-force approach does not work where we generate uncompressed list and do the dot product? I think many people would follow this approach. Here is my Python solution. a = [*map(int, input().split())] b = [*map(int, input().split())] i = 0 j = 0 ans = 0 while i < len(a) and j < len(b): front_a = a[i] front_b = b[j] if front_a < front_b: ans += front_a * (a[i+1]*b[j+1]) b[j]-=a[i] i += 2 elif front_a > front_b: ans += front_b * (a[i+1]*b[j+1]) a[i]-=b[j] j += 2 else: ans += front_a * (a[i+1]*b[j+1]) i += 2 j += 2 print(ans)

awnion Unnamed CodinGamer

How about this? :P def dot(a, b): if not a or not b: return 0 if a > b: return dot(b, a) b[0] -= a[0] return dot(a[2:], b) + a[0] * a[1] * b[1] print(dot(*[[*map(int,x.split())]for x in open(0)])) ____ P.S. seems like a[2:] is O(1) in python and the solution is still linear 🤔 in Haskell it's even more elegant main = interact $ show . (\(a : b : _) -> dot a b) . map (map read . words) . lines dot [] _ = 0 dot a b | head a > head b = dot b a dot (cx : x : a) (cy : y : b) = dot a (cy - cx : y : b) + cx * x * y

tutubalin Unnamed CodinGamer

✅ Approved the contribution. Comment: It's not hard, but still challenging.

> The absolute values of the final result and all intermediate results are less than 2^60 JS Number supports interger values up to 2^53.

Oh yeah, thanks, I forgot about it. Actually, all intermediate results are less than 2^40. I'll fix it.

Changed 1_000_000 -> 1_000_000_000 D. BF shouldn't work I guess.

Konstant Unnamed CodinGamer

Nice idea. Difficult fits more for clash i suppose

Clashers didn't like it =) Had to move here.