Why 0 and 1 is losing state and Grundy of 2 is {1,1}.
Can someone please tell me what is wrong in this solution that I submitted for the problem Area of Expertise:
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <array>
#include <iterator>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <climits>
#include <queue>
#include <stack>
#include <deque>
#include <list>
using namespace std;
typedef long long int ll;
typedef short int si;
typedef vector<int> vi;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define fastio ios::ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define eb emplace_back
#define mp make_pair
#define MOD 1000000007
#define MAX 1e9
#define MIN -1e9
/*ll mod(ll i)
{
if (i < 0)
return (i % MOD) + i;
else
return i % MOD;
}*/
int main()
{
fastio;
int n;
cin >> n;
vector<pair<ll, ll>> coor(n);
rep(i, n)
{
cin >> coor[i].first >> coor[i].second;
}
unordered_map<int, unordered_map<int,ll>> m;
rep(i, n)
{
m[i][i] = 0;
m[i][(i + 1) % n] = 0;
int cumpoint = (i + 1) % n;
int area = 0;
int area_count = (i + 2) % n;
do
{
ll x1 = coor[i].first, y1 = coor[i].second;
ll x2 = coor[cumpoint].first,
y2 = coor[cumpoint].second;
ll x3 = coor[(cumpoint + 1) % n].first,
y3 = coor[(cumpoint + 1) % n].second;
ll area_temp = 0;
ll t1 = x1 * (y2 - y3), t2 = x2 * (y3 - y1), t3 = x3 * (y1 - y2);
area_temp = ((t1)+(t2)+(t3));
if (area_temp < 0)
area_temp = -area_temp;
area += area_temp;
area %= MOD;
m[i][area_count++] = area;
cumpoint++;
cumpoint %= n;
} while (cumpoint != (i + n - 1) % n);
}
int q;
cin >> q;
while (q--)
{
ll i, j;
cin >> i >> j;
i--, j--;
cout << m[i][j] << '\n';
}
return 0;
}First observation is that when 2 balls with equal mass collide, they just interchange their velocities. Since the balls with equal mass are indistinguishable, we can assume that they pass through each other and don’t collide.
Let n_1 and n_2 be number of balls with mass 1kg and 2kg.
Denote solution as f(n_1, n_2)
Now, if n_1 \le n_2, the balls gets separated in 3 groups -
n_1 balls of 1kg, say velocity v_1
n_1 balls of 2kg, velocity v_2
n_2 - n_1 balls of 2kg, velocity v_3
with v_2 < v_3 < v_1 in same direction, so now they are stable.
Otherwise if n_1 > n_2,
The first n_2 1kg balls gets reversed with some velocity and form a group.
All the 2kg balls have equal velocities, but slightly less than before. But it doesn’t matter because only the fact that they collide with the remaining 1kg balls matters.
The problem is now same as f(n_1 - n_2, n_2)
1 Like
The time and space complexity seems to be \mathcal{O}(n^2).