Hello everyone !!
After 3 successful editions, Aparoksha is back with flagship coding event — CodeRed.
CodeRed 2020 consists of 2 rounds, Online preliminary round and Onsite final round. The online preliminary round will be a 3-hour long team event with a maximum size of the team being 3 members. The participants need not be from the same college/institution/organization. Problem set has 6/7 problems of varying difficulty. CodeRed 2020 is scheduled at March 11, 2020 at 22:00 IST
Last year CodeRed 2019 had 1271 teams registered, we are expecting higher participation this year. You can register your team here — CodeRed 2020 online preliminary round.
CodeRed, Alkhwarizm (Rated for all CodeChef contest) and Humblefool cup (Which happened a few days ago on Topcoder) are all among flagship coding events of Aparoksha — Techincal fest of Indian Institute of Information Technology (IIIT), Allahabad.
The total prize money is worth INR 125,000. Also, top 3 teams in the online preliminary round will get INR 3000, 2500 and 1500 respectively. The best 40 Indian teams will make it to the onsite round (To be held in IIIT Allahabad). All teams making it to the onsite round will get Aparoksha T-shirts.
Please fill out this Registration form to avail prizes — Register here
Problems have been set and tested by Mridul Gupta — mridul1809, Shivam Garg — shivamg_isc, Vaibhav Srivastava — dbest077, Ravi Chandra — rc_4594 , Ashutosh Kaushik — AK18, Kumar Raju — Eunoia__1729, priyanshu kumar — priyanshupkm.
Editorial will be posted here after the contest.
PS: Please Ignore the timing on the poster.
Upd1: 250 laddus for each member of top 3 teams. 9 hours to go.
Upd2: 30 minutes to go
upd3: the contest has been extended by 30 minutes, filling the registration form is mandatory to qualify for the on-site final
Upd4: Thanks for the overwhelming response. :D
Congratulations to the top 3 winners :D
1. NTT — tempura0224, tatyam, noimi
2. fast_coders — acraider, nitixkrai, fsociety00
3. Minimum Spanking Tree — hitman623, Enigma27, _shanky
Hints for the problems, detailed editorials will be posted later.
Hints :
By rc_4594
Let $$$dp(x,y)$$$ be Minimum Cost Of Reaching $$$(x,y)$$$ and placing a landmark over there.
We need to find value of $$$dp(N,M)$$$.
Consider the sequence of landmarked spots as $$$(x_1,y_1) , (x_2,y_2) ... (x_k,y_k) $$$
$$$dp(x_i , y_i)$$$ = $$$F(x_{i-1},y_{i-1}) \times (x_i - x_{i-1} + y_i - y_{i-1} ) + dp(x_{i-1},y_{i-1}) + T(x_i , y_i)$$$.
This becomes a DP Optimization problem which can be solved using Convex Hull Trick!
Expected Complexity : $$$ O(NM^2 ) $$$ (In case of large $$$M$$$ , transpose the matrix , it wont change the answer )
#include <iostream>
#include <vector>
#include <string.h>
#include <set>
#include <map>
#include <unordered_map>
#include <assert.h>
#include <algorithm>
#include <queue>
#include <bitset>
#include <stack>
#include <chrono>
#include <random>
#include <climits>
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define ll long long
#define MOD 1000000007
#define INF 1000000000000000000
#define float double
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define uid uniform_int_distribution <int>
using namespace std;
// Read the question carefully and see all the given sample tests
// Think about the correctness before implementing
struct Line {
mutable ll k, m, p;
bool operator<(const Line& o) const { return k < o.k; }
bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
// (for doubles, use inf = 1/.0, div(a,b) = a/b)
const ll inf = LLONG_MAX;
ll div(ll a, ll b) { // floored division
return a / b - ((a ^ b) < 0 && a % b); }
bool isect(iterator x, iterator y) {
if (y == end()) { x->p = inf; return false; }
if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
else x->p = div(y->m - x->m, x->k - y->k);
return x->p >= y->p;
}
void add(ll k, ll m) {
auto z = insert({k, m, 0}), y = z++, x = y;
while (isect(y, z)) z = erase(z);
if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
while ((y = x) != begin() && (--x)->p >= y->p)
isect(x, erase(y));
}
ll query(ll x) {
assert(!empty());
auto l = *lower_bound(x);
return l.k * x + l.m;
}
};
int main() {
int n, m;
cin >> n >> m;
vector<vector<ll>> T(max(n, m), vector<ll>(min(n, m)));
vector<vector<ll>> F(max(n, m), vector<ll>(min(n, m)));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(n < m)
cin >> T[j][i];
else
cin >> T[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(n < m)
cin >> F[j][i];
else
cin >> F[i][j];
}
}
if(n < m)
swap(n, m);
LineContainer foo[m];
ll res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(i == 0 && j == 0) {
foo[j].add(F[i][j], 0);
continue;
}
ll ans = -INF;
for (int k = 0; k <= j; k++) {
if(i == 0 && k == j)
continue;
ans = max(ans, foo[k].query(-i - j));
}
foo[j].add(F[i][j], ans + F[i][j] * (i + j) - T[i][j]);
res = ans - T[i][j];
}
}
cout << -res;
}
By mridul1809
Given the structure of "graph" , we can move upwards only 1 step at a time.
The cycles are to create extra steps so we can get total number of steps as multiple of required number.
To go from A to B+1 , we can only consider the cycles starting and ending between A and B.
Let the lengths of all such cycles be $$$a_1,a_2,...,a_p$$$. We need to find a solution to the equation $$$x_1a_1 + x_2a_2 + ... + x_pa_p + B+1 - A = kY$$$
rearranging we get
$$$B+1-A = kY - ( x_1a_1 + x_2a_2 + ... + x_pa_p )$$$
$$$B+1-A = kY + z_1a_1 + z_2a_2 + ... + z_pa_p )$$$
we need to find if an integral solution to this equation exists such that
→ $$$k > 0$$$
→ $$$z_i <= 0$$$
If $$$B+1 - A = q \times GCD(k,a_1 , a_2 , .. a_n) $$$ (where $$$q$$$ is any +ve integer) we will always have a solution.
Now the question remains to find the GCD of lengths of all the cycles between A and B.
This can be done using Sorting Queries , Merge Sort Tree , Persistent Segment Tree , etc.
Expected Complexity : $$$ O(MlogM + QlogN) $$$ ($$$M$$$ is the number of cycles)
//mridul1809
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define s(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define p(x) printf("%d ",x)
#define pl(x) printf("%lld ",x)
#define endl "\n"
#define vi vector <int>
#define pii pair <int,int>
#define sz(x) x.size()
#define all(x) x.begin(),x.end()
#define max5 100005
#define max6 1000005
#define maxlong 20
struct cycle
{
int l,r,s;
};
vector < cycle > cycles;
bool comp(cycle a , cycle b)
{
return (a.r < b.r);
}
struct query {
int a,b,i;
ll y;
};
bool comp_query(query a , query b)
{
return (a.b < b.b);
}
vector <query> queries(max5);
vector <string> answers(max5);
vector <int> tree(4*max5);
void update(int l ,int r , int pos , int val , int idx)
{
if(l == r)
{
tree[idx] = __gcd(tree[idx] , val);
return;
}
int mid = (l + r)/2;
if(pos <= mid)
update(l , mid , pos , val , 2*idx);
else
update(mid+1 , r , pos , val , 2*idx+1);
tree[idx] = __gcd(tree[2*idx] , tree[2*idx+1]);
}
int query_tree(int l ,int r, int ql, int qr, int idx)
{
if(ql > r || l > qr)
return 0;
if(ql <= l && r <= qr)
return tree[idx];
int mid = (l + r)/2;
return __gcd(query_tree(l,mid,ql,qr,2*idx) , query_tree(mid+1,r,ql,qr,2*idx+1));
}
void solve()
{
int n,i,m,t,j;
s(n);
for(i = 1; i <= n+1; i++)
{
s(m);
for(j = 1; j <= m; j++)
{
s(t);
cycles.pb({t , i , i - t + 1});
}
}
sort(all(cycles) , comp);
int q;
s(q);
for(i = 0; i < q; i++)
{
int a , b;
ll y ;
cin >> a >> b >> y;
queries[i].a = a;
queries[i].b = b;
queries[i].i = i;
queries[i].y = y;
}
sort(queries.begin() , queries.begin() + q, comp_query);
int cc = 0;
int qc = 0;
while(qc < q)
{
while(cc < sz(cycles) && cycles[cc].r <= queries[qc].b)
{
update(1 , n , cycles[cc].l , cycles[cc].s , 1);
cc++;
}
int limit = queries[qc].b;
while(qc < q && queries[qc].b <= limit)
{
ll result = query_tree(1 , n , queries[qc].a , n , 1);
result = __gcd(result , queries[qc].y);
if((queries[qc].b-queries[qc].a+1)%result == 0)
answers[queries[qc].i] = "YES";
else
answers[queries[qc].i] = "NO";
qc++;
}
}
for(i = 0; i < q; i++)
cout << answers[i] << endl;
return;
}
int main()
{
int t = 1;
// s(t);
while(t--)
solve();
return 0;
}
By shivamg_isc
The first instinct for this question would be Matrix Exponentiation, but because the value of N is 1000, this would lead to TLE.
The idea almost remains the same, but with a slight tweak.
Maintain a $$$bitset <N> canReach[30][N]$$$.
If you can reach from $$$i$$$ to a point $$$k$$$ using exact $$$2^j$$$ steps, the $$$k$$$-th bit will be set in the bitset $$$canReach[j][i]$$$.
Similarly, an array $$$min[30][N]$$$ needs to be maintained. $$$min[j][i]$$$ stores the min value among all the nodes that can be visited from $$$i$$$ using atmost $$$2^j$$$ steps.
This can be maintained in a sparse table fashion.
wait for a while.
By AK18
2nd operation is useless, it won't affect GCD at all.
Observation in 1st operation: after removal array is non-empty and you always remove a continous subsegment, which means either first or last element will always be there in the array. Now what would be the optimal choice ? obvious, maximum of first and last. Picking more than 1 elements will always reduce the gcd.
#include<bits/stdc++.h>
using namespace std;
void solve();
int main()
{
int t = 1;
cin >> t;
for(int i = 1; i <= t; ++i)
solve();
}
void solve() {
int n;
cin >> n;
std::vector<long long int> v(n);
for(int i = 0; i < n; ++i) {
cin >> v[i];
}
cout << max(v[0],v[n-1]) << endl;
}
By Eunoia__1729
The question boils down to find the number of ways to go from any black cell in the 1st row to any black cell in the Mth row and the required observation is that in each move the color of the cell changes.
#include <bits/stdc++.h>
int main()
{
long long n, m, i, j, k, ans = 0;
cin>>n>>m;
ll dp[n+1][m+1];
ll r[4] = {1,2,1,2};
ll c[4] = {-2,-1,2,1};
memset(dp,0,sizeof(dp));
for(i = 0; i < m; ++i)
if( i%2)
dp[0][i] = 1;
for(i = 0; i < n; ++i)
for(j = 0; j < m; ++j)
for(k = 0; k < 4; ++k)
if( i - r[k] < n and i - r[k] >= 0 and j - c[k] < m and j - c[k] >= 0)
{
dp[i][j]+=dp[i - r[k]][j - c[k]];
dp[i][j]%=mod;
}
for(i = 0; i < m; ++i)
if( i%2 == 1 - n%2)
{
ans+=dp[n-1][i];
ans%=mod;
}
cout<<ans<<endl;
return 0;
}
By shivamg_isc , AK18, Eunoia__1729
Here we first use simple bfs to calculate level of each node. Now let us assume that there are no values on the node and we need to find the node with minimum index closest to the root, which can be done by just sorting it and doing binary search. Now when we have values, sorting it by value will change the order of levels. Then, for each level keep the maximum value of the node, building segment tree of maximum of a segment. Now for each query we just find the minimum index idx such that [1,idx] contains the node with value greater than X(which can be done in $$$logN$$$ or $$$(logN)^2$$$. For each level we have pair of (value of node, node) stored in multiset. we can get our answer from that level's multiset. For updates, just erase from multiset and insert the required pair, and also update the segment tree.
Time complexity: $$$O(NlogN)$$$
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define pii pair<int,int>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define SZ(x) ((int)x.size())
#define FOR(i,a,b) for(int i = a; i < b; ++i)
typedef long long ll;
void solve();
#define int ll
const int N = 1e5+2;
multiset<int> ms[N];
multiset<pii> dd[N];
std::vector<int> adj[N];
std::vector<int> dis(N,-1);
int t[4*N];
int a[N];
int n;
void upd(int node, int x) {
t[node] = x; // change
return;
}
void build(int node = 1,int tl = 0,int tr = n - 1) {
if(tl > tr) {
return;
}
if(tl == tr) {
t[node] = a[tl]; // change
return;
}
int mid = (tl + tr) / 2;
build(2 * node, tl, mid);
build(2 * node + 1, mid + 1, tr);
t[node] = max(t[2 * node] , t[2 * node + 1]); // change
}
void updateRange(int pos,int val, int node = 1, int tl = 0, int tr = n-1) {
if(pos < tl or pos > tr) {
return;
}
if(tl == tr) {
upd(node,val);
return;
}
int mid = (tl + tr) / 2;
if(tl <= pos and pos <= mid)
updateRange(pos, val, 2 * node, tl , mid);
else
updateRange(pos, val, 2 * node + 1, mid+1, tr);
t[node] = max(t[2 * node] , t[2 * node + 1]); // change
}
int query(int val,int node = 1, int tl = 0, int tr = n-1) {
if ( tr < tl) {
return 0; // change
}
if(tl == tr) {
return tl; // change
}
int mid = (tl + tr) / 2;
int p = t[2*node];
int q = t[2*node+1]; // change
// debug(val,node, tl,tr, p ,q);
if(p > val) {
return query(val,2*node,tl,mid);
}
else if(q > val){
return query(val,2*node+1,mid+1,tr);
}
return -1;
}
int32_t main()
{
fast;
solve();
}
int val[N];
void solve() {
cin >> n;
FOR(i,1,n+1) {
cin >> a[i];
val[i] = a[i];
}
FOR(i,0,n-1) {
int A,b;
cin >> A >> b;
adj[A].pb(b);
adj[b].pb(A);
}
queue<int> Q;
Q.push(1);
dis[1] = 0;
ms[0].insert(a[1]);
dd[0].insert({a[1],1});
while(SZ(Q)) {
int top = Q.front();
Q.pop();
for(auto i:adj[top]) {
if(dis[i] == -1) {
dis[i] = dis[top] + 1;
ms[dis[i]].insert(a[i]);
dd[dis[i]].insert({a[i],i});
Q.push(i);
}
}
}
FOR(i,0,n) {
if(SZ(ms[i])) {
a[i] = *ms[i].rbegin();
}
else {
n = i;
break;
}
}
build();
int q;
cin >> q;
while(q--) {
int T;
cin >> T;
if(T == 1) {
int x,y;
cin >> x >> y;
ms[dis[x]].erase(ms[dis[x]].find(val[x]));
ms[dis[x]].insert(y);
dd[dis[x]].erase(dd[dis[x]].find(make_pair(val[x],x)));
a[dis[x]] = *ms[dis[x]].rbegin();
val[x] = y;
updateRange(dis[x],*ms[dis[x]].rbegin());
dd[dis[x]].insert({val[x],x});
}
else {
int x;
cin >> x;
int p = query(x);
if(p == -1) {
cout << p << endl;
continue;
}
auto it = dd[p].upper_bound(make_pair(x+1,-1));
cout << (*it).se << endl;
}
}
}
By dbest077
A Bitmask + Dp solution to iterate over the 2D matrix to check every state possible. Use a visited array to store previous visited ( Not neccessary ) and a DP to store answer.
For $$$n == 1$$$ , simple formulae can be generated.
Then try to maximize position that can be 0, automatically the other thing happens.
For rest , first make n * m , st n < m, as ans does not change, Then do a DFS over every possible state by using left rotation and right rotation of bit ( L , R ,U , D, *). Use DP to store answer.
#include <bits/stdc++.h>
using namespace std;
bool seen[40][256][256];
int DP[40][256][256];
int func(int a, int b, int c) {
if (seen[a][b][c]) return DP[a][b][c];
seen[a][b][c] = true;
// Generate mask by left rot and right rot.
int y = (c | b | (b << 1) | (b >> 1)) & net;
if (p == m) {
if (y == net) {
return DP[a][b][c] = 0;
} else {
return DP[a][b][c] = INT_MAX;
}
}
int ans = INT_MAX;
for (int i = 0; i < (1<<n); i++) {
if (a == 0 || (y|i) == net) {
ans = min(ans, func(a+1, i, b) + __builtin_popcount(i));
}
}
return DP[a][b][c]= ans;
}
int main() {
//INPUT n ,m ;
if (n > m){
int temp = n;
n = m;
m = temp;
}
if (n == 1) {
cout << m-1 - (m-1)/3 << endl;
} //BEST CASE.
else {
net = (1<<n)-1;
int cal = func(0, 0, 0); //DP CASE
cal = n*m - cal;
cout << cal << endl;
}
}
Looking forward to it.
The participants need not be from the same college/institution/organization.
Hope this is as exciting as last year's.
Is it from 9pm or 10pm?
10 pm. Ignore the timing on the poster. sorry for the inconvenience.
Was $$${O(q*\sqrt{n}*log(n))}$$$ the intended complexity for Bhindi Master and Graph ?
nope
Most likely there is $$$O(nlog(n))$$$ solution, however $$$O(nlog^2(n))$$$ passes easily.
Here is O(nlog(n)) solution. https://www.codechef.com/viewsolution/30325628
Can you briefly explain your solution ?
lets put all the vertices in the new array in order of distance from root. i.e. all vertices with distance 1 will come first, then all vertices with distance 2 and so on. now for finding minimum distance from root we need to query minimum index in the new array such that value at this index> value of query. We can do this with binary search + query on segtree in O(log^2(n)). we can also do this by doing binary search query on segtree. the rest part of the problem can be solved with just a set.
I brute forced but it didn't gave me TLE but I was getting WA.
Can you please explain what I was doing wrong.
Approach : I listed nodes at each level in a array of vector.
I made an array which contains the smallest element value at among the nodes at that level using the indexes.
https://pastebin.com/ymNdB9Z3
Here's the code
Why did you store min elem at each level? You should have stored max at each level.
There may be a case as follows —
Level 1 values — { 3 }
Level 2 values — { 5, 11 }
Level 3 values — { 6, 7, 8}
If the query is 10, answer should be stored at level 2, but storing min as you have done will return -1.
I submitted using square root decomposition and it worked for me :)
How to solve Kem Party problem fast? My solution complexity is $$$O(n * m * min(n, m) * log n)$$$ with dynamic convex hull trick, which seems to be overkill...
I too used 2D-Fenwick Tree + Convex Hull Trick to solve in O(N*M*log^3n ). [Quite same in runtime i guess].
With random weights, i don't think that the lines will follows some property allowing any offline processing.
Great contest! Enjoyed the problems, even though I only solved 3. Can somebody explain the convex hull optimization trick used to solve Ken Party? Or show me a link that explains it? TIA
Can anyone please explain why I am getting WA in Bhindi Master And Graph, I store the nodes at each level and the max value at each level and then if max value of a level is greater than X, I print the smallest node with value>X.
Solution
First of all, the complexity of your solution is Q*N which is not in the time limit :/
now while you are updating the value of the node, you are changing the max if the current update is larger than max at that level, which is wrong, as there might be multiple nodes with same value at a certain level or maximum value at that level might decrease etc.
keep values available at each level to update the maximum (to correct the logic of your code still it will exceed the time limit), to improve the complexity you may refer to hint posted above :)