Google APAC Kickstart 2017 Round D is coming

9 лет назад, скрыть # |

Approach for B small? I tried to do kadane for k/n^2 elements for each dp state. Is this intended?

→ Ответить

rajat1603

9 лет назад, скрыть # ^ |

submatrix sum is product of Sum of A from (X1 .. X2) and Sum of B from (Y1 .. Y2) , Now suppose you have the list of all subarray sums of A and B , then you can binary search on answer. But notice we don't need all subarrays but only the ones with Max sums , Min Sums , just > 0 and just < 0 , so we can use a vector segtree to get these.

→ Ответить

9 лет назад, скрыть # ^ |

+21

No idea what you are talking about. T.T

→ Ответить

I_Love_Nicki_Minaj

9 лет назад, скрыть # ^ |

Can you please explain that segment tree part again?

→ Ответить

_namespace

9 лет назад, скрыть # ^ |

+16

Nice display picture :)

→ Ответить

OfTheSharingan

9 лет назад, скрыть # ^ |

bhen k lode

→ Ответить

rhezo

9 лет назад, скрыть # ^ |

I guess you're talking about getting 10^5 maxsums, minsums, > 0 sums and < 0 sums. Am I right? How do i get these by vector segtree?

→ Ответить

rajat1603

9 лет назад, скрыть # ^ |

let sum_i denote prefix sum from 1 to i , the max subarray sum ending at i is sum_i-min(sum_j for 0 < = j < = i - 1) , so we we keep a priority queue storing (Sum , Right endpoint , Range for left endpoint , Min element index) and using this when you pop the top element of priority queue , you can split the Range for left endpoints into 2 parts , (on the left of min element index and the right). This gives us the max subarray sums , the minsums part is also very similar. For > 0 sums instead of finding minimum subarray sum , we find the subarray sum just smaller than this (using vector segtree / persistent segtree) and do stuff similar to described above , Sums < 0 is very similar (Replace just smaller with just bigger).

→ Ответить

sanket407

9 лет назад, скрыть # ^ |

Did a O(n^4) soln for getting all sub matrix sums. Also used a priority queue on the side for storing max K sums out of these

→ Ответить

9 лет назад, скрыть # ^ |

← Rev. 2 →

Well, I'm stupid enough to be concerned about complexity in kickstart :(

→ Ответить

rajat1603

9 лет назад, скрыть # |

+34

I didn't want to derive the formula for closest distance of a point from a parabola and did some slow heuristics , took long enough to run but luckily i was able to submit with 2 seconds left.

→ Ответить

flatline

9 лет назад, скрыть # ^ |

+16

I finished just two minutes after the contest ended. My solution is basically a Russian Nesting Doll equivalent of Binary/Ternary Search.

Code

→ Ответить

9 лет назад, скрыть # ^ |

I also solved C-small two minutes after contest, so sad(( I do binary search for radius and checking for intersection with point by going through parabola with low delta x.

Code

	int rep = 0;
	while (rep < repCount)
	{
		rep++;
		r = (lR + bR) / 2;
		dbl r2 = r * r;
		a = (4.0 * (r - h)) / p2;
		bool good = 1;
		dbl delta = (2*r) / numIter;
		for (int i = 0; i <= numIter; i++)
		{
			dbl x2 = x - r + i * delta;
			dbl y2 = a * x2 * (x2 - p);
			dbl d = sqr(x2 - x) + sqr(y2 - y);
			if (d < r2)
			{
				good = 0;
				break;
			}
		}
		if (good) lR = r;
		else bR = r;
	}

→ Ответить

9 лет назад, скрыть # |

I couldn't run my solution for B-small on VS-2015 because of too large array (~ 4*10^8), but it works fine on GNU C++. Is there any solution for creating large arrays in MS C++ ?

Code

const int maxSize = 404010000;
LL* sums = new LL[maxSize + 5];

void solve()
{
	LL n, k, a1, b1, c, d, e1, e2, f;
	cin >> n >> k >> a1 >> b1 >> c >> d >> e1 >> e2 >> f;
	gen(n, a1, b1, c, d, e1, e2, f);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			matrix[i][j] = a[i] * b[j];
	precalcSum(n);

	LL sum;
	LL t = 0;
	for (int i1 = 1; i1 <= n; i1++)
		for (int j1 = 1; j1 <= n; j1++)
			for (int i2 = i1; i2 <= n; i2++)
				for (int j2 = j1; j2 <= n; j2++)
				{
					sum = getSum(i2, j2, i1, j1);
					sums[t] = sum;
					t++;
				}

	nth_element(sums, sums + t-k, sums + t);
	cout << sums[t-k] << endl;
}

→ Ответить

ckcz123

9 лет назад, скрыть # ^ |

← Rev. 2 →

You shouldn't remember all the sums. However, remember only the largest K (~10^5) sums is enough.

→ Ответить

9 лет назад, скрыть # ^ |

← Rev. 2 →

Thanks, I know this. But question generally is about creating large arrays, not especially problem B-small:)

UPD Solved, It's enough switch build mode to x64 to create large arrays (up to MaxInt bytes)!

code

const int maxInt = 2147483647; // 2^31 - 1
LL* longs = new LL[maxInt / 2]; 
int* ints = new int[maxInt];

→ Ответить

SlavaSSU

9 лет назад, скрыть # ^ |

what about std::vector?

→ Ответить

9 лет назад, скрыть # ^ |

Vector produce runtime error in MS C++

→ Ответить

9 лет назад, скрыть # |

← Rev. 2 →

I couldn't get AC on B small due to one stupid bug. Nevertheless, here's my solution for which I got AC now. First we find all the subarrays sums for A and B. Now, we sort them, let's call them X and Y. And make a max-heap for the maximum product. So, in the starting we insert in the heap, $\text{[math]}$ and X[size - 1]·Y[size - 1] (this is because max. product is either the product of two largest positive numbers or two smallest negative numbers). We keep track of the current indices which are there, let's say they are i, j then we insert in the heap, product of these elements (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1). Overall complexity of solution is $\text{[math]}$

→ Ответить

9 лет назад, скрыть # ^ |

code please

→ Ответить

9 лет назад, скрыть # ^ |

There you go

→ Ответить

9 лет назад, скрыть # ^ |

Aren't you making the assumption that the kth value will always start from (1,1) of sorted Aprefixsum and Bprefixsum ? And both these prefix sum arrays were made taking first i or j elements of a and b. So, doesn't this mean no matter what result you get, you'll have a submatrix from top left corner of our initial matrix?

→ Ответить

9 лет назад, скрыть # ^ |

No, you got that wrong. The X and Y arrays consists of all the subarrays of A and B respectively, not just prefix sums. That's why the complexity is O(n²). That's why always the first maxm product will start from (1,1) and (n-1, n -1)[n denotes size of X array]

→ Ответить

9 лет назад, скрыть # ^ |

Yeah, I was about to edit that I misunderstood that part :)

This passes B small and large both I hope.

→ Ответить

9 лет назад, скрыть # ^ |

+10

This won't pass B large as size of X and Y are way too large about 10^10

→ Ответить