It's not really surprising that the form doesn't validate that the URL is a real profile URL, they did some rough validation and that's enough; do you expect forms to also automatically check that your City is a "real city" against some magical database before allowing your submission? No one ever does that.

LinkedIn profile is required because, clearly, Quora is running this (for free, with real prize money!) as a tool to recruit people to work there.

Hi, thanks for the question! This iteration of the challenge will contain problems that fall into two categories.

1. “Algorithm” problems: These are competitive programming-style questions that have strictly algorithmic solutions. It is possible to achieve a full score on these problems. Most of the problems will fall into this category.
2. “Machine Learning” problems: These are problems around machine learning concepts. Scoring is problem-dependent, but roughly would be based on some scaled accuracy metric. We do not guarantee that it is possible to achieve a full score on these problems.

I think a shirt like that mainly has value to you, so no one else can answer that question. Unless you mean the monetary value of a shirt which can't be over 15 dollars (and could be a lot less)

Am I right that all problems allow partial scoring, and that wrong attempts don't increase penalty? Will there be a limit on a number of submissions per problem?

29 January 2021 — "In the week before the contest, you should receive another email from us with the link to the contest platform and instructions on how to log in. We will use the same link for both divisions of the contest, and you will be able to log in to either one (or both) of the divisions."

I have not received another email ...

I thought we had all of February 5th (until 23:59 UTC) at least to register... ):

I thought the same thing, two rounds missed.

+1, can the registration time be extended? :(

Doubling the time limit is understandable but not needed; doubling the memory limit is just weird.

There isn't a custom invocation like what Codeforces have that can show us what is the error code :/

Actually, I missed the practice session. Can you tell me that what should be the name of class for Java solution ? Or can we name it anything ?

seeing same type of comments nowadays It feels that anton have redefined competitive programming.

It is bipartite but your complexity is wrong.

Yeah I did the same. But I dont know anything about Maxmimum Independent set. So I just copied some template from github.

I am really curious about the expected solution.

Yes, the graph is bipartite. But I think you are assuming that you can always get a maximum independent set in a bipartite graph by taking all the nodes in one of it sides (same color). That's clearly not true.

I think you have to find the maximum independent set instead of choosing only one color.

Maximum independent set = total vertexes — edges in maximum matching

Yea it is, you just need to maintain the current type of connected components in each column and also which squares in the column are "active".

I didn't end up with an RTE, but I got WA7 on the first subtask and couldn't finish debugging before the end of the round. I'm also looking for a countercase; I've stress tested my solution on thousands of cases against a slow solution I wrote and the correct solutions I've just been sent and can't find a case that I WA. If anyone happens to have gotten WA7/RTE7, found a countercase, and successfully debugged their solution, that case would be very much appreciated!

One thing that I missed in first attempt and got WA at test 7 was that guards will also be stopped by the walls. So you can't just check manhattan distance of a cell from a guard and determine its feasibility.

I got AC by assuming each column originally followed a normal distribution with its post-flip mean and standard deviation and picking the rows where the product of the normal PMF corresponding to each value assuming the row is not flipped divided by the product of the normal PMF corresponding to each value assuming the row is flipped is minimized. Intuitively, I assumed that the flips didn't substantially change the overall distribution of each column and then picked the rows where flipping most drastically increases the probability that the values in the row appear in their corresponding distributions.

Here's my code (excluding my template): https://pastebin.com/YtYNwPh5

I computed the mean and standard deviation of each column. Then, for each row $$$r$$$, let $$$f(r)$$$ denote the sum of squared distance from 0.5 of all the value of the cumulative normal distribition on each value in the row (drawn from the estimated normal distribution for each column). Do the same for reversed row $$$r'$$$ and finally sort all rows by the value $$$f(r')-f(r)$$$ and output the first $$$b$$$ rows.

thanks!

And here is the second division problemset.

For the second last problem, we want to select the reversed rows. A cell is misplaced if its value deviates from the mean of the column. We do want to normalise the deviation by dividing with the standard deviation of the column. The rows with many very misplaced cells are likely reversed.

We can reverse the b worst rows, and the result was already quite good (around 70?).

The issue with reversing many rows at once is that we might reverse the wrong row. One way is to reverse one row at a time, and recalculate the mean and standard deviation. But this is too slow.

The middle ground is to reverse a portion of the b rows, in maybe 16 portions. I scored 99 points (even though it displayed 100 on the console).

The "ML technique" here is statistical knowledge of mean and standard deviation.

Code: https://github.com/tonghuikang/codecomp/blob/quora-2021-1/template/f.py

For the last problem, I used LightGBM (which is one the packages Quora allows, and is faster than XGBoost).

The challenge is feature engineering. Each data should have the same set of features, but what we see in the data is that each user can visit multiple sites. What I did is to cycle through the visits — each user will revisit the first site again. For the time, I calculated the time difference, and cycle. Each data will have 200+200 features.

I was prepared to handle more feature engineering and fine-tune the threshold, but I got full marks after a few tries.

The "ML technique" feature engineering, and trust the black box GBDT model and pray.

Code: https://github.com/tonghuikang/codecomp/blob/quora-2021-1/template/spam.ipynb

For each cell $$$c$$$ that a guard with radius $$$r$$$ is on, set $$$dist[c] = -(r+1)$$$. Now do a multisource shortest path using a priority queue starting from all these cells. For any cell, if the shortest distance is found to be less than 0 at the end, then it is covered by atleast one guard.

Hey, I used multisource BFS, pushed the coordinate of every guard in the queue with their distance, and mark the cell visited if a guard can reach the cell. Now, if our source is visited means at least one guard can reach our initial position and we can't go any further, so "IMPOSSIBLE". If our destination is visited means we can't go to destination, so "IMPOSSIBLE" and if all the neighbors of destination are visited then there is no chance to go to destination cell so the answer is "IMPOSSIBLE". If none of the conditions is satisfied above then apply simple BFS from source to destination. If we can reach the destination cell then print the distance else "IMPOSSIBLE".

It's Out Now: Quora Programming Challenge 2021 Full Ranking (https://docs.google.com/spreadsheets/d/1xVzryOFrhq7G9YpePcstexg8owvQPyev7EOXogdaI2c/edit?usp=sharing)

I have input, not sure if there was an output

You only need to keep track of the enemy with the longest remaining range if starting from that cell. That way you only need to propagate from that cell once.

Same, I found a solution on Google, but I could only get the first subtask because I had some weird bug causing me to WA on the second subtask.

Best I could find was this link in Russian, which I tried to piece together with Google Translate :)

https://codeforces.me/blog/entry/86539?#comment-758158

Jonathan has uploaded it on his website

https://jonathanirvin.gs/files/division2_3d16774b0423.pdf

you can find div2 problems in this pdf file **https://drive.google.com/file/d/1ztxHk9Y0Knkm662F2s5dEIOYiP-a7VSk/view?usp=sharing**

Here is my code for Problem Escape (excluding my template):

const int mxN =1e3+2 ;
const int di[4]={1,0,-1,0},dj[4]={0,-1,0,1} ;
int n,m,K,d[mxN][mxN];
string s[mxN] ;
bool e(int i,int j){
	return(i<n&&j<m&&i>=0&&j>=0&&s[i][j]!='#') ;
}
void solve(){		
	read(n,m,K) ;
	FOR(n)
		read(s[i]) ;
	queue<ar<int,3>>qu  ;
	FOR(K){
		int a,b,c ;read(a,b,c) ;
		--a;--b ;
		qu.push({a,b,c}) ;
		s[a][b]='#' ;
	}
	int si,sj,ti,tj ;
	FOR(n){
		FOR(j,m){
			if(s[i][j]=='S')
				si=i,sj=j,s[i][j]='.';
			if(s[i][j]=='E')
				ti=i,tj=j,s[i][j]='.' ;
		}
	}
	while(qu.size()){
		ar<int,3> u = qu.front() ;
		qu.pop() ;
		if(u[2]==0)
			continue ;
		FOR(k,4){
			int ni=u[0]+di[k],nj=u[1]+dj[k] ;
			if(!e(ni,nj))
				continue  ;
			qu.push({ni,nj,u[2]-1}) ;
			s[ni][nj]='#' ;
		}

	}
	if(s[si][sj]=='#')
		pf("IMPOSSIBLE") ;
	queue<ar<int,2>>qe  ;
	mems(d,-1) ;
	d[si][sj]=0 ;
	qe.push({si,sj}) ;
	while(qe.size()){
		ar<int,2> u = qe.front() ;
		qe.pop() ;
		FOR(k,4){
			int ni=u[0]+di[k],nj=u[1]+dj[k] ;
			if(!e(ni,nj))
				continue ;
			qe.push({ni,nj}) ;
			d[ni][nj]=d[u[0]][u[1]]+1 ;
			s[ni][nj]='#' ;
		}
	}
	if(d[ti][tj]==-1)
		pf("IMPOSSIBLE") ;
	pf(d[ti][tj]) ;
}

EDIT: It seems the test-cases for this problems were weak, thanks to quinoa for giving a counter case for the above solution. The following solution seems correct to us now, though confirmation of the same is appreciated.

#include"bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")
typedef long long ll ;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define CS custom_hash
#define vt vector 
#define loop(i,a,b) for(ll i=a ;i<b;i++)
#define For(i,n) for(int i=0;i<(ll)n;i++)
#define Rev(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,n) for(int i=1;i<=n;++i)
#define F first
#define S second
#define pb push_back
#define em emplace_back
#define all(v) (v).begin(),(v).end()                                            
#define mems(x, y) memset(x, y, sizeof(x))
#define sz(x) (int)(x).size()
#define mp(a,b) make_pair(a,b)
#define po(n) cout << n <<"\n " 
#define ar array
#define endl "\n" 
#define PI acos(-1) 
#define umap unordered_map
#define gmap gp_hash_table
#define ld long double 
#define SA(n) __builtin_popcountll(n) 
#define LB lower_bound  
#define UB upper_bound 
// debugger credits: https://codeforces.me/blog/entry/68809 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
template <typename T, typename V>
void mdebug(map<T,vector<V>>m){
  for(auto x:m){
    cerr << x.first << " : [ " ;
    for(auto c:x.second)
      cerr << c << " ";
    cerr << "]"<<'\n' ;
  }
}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
//#pragma GCC optimize "trapv"
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//template credits :William Lin(tmwilliamlin168)
#define F_OR(i, a, b, s) for (int i = (a); ((s) > 0 ? i < (b) : i > (b)); i += (s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)
template<class T> bool umin(T& a, const T& b) {
	return b<a?a=b, 1:0;
}
template<class T> bool umax(T& a, const T& b) { 
	return a<b?a=b, 1:0;
}
template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(ar<A, S>& a);
template<class T> void read(T& x) {
	cin >> x;
}
void read(double& d) {
	string t;
	read(t);
	d=stod(t);
}
void read(long double& d) {
	string t;
	read(t);
	d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
	read(h);
	read(t...);
}
template<class A> void read(vt<A>& x) {
	EACH(a, x)
		read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
	EACH(a, x)
		read(a);
}
string to_string(char c) {
	return string(1, c);
}
string to_string(bool b) {
	return b?"true":"false";
}
string to_string(const char* s) {
	return string(s);
}
string to_string(string s) {
	return s;
}
string to_string(vt<bool> v) {
	string res;
	FOR(sz(v))
		res+=char('0'+v[i]);
	return res;
}

template<size_t S> string to_string(bitset<S> b) {
	string res;
	FOR(S)
		res+=char('0'+b[i]);
	return res;
}
template<class T> string to_string(T v) {
    bool f=1;
    string res;
    EACH(x, v) {
		if(!f)
			res+=' ';
		f=0;
		res+=to_string(x);
	}
    return res;
}

template<class A> void pff(A x) {
	cout << to_string(x);
}
template<class H, class... T> void pff(const H& h, const T&... t) { 
	pff(h);
	pff(t...);
}
void print() {
	pff("\n");
}
template<class H, class... T> void print(const H& h, const T&... t) { 
	pff(h);
	if(sizeof...(t))
		pff(' ');
	print(t...);
}
struct PH{
  size_t operator()(const pair<int,int>&x)const{
    size_t ans=0;
    for(int i=0;i<x.first;i++)
      ans+=x.second;
    return ans;
  }
};
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
// void DBG() {
// 	cerr << "]" << endl;
// }
// template<class H, class... T> void DBG(H h, T... t) {
// 	cerr << to_string(h);
// 	if(sizeof...(t))
// 		cerr << ", ";
// 	DBG(t...);
// }
// // #ifdef _DEBUG
// #define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
// // #else
// // #define dbg(...) 0
// // #endif

template<class T> void offset(ll o, T& x) {
	x+=o;
}
template<class T> void offset(ll o, vt<T>& x) {
	EACH(a, x)
		offset(o, a);
}
template<class T, size_t S> void offset(ll o, ar<T, S>& x) {
	EACH(a, x)
		offset(o, a);
}
template<class T> void fk(T a) { 
  print(a) ;
  exit(0) ;
}
#define pf(n) return print(n)
#define int ll 
long const M=1e9+7;
const ll INF =1e18;
// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).
//Syntax to create a min heap for priority queue
// priority_queue <T, vector<T>, greater<T>>pq ;

//make sure to clear the adjacency list for every test case 
// check mxN size 
//check if numbers are big use powl,sqrtl,builtin_popcountll()...... 
const int mxN =1e3+2 ;
const int di[4]={1,0,-1,0},dj[4]={0,-1,0,1} ;
int n,m,K,d[mxN][mxN];
string s[mxN] ;
bool e(int i,int j){
	return(i<n&&j<m&&i>=0&&j>=0&&s[i][j]!='#') ;
}
void solve(){		
	read(n,m,K) ;
	FOR(n)
		read(s[i]) ;
	priority_queue<ar<int,3>>qu  ;
	FOR(K){
		int a,b,c ;read(a,b,c) ;
		--a;--b ;
		qu.push({c,a,b}) ;
		s[a][b]='#' ;
	}
	int si,sj,ti,tj ;
	FOR(n){
		FOR(j,m){
			if(s[i][j]=='S')
				si=i,sj=j,s[i][j]='.';
			if(s[i][j]=='E')
				ti=i,tj=j,s[i][j]='.' ;
		}
	}
	while(qu.size()){
		ar<int,3> u = qu.top() ;
		qu.pop() ;
		if(u[0]==0)
			continue ;
		FOR(k,4){
			int ni=u[1]+di[k],nj=u[2]+dj[k] ;
			if(!e(ni,nj))
				continue  ;
			qu.push({u[0]-1,ni,nj,}) ;
			s[ni][nj]='#' ;
		}

	}
	if(s[si][sj]=='#')
		pf("IMPOSSIBLE") ;
	queue<ar<int,2>>qe  ;
	mems(d,-1) ;
	d[si][sj]=0 ;
	qe.push({si,sj}) ;
	while(qe.size()){
		ar<int,2> u = qe.front() ;
		qe.pop() ;
		FOR(k,4){
			int ni=u[0]+di[k],nj=u[1]+dj[k] ;
			if(!e(ni,nj))
				continue ;
			qe.push({ni,nj}) ;
			d[ni][nj]=d[u[0]][u[1]]+1 ;
			s[ni][nj]='#' ;
		}
	}
	if(d[ti][tj]==-1)
		pf("IMPOSSIBLE") ;
	pf(d[ti][tj]) ;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  //cout << setprecision(20) << fixed ;
  int T=1;
	// read(T);
	FOR(_,T){
		// pff("Case #", _+1, ": ");
		solve();
	}
	return 0;
}

Datacenter: transform each coordinate (x, y) into (x + y, x — y). The problem is now equivalent to finding the datacenter i that minimizes

which is much nicer to handle: precompute some prefix / suffix sum and iterate through each possible datacenter as the choice.

Skyscraper: maintain a segment tree where each node contains the maximum height (and possibly the minimum height, not sure if this is needed). The goal is, for a skyscraper i, to quickly find the minimum and maximum indices L and R such that all skyscrapers within [L; R] have heights no more than that of i. You can adapt the segment tree to quickly find these indices in O(log N) time.

We were tasked to predict the missing word in the sentence.

When I want to predict the missing word b in a triplet a,b,c — I consider for every possible b, the frequency of (a,b), the frequency of (b,c) and the freqency of (a,b,c). The candidate word for b that appears the most frequently will be my prediction.

It makes sense if we give greater weights to (a,b,c) because it is less likely to appear compared to (a,b) or (b,c). I count the freqency every appearance of (a,b,c) 10 times rather than once that I did for (a,b) and (b,c). This scored around 47/100 points.

To get 78/100 points, I considered two words before and two words after the missing word. In the final minutes of the contest, I was fine-tuning the weights and submitted the code repeatedly.

Code: https://github.com/tonghuikang/codecomp/blob/quora-2021-2/template/f.py

It is also possible to consider up to 30 characters before and after for a slightly higher score at a very little increase in complexity, but my code was not structured to do that.

For the full score, I think we need to use a neural network model. The general problem here is masked language encoding.

https://keras.io/examples/nlp/masked_language_modeling/

There are readily available templates out there, but it needs to download billon-parameter models which is not allowed by the online judge. We need to build (or copy) a downsized model that is suitable for the dataset.

I think I got lucky when hitting high score pretty quickly.

First I got 70 pts by keeping track of a frequency table of all 2-gram (an ordered pair of word (x, y)), and for each possible candidate w, its score is freq (p, w) * freq (w, r) where p and r are the word before and after w, respectively (if there's no such word p/r or the pair doesn't exist in the frequency table, assign the weight of 1 for that pair).

Return the word of highest score.

I got 82 by improving the above idea with including the 3-grams.

congrats !

Did you get any link to track the T-shirt? (cause no link sent to me)