Hey all,
We are excited to invite everyone to the Quora Programming Challenge 2022, a free programming competition open to participants from around the world*! The competition will take place on February 5, 2022 from 14:00 to 18:00 (UTC + 00:00). We had a successful challenge last year with great participation and positive feedback for the problems, so we’re excited to do it again this year!
Quora (https://www.quora.com/) is a platform to ask questions, get useful answers, and share what you know with the world. In this contest, we include some problems inspired by real-world challenges that Quora engineers faced building and growing the product. In addition to competitive programming-style questions, there will also be some machine learning problems. We hope that this contest will be fun for everyone!
You will be given several algorithm problems and a few machine learning problems.
- Algorithm problems: These are competitive programming-style questions that have strictly algorithmic solutions. It is possible to achieve a full score on these problems.
- Machine Learning problems: These are problems around machine learning concepts. Scoring is problem-dependent, based on a scaled accuracy metric. It may not be possible to achieve a full score on these problems.
The problems were prepared by Quora employees including KhaledRezk, vlchen888, Myungwoo, Hwan Seung Yeo, Ryan Cheu, and me. They were tested by gafeol, huikang, and many other Quora employees.
The top contestants will be able to win the following prizes:
- 1st place: $3000 USD
- 2nd place: $2000 USD
- 3rd place: $1000 USD
- 4th to 10th place: $200 USD
- 11th to 20th place: $100 USD
- Top 100 places: Quora T-Shirt
Our recruiting team will also be reaching out to top participants for their interest in interviewing for roles at Quora. We recently became a remote-first company, so you don’t have to relocate to work with us.
Hope to see you at the contest!
Register here by February 3, 2022 16:00 (UTC + 00:00): https://www.quora.com/careers/challenge.
For any feedback or questions, please comment on this post or email: programming-challenge@quora.com.
*Except for excluded countries. Full details, including the dates and rules of the competition, can be found here
Great initiative
Hi all, I participated in this challenge last year. I got an interview and a shirt from the challenge.
I am currently two months into my new grad role at Quora. This is me with the shirt.
There are three of us are who are hired from the interviews from the competition, with a few more in the pipeline.
These are the last year's problems for reference, obtained from this Codeforces comment.
Feel free to reach out if you have any questions!
On what basis are participants divided into div 1 and div 2? I did not find any such preference during registration.
It was more like session one and session two, held at different times with different questions. Participants could choose to participate in either or both of the sessions. The intention is to make it more convenient for participants of different timezones.
This year we decided to have only one session, and they share one prize pool.
Is there somewhere we can submit solutions to last year's problems?
We will not provide a venue to submit solutions to the last year's problems. However, when we invite the participants to try out our contest environment nearer to the contest date, we may feature an easy problem from the last year.
You can refer to comments shared by other participants for some clues on how to solve them. Some of them may have shared their code too, and you can compare your code with theirs.
For ML problems, it is difficult to compare and see if your solution works because it involves a very customized checker and hidden datasets. You can refer to my solutions, which were pretty high scoring for the ML problems.
Ok, thanks.
Why are people from balkans not allowed to compete?
Upcoming Practice Session!
Registration will be open until February 3, 2022 16:00 UTC, so it’s not too late to sign up! We will be sending out the login credentials and instructions to access the contest platform shortly after the registration closes.
As a reminder, the challenge will take place on February 5th, 2022 14:00 — 18:00 UTC.
To help you get familiar with the platform before the contest, we will be holding a practice session on February 3, 2022 18:00 UTC to February 4, 2022 18:00 UTC where you can login to the contest platform using your login credentials, and try out the example problem. The example problem is not representative to the difficulty level of the contest, but hopefully this would be helpful for you to get used to the input / output mechanisms that will be used in the contest.
If you encounter any issues, please reach out to us at programming-challenge@quora.com.
Last Day Notice
Programming challenge will be held on February 5, 2022 from 14:00 to 18:00 (UTC + 00:00).
Don't forget to participate!
Should we have received the registration email already?
You asked in a perfect time, just around the announcement: https://qr.ae/pGExeF
(and for now yes, ofc)
What are the level of problems according to codeforces rating?
Hard to tell, there are easy to hard problems, as well as ML problems integrated into challenge
Will the real contest be held in same website as practice round?
If so, where will be able to see the standings? (as there was no standings in practice round)
Details are in here: https://qr.ae/pGExeF
Thank you so much for the amazing problems. Can we get something like an editorial after it ends?
I CAME TO WHINE
HOW THE FUCK DO YOU WRITE DCHT WITH ROLLBACK?
Test are weak, my solution with copying cht for every children got 100 lol
You can use HLD technique and have $$$O(n \log^2 n)$$$ solution.
I suppose that we need keep cht for every path?
Yes we have a list of chts and when we go down on a light path we make another one and add it to the end of the list, when we are done with that subtree we can just pop it. When we go down on a heavy edge we don't add anything. For every node we always use the last added cht.
You can use heavy light decomposition, maintaining O(log n) dynamic converx hull for chains from current node to root.
I got sick at the end so I wrote some decomposition of hulls which passed but it's O(NsqrtNlgN) at best considering the set's constant factor it should be a little more still it's fucked up that this passes.
I tried persistent Li Chao tree but it ran out of memory. I wonder if it's possible to get it within bounds...
What implementation did you use? I used persistent Li Chao tree using the implementation linked in the comments of https://mirror.codeforces.com/blog/entry/68363 and I got AC.
I rolled my own, and tried to optimize by using a vector + indices instead of pointers, but didn't work either.
Did you use long long for the line slopes/intercepts with the linked implementation? Or had to stick with int?
No, I changed everything to
int64_t
, and also changed the maximum from1e9
to4e18
.I did it. I created static array with 7'500'500 nodes instead of pointers.
I would get literally sick if I tried doing something like that :(
I used persistent Li Chao tree: https://mirror.codeforces.com/blog/entry/68363
This contest was the first time I have ever used this data structure on any problem, LOL
You can write Persistent LiChao tree. I actually wrote it but failed to get AC due to some formatting issues while reading input in java (subtask 2, file 21 and subtask 3, file 49).
Isn't there a simple and straightforward $$$O(n \log^2 n)$$$ solution? If you have vertices in dfs order, build a segment tree on it and store a CHT in every vertex. Now you only need to be able to add a new line (car) to a segment (which is adding a line to at most $$$\log n$$$ CHT's), and do point queries where you take the best value from every CHT on the way to the corresponding segment tree vertex.
I simply saved the changed values on the Li Chao Tree and then rollback. The complexity is O(nlogn)
tourist (Gennady Korotkevich) while submitting the last point on task to get 100.0 points instead of 99.0, that's was incredible remontada.
How to solve Xuora?
Case work (n = 4k, n = 4k+1, n = 4k+2, n = 4k+3)
Can you please explain, how will you find the (m — n) numbers.
I didn't solve it, but here's an idea I had after the contest ended:
If we consider some m, then we want to find (m — n) numbers <= m where xor(1..m) = xor(the numbers we choose). Let k = xor(numbers we choose).
We can get k like this: satisfy each bit from (msb, 0) in that order (msb is most significant bit). We can see that once we are done taking bits for some msb, we can jump down until the msb changes, and no matter what we choose we do not mess up the answer we already have.
The problem with this is we need at least bitcount(k) moves to make it work. What if (m — n) is less than this? We can combine some bits and take them all at once. This is because we can find any number < 2^(msb) in [1..m]. Then we need at least min(bitcount(k), 2) moves to make it work.
If $$$n$$$ is $$$4k + 3$$$, you're done. $$$\newline$$$ If $$$n$$$ is $$$4k$$$, $$$m = n + 1$$$. Remove 1. $$$\newline$$$ If $$$n$$$ is $$$4k + 2$$$, you can prove that unless $$$n + 2$$$ is of the form $$$2^k$$$, you can remove 2 numbers keeping $$$m = n + 2$$$. Otherwise, $$$m = n + 3$$$. $$$\newline$$$ Similarly, if $$$n$$$ is $$$4k + 1$$$, you can show that unless $$$n + 3$$$ is of the form $$$2^k$$$, you can remove 3 numbers keeping $$$m = n + 3$$$. Otherwise, $$$m = n + 4$$$.
In case anyone wants to upsolve the IP problem (not sure how strength of test data compares): https://codingcompetitions.withgoogle.com/kickstart/round/00000000004349ac/0000000000434880
My code passed the Google one but failed the Quora one :( can you share your code?
Why 96 for problem IP?
In my case, my solution was broken if one of the addresses started with 0.0.0.0 (and fixing that took me from 96 to 100) but not sure if it's the same for you.
could you please share the details of your implementation as I am still unable to figure out the bug in my code leading to 96?
can u share the code please
https://ideone.com/HuFtnH
One possible issue is that
(1 << 32)
doesn't work, you need to use(1LL << 32)
.I had 56 in problem IP and have no idea why. Did anyone experience a similar thing?
Question for anyone from quora, or anyone with knowledge of last year's contest result:
Upto what rank can people expect to get interview call from quora?
How to solve "subtracting?"
Congratulations on the only full solve for cake!
There are a few ways to subtract better than random
This requires some intuition on how classifiers, metrics and the black magic of gradient boosting decision tree works.
33 points: for each point, find the distance to the closest point of the same class. Keep $$$n-k$$$ points with the maximum value. (kind of "deduplicating" the points)
52 points: the same, but when calculating the value for each point $$$i$$$, only consider points $$$j > i$$$ (this way, if two points are close to each other, we don't remove both because of that, but only remove one).
100 points: first, pick around $$$0.5 \cdot (n-k)$$$ points using algorithm X, then pick the remaining $$$0.5 \cdot (n-k)$$$ points using the above method. (and do a lot of parameter tweaking)
Algorithm X: for each class, try to pick a representative subset of points of size $$$0.5 \cdot (n-k) / num_{classes}$$$. Start with an arbitrary point, then repeat adding the point with the largest sum (or min) of distances to the already picked points of the class.
What were your approaches to cake and coldstart? In particular, I saw you solved coldstart very quickly, but my approach required a lot of tweaking too, so I wonder if there's anything simple. (My approach was built around finding training data records with at least 3 or 4 pairs <person; upvoted> in common with the query, then taking some kind of an average.)
Cake: I modified bicsi's half-plane set: https://mirror.codeforces.com/blog/entry/61710. It maintains all half-planes that determine the border of the cake.
Unfortunately, the version linked in that post didn't seem to compile, so I ended up copying a working version from https://infoarena.ro/monitor?task=camera, and then modifying it to dynamically maintain the area.
For each employee, the idea is to first try the orientation of the plane that results in fewer half-planes being removed from the set. If that results in the remaining cake having less than half the area, we can afford to try the other orientation (and the number of vertices in the cake will halve). The runtime is $$$O(N\log N)$$$.
Unfortunately, I didn't understand the code well enough to implement this so I ended up just picking an arbitrary vertex of the convex hull and first trying the orientation that resulted in this vertex still being inside the cake, and then trying the other. Definitely hackable but okay in the average case.
I also ran into some floating-point issues (I think the
__float128
in the code below is necessary). It is probably possible to make this WA ......
Coldstart: All you needed to do was modify one of huikang's solutions to last year's Quora challenge. :)
Congrats on the win! For "subtracting" I spent the last 20 minutes or so just resubmitting my nondeterministic solution that usually earned zero points but did manage to increase my score by a few points more than once. I suppose I was rather lucky that this earned me any points at all ...
I also found it interesting that 20 of my points on "subtracting" came from printing out 0...k-1 ...
How to solve C?
Use FFT. $$$\newline$$$ $$$polyA(i) = 1$$$, if $$$s[i] = A$$$. Odd coefficients of $$$polyA * polyT$$$ give you the values where $$$A$$$ and $$$T$$$ match. Similarly compute this for $$$G$$$ and $$$C$$$, add and take max over the odd coefficients.
I had neither Karatsuba nor FFT in my library, so I quickly implemented Karatsuba and it was too slow.
Tried FFT, it was also too slow. I guess people have optimized implementations in their libs if it worked for them?
The limit on N was 300000, annoyingly only slightly above a power of two, hampering both Karatsuba and FFT. Changed the base case in Karatsuba from 32 to 40, still too slow.
Unrolled manually the 40-40-loop in the base case of Karatsuba, also taking into account that we need only the odd coefficients. And now it passed...
Not sure how it worked for other people, but my impression about that problem was that there was not much algorithmic thinking (the idea to use fast polynomial multiplication should be rather obvious for those who know the technique), more using prewritten algorithms and/or low-level optimizations.
I had to think about this problem a lot as I am not well versed with FFT or convolutions. But since I knew the definition of convolution, I was able to notice that property in the problem.
I have no idea how to calculate a convolution fast so I used the AtCoder Library
There was minimal implementation and the code ran pretty fast. I was only able to solve this "library" problem because of ACL. Overall it was more of algorithmic problem for me, so I liked it a lot.
Where can we find the full standing of the contest?
Top 150
Yes I know, I need the full standing not just the top 150
The reply here says: We may release the ranking when we finish vetting the solutions.
Thanks
In the tree problem (dfs from node 1) then for each node check all ancestors ans[node] = min(ans[node] , ans[ancestor] + R[ancestor] + C[ancestor] * distance) What's wrong with this? I couldn't pass first subtask
A node can take rent from any ancestors of its ancestor. in the sample test case, node 4 took rent from node 1 instead of its parent 5.
ancestor i mean any node up in the tree (parents of parents .... etc)
distance = distance from ancestor?
yes
It should be true, maybe overflow?
For those who did not participate the contest and would like to follow the discussion, here is the problem statements (thanks to rfpermen for downloading these)
What was the solution for DNA?
I see a lot of people solved it, but I still can't figure out a linear solution
It is a FFT problem.
Let $$$polyA$$$ be a sequence of numbers $$$a_0, a_1, \dots, a_{n-1}$$$ where $$$a_i=1$$$ if the $$$i$$$th letter in the string is "A" and $$$a_i=0$$$ otherwise. Make similar sequences for $$$polyT$$$, $$$polyG$$$, and $$$polyC$$$.
Now, take the convolution of $$$polyA$$$ and $$$polyT$$$ (this is where FFT comes in, because FFT calculates convolution very quickly). Let's say the convolution is the sequence $$$c_0, c_1, \dots, c_{2n-2}$$$. For any $$$1\leq i\leq n-1$$$, observe that $$$c_{2i-1}$$$ represents the number of A-T/T-A bonds that will occur when you fold the DNA string with $$$i$$$ bases on the left side of the fold.
Now, take the convolution of $$$polyG$$$ and $$$polyC$$$, and let's say the convolution is the sequence $$$d_0, \dots, d_{2n-2}$$$. By similar reasoning, $$$d_{2i-1}$$$ represents the number of G-C/C-G bonds that will occur when you fold the DNA string with $$$i$$$ bases on the left side of the fold.
Thus, the number of bonds that will occur when you fold the DNA string with $$$i$$$ bases on the left side of the fold is $$$c_{2i-1}+d_{2i-1}$$$, and from here it is very easy to find the $$$i$$$ which maximizes $$$c_{2i-1}+d_{2i-1}$$$ using a simple
for
loop. Since we only do two convolution operations on sequences of length $$$n$$$, the complexity is $$$O(n log n)$$$.Not even able to solve the first problem, the challenge is ended, can u share ur code here. (i mean the IP BLOCKs}
Any place for upsolving?
Also, picture is a standard problem, right? Count axis-aligned rectangles formed by line segments. I'm pretty sure I saw it at least once in a contest.
Have people received invitations for interviews or similar?