### osmanorhan's blog

By osmanorhan, history, 4 months ago,

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.

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.
2. 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: [email protected].

*Except for excluded countries. Full details, including the dates and rules of the competition, can be found here

• +128

 » 4 months ago, # |   +5 Great initiative
 » 4 months ago, # |   -7 Great, but Cuba isn't an available country :'(
 » 4 months ago, # |   +47 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!
•  » » 4 months ago, # ^ | ← Rev. 2 →   +12 On what basis are participants divided into div 1 and div 2? I did not find any such preference during registration.
•  » » » 4 months ago, # ^ |   +16 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.
 » 4 months ago, # |   +8 Is there somewhere we can submit solutions to last year's problems?
•  » » 4 months ago, # ^ |   0 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.
•  » » » 4 months ago, # ^ |   0 Ok, thanks.
 » 4 months ago, # |   0 Why are people from balkans not allowed to compete?
»
4 months ago, # |
+26

## 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 [email protected].

»
3 months ago, # |
+11
##### 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!

•  » » 3 months ago, # ^ |   +5 Should we have received the registration email already?
•  » » » 3 months ago, # ^ |   0 You asked in a perfect time, just around the announcement: https://qr.ae/pGExeF(and for now yes, ofc)
 » 3 months ago, # |   0 What are the level of problems according to codeforces rating?
•  » » 3 months ago, # ^ |   0 Hard to tell, there are easy to hard problems, as well as ML problems integrated into challenge
 » 3 months ago, # |   0 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)
•  » » 3 months ago, # ^ |   0 Details are in here: https://qr.ae/pGExeF
 » 3 months ago, # |   +7 Thank you so much for the amazing problems. Can we get something like an editorial after it ends?
 » 3 months ago, # |   +23 I CAME TO WHINEHOW THE FUCK DO YOU WRITE DCHT WITH ROLLBACK?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +14 Test are weak, my solution with copying cht for every children got 100 lol
•  » » 3 months ago, # ^ | ← Rev. 2 →   +14 You can use HLD technique and have $O(n \log^2 n)$ solution.
•  » » » 3 months ago, # ^ |   0 I suppose that we need keep cht for every path?
•  » » » » 3 months ago, # ^ |   0 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.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +5 You can use heavy light decomposition, maintaining O(log n) dynamic converx hull for chains from current node to root.
•  » » » 3 months ago, # ^ |   0 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.
•  » » 3 months ago, # ^ |   0 I tried persistent Li Chao tree but it ran out of memory. I wonder if it's possible to get it within bounds...
•  » » » 3 months ago, # ^ |   0 What implementation did you use? I used persistent Li Chao tree using the implementation linked in the comments of https://codeforces.cc/blog/entry/68363 and I got AC.
•  » » » » 3 months ago, # ^ |   0 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?
•  » » » » » 3 months ago, # ^ |   0 No, I changed everything to int64_t, and also changed the maximum from 1e9 to 4e18.
•  » » » 3 months ago, # ^ |   0 I did it. I created static array with 7'500'500 nodes instead of pointers.
•  » » » » 3 months ago, # ^ |   0 I would get literally sick if I tried doing something like that :(
•  » » 3 months ago, # ^ |   +15 I used persistent Li Chao tree: https://codeforces.cc/blog/entry/68363This contest was the first time I have ever used this data structure on any problem, LOL
•  » » 3 months ago, # ^ |   0 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).
•  » » 3 months ago, # ^ | ← Rev. 2 →   +31 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.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +5 I simply saved the changed values on the Li Chao Tree and then rollback. The complexity is O(nlogn)
 » 3 months ago, # |   +70 tourist (Gennady Korotkevich) while submitting the last point on task to get 100.0 points instead of 99.0, that's was incredible remontada.
 » 3 months ago, # | ← Rev. 2 →   0 How to solve Xuora?
•  » » 3 months ago, # ^ |   +14 Case work (n = 4k, n = 4k+1, n = 4k+2, n = 4k+3)
•  » » » 3 months ago, # ^ |   0 Can you please explain, how will you find the (m — n) numbers.
•  » » » » 3 months ago, # ^ |   +3 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.
•  » » 3 months ago, # ^ | ← Rev. 4 →   +9 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$.
 » 3 months ago, # |   +30 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
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 My code passed the Google one but failed the Quora one :( can you share your code?
 » 3 months ago, # |   0 Why 96 for problem IP?
•  » » 3 months ago, # ^ |   +3 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.
•  » » » 3 months ago, # ^ |   0 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?
•  » » » 3 months ago, # ^ |   0 can u share the code please
•  » » » » 3 months ago, # ^ |   0
•  » » 3 months ago, # ^ |   +32 One possible issue is that (1 << 32) doesn't work, you need to use (1LL << 32).
•  » » » 3 months ago, # ^ |   0 I had 56 in problem IP and have no idea why. Did anyone experience a similar thing?
 » 3 months ago, # |   0 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?
 » 3 months ago, # |   +11 How to solve "subtracting?"
•  » » 3 months ago, # ^ |   +26 Congratulations on the only full solve for cake!There are a few ways to subtract better than random From classes that are overrepresented (this was most effective in internal testing) From points of the same class that are close to each other From points that are giving the strongest and correct prediction if evaluated with the trained model This requires some intuition on how classifiers, metrics and the black magic of gradient boosting decision tree works.
•  » » 3 months ago, # ^ |   +40 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 in common with the query, then taking some kind of an average.)
•  » » » 3 months ago, # ^ | ← Rev. 8 →   +28 Cake: I modified bicsi's half-plane set: https://codeforces.cc/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 ... Cake Code... #include using namespace std; using ll = long long; using db = long double; // or double, if TL is tight using str = string; // yay python! // pairs using pi = pair; using pl = pair; using pd = pair; #define mp make_pair #define f first #define s second #define tcT template using V = vector; tcT, size_t SZ> using AR = array; using vi = V; using vb = V; using vl = V; using vd = V; using vs = V; using vpi = V; using vpl = V; using vpd = V; // vectors // oops size(x), rbegin(x), rend(x) need C++17 #define sz(x) int((x).size()) #define bg(x) begin(x) #define all(x) bg(x), end(x) #define rall(x) x.rbegin(), x.rend() #define sor(x) sort(all(x)) #define rsz resize #define ins insert #define pb push_back #define eb emplace_back #define ft front() #define bk back() #define lb lower_bound #define ub upper_bound tcT> int lwb(V& a, const T& b) { return int(lb(all(a),b)-bg(a)); } tcT> int upb(V& a, const T& b) { return int(ub(all(a),b)-bg(a)); } // loops #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) #define R0F(i,a) ROF(i,0,a) #define rep(a) F0R(_,a) #define each(a,x) for (auto& a: x) const int MOD = 1e9+7; // 998244353; const int MX = 2e5+5; const ll BIG = 1e18; // not too close to LLONG_MAX const db PI = acos((db)-1); const int dx[4]{1,0,-1,0}, dy[4]{0,1,0,-1}; // for every grid problem!! mt19937 rng(0); template using pqg = priority_queue,greater>; // bitwise ops // also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set constexpr int bits(int x) { // assert(x >= 0); // make C++11 compatible until USACO updates ... return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x)) constexpr int p2(int x) { return 1<0&&a%b); } // divide a by b rounded up ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down tcT> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } // set a = min(a,b) tcT> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } // set a = max(a,b) tcTU> T fstTrue(T lo, T hi, U f) { ++hi; assert(lo <= hi); // assuming f is increasing while (lo < hi) { // find first index such that f is true T mid = lo+(hi-lo)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; } tcTU> T lstTrue(T lo, T hi, U f) { --lo; assert(lo <= hi); // assuming f is decreasing while (lo < hi) { // find first index such that f is true T mid = lo+(hi-lo+1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; } tcT> void remDup(vector& v) { // sort and remove duplicates sort(all(v)); v.erase(unique(all(v)),end(v)); } tcTU> void erase(T& t, const U& u) { // don't erase auto it = t.find(u); assert(it != end(t)); t.erase(it); } // element that doesn't exist from (multi)set #define tcTUU tcT, class ...U inline namespace Helpers { //////////// is_iterable // https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable // this gets used only when we can call begin() and end() on that type tcT, class = void> struct is_iterable : false_type {}; tcT> struct is_iterable())), decltype(end(declval())) > > : true_type {}; tcT> constexpr bool is_iterable_v = is_iterable::value; //////////// is_readable tcT, class = void> struct is_readable : false_type {}; tcT> struct is_readable> declval()), istream&> > > : true_type {}; tcT> constexpr bool is_readable_v = is_readable::value; //////////// is_printable // // https://nafe.es/posts/2020-02-29-is-printable/ tcT, class = void> struct is_printable : false_type {}; tcT> struct is_printable()), ostream&> > > : true_type {}; tcT> constexpr bool is_printable_v = is_printable::value; } using R = long double; inline namespace Input { void re(R& r) { db d; cin >> d; r = d; } tcT> constexpr bool needs_input_v = !is_readable_v && is_iterable_v; tcTUU> void re(T& t, U&... u); tcTU> void re(pair& p); // pairs // re: read tcT> typename enable_if,void>::type re(T& x) { cin >> x; } // default tcT> void re(complex& c) { T a,b; re(a,b); c = {a,b}; } // complex tcT> typename enable_if,void>::type re(T& i); // ex. vectors, arrays tcTU> void re(pair& p) { str x,y; re(x,y); p.f = stold(x); p.s = stold(y); } tcT> typename enable_if,void>::type re(T& i) { each(x,i) re(x); } tcTUU> void re(T& t, U&... u) { re(t); re(u...); } // read multiple // rv: resize and read vectors void rv(size_t) {} tcTUU> void rv(size_t N, V& t, U&... u); template void rv(size_t, size_t N2, U&... u); tcTUU> void rv(size_t N, V& t, U&... u) { t.rsz(N); re(t); rv(N,u...); } template void rv(size_t, size_t N2, U&... u) { rv(N2,u...); } // dumb shortcuts to read in ints void decrement() {} // subtract one from each tcTUU> void decrement(T& t, U&... u) { --t; decrement(u...); } #define ints(...) int __VA_ARGS__; re(__VA_ARGS__); #define int1(...) ints(__VA_ARGS__); decrement(__VA_ARGS__); } inline namespace ToString { tcT> constexpr bool needs_output_v = !is_printable_v && is_iterable_v; // ts: string representation to print tcT> typename enable_if,str>::type ts(T v) { stringstream ss; ss << fixed << setprecision(15) << v; return ss.str(); } // default tcT> str bit_vec(T t) { // bit vector to string str res = "{"; F0R(i,sz(t)) res += ts(t[i]); res += "}"; return res; } str ts(V v) { return bit_vec(v); } template str ts(bitset b) { return bit_vec(b); } // bit vector tcTU> str ts(pair p); // pairs tcT> typename enable_if,str>::type ts(T v); // vectors, arrays tcTU> str ts(pair p) { return "("+ts(p.f)+", "+ts(p.s)+")"; } tcT> typename enable_if,str>::type ts_sep(T v, str sep) { // convert container to string w/ separator sep bool fst = 1; str res = ""; for (const auto& x: v) { if (!fst) res += sep; fst = 0; res += ts(x); } return res; } tcT> typename enable_if,str>::type ts(T v) { return "{"+ts_sep(v,", ")+"}"; } // for nested DS template typename enable_if,vs>::type ts_lev(const T& v) { return {ts(v)}; } template typename enable_if,vs>::type ts_lev(const T& v) { if (lev == 0 || !sz(v)) return {ts(v)}; vs res; for (const auto& t: v) { if (sz(res)) res.bk += ","; vs tmp = ts_lev(t); res.ins(end(res),all(tmp)); } F0R(i,sz(res)) { str bef = " "; if (i == 0) bef = "{"; res[i] = bef+res[i]; } res.bk += "}"; return res; } } inline namespace Output { template void pr_sep(ostream& os, str, const T& t) { os << ts(t); } template void pr_sep(ostream& os, str sep, const T& t, const U&... u) { pr_sep(os,sep,t); os << sep; pr_sep(os,sep,u...); } // print w/ no spaces template void pr(const T&... t) { pr_sep(cout,"",t...); } // print w/ spaces, end with newline void ps() { cout << "\n"; } template void ps(const T&... t) { pr_sep(cout," ",t...); ps(); } // debug to cerr template void dbg_out(const T&... t) { pr_sep(cerr," | ",t...); cerr << endl; } void loc_info(int line, str names) { cerr << "Line(" << line << ") -> [" << names << "]: "; } template void dbgl_out(const T& t) { cerr << "\n\n" << ts_sep(ts_lev(t),"\n") << "\n" << endl; } #ifdef LOCAL #define dbg(...) loc_info(__LINE__,#__VA_ARGS__), dbg_out(__VA_ARGS__) #define dbgl(lev,x) loc_info(__LINE__,#x), dbgl_out(x) #else // don't actually submit with this #define dbg(...) 0 #define dbgl(lev,x) 0 #endif const clock_t beg = clock(); #define dbg_time() dbg((db)(clock()-beg)/CLOCKS_PER_SEC) } inline namespace FileIO { void setIn(str s) { freopen(s.c_str(),"r",stdin); } void setOut(str s) { freopen(s.c_str(),"w",stdout); } void setIO(str s = "") { cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams // cin.exceptions(cin.failbit); // throws exception when do smth illegal // ex. try to read letter into int if (sz(s)) setIn(s+".in"), setOut(s+".out"); // for old USACO } } // #include // using namespace std; namespace Retro { using T = R; using T2 = R; using T4 = R; const T2 INF = 2e6; struct Line { T a, b; T2 c; }; bool operator==(const Line& x, const Line& y) { return x.a == y.a && x.b == y.b && x.c == y.c; } bool operator<(Line m, Line n) { auto half = [&](Line m) { return m.b < 0 || m.b == 0 && m.a < 0; }; return make_tuple(half(m), (T2)m.b * n.a) < make_tuple(half(n), (T2)m.a * n.b); } tuple LineIntersection(Line m, Line n) { T2 d = (T2)m.a * n.b - (T2)m.b * n.a; // assert(d); T4 x = (T4)m.c * n.b - (T4)m.b * n.c; T4 y = (T4)m.a * n.c - (T4)m.c * n.a; return {x, y, d}; } Line LineFromPoints(T x1, T y1, T x2, T y2) { T a = y1 - y2, b = x2 - x1; T2 c = (T2)a * x1 + (T2)b * y1; return {a, b, c}; } // ostream& operator<<(ostream& out, Line l) { // out << "Line " << l.a << " " << l.b << " " << -l.c; // // out << "(" << l.a << " * x + " << l.b << " * y <= " << l.c << ")"; // return out; // } V deleted; struct HalfplaneSet : multiset { __float128 total = 0; HalfplaneSet() { auto it = insert({+1, 0, INF}); add_contrib(it, 1); it = insert({0, +1, INF}); add_contrib(it, 1); it = insert({-1, 0, INF}); add_contrib(it, 1); it = insert({0, -1, INF}); add_contrib(it, 1); // dbg(total); }; auto adv(auto it, int z) { // z = {-1, +1} while (z != 0) { if (z < 0) ++z, it = --(it == begin() ? end() : it); else --z, it = (++it == end() ? begin() : it); } return it; } void contrib(Line a, Line b, Line c, int sgn) { T4 x1, y1, x2, y2; T2 d1, d2; tie(x1, y1, d1) = LineIntersection(a, b); tie(x2, y2, d2) = LineIntersection(b, c); // if (abs(d1) < 1e-9 || abs(d2) < 1e-9) return; R er = sgn * (x1 * y2 - x2 * y1) / d1 / d2; if (!(-1e25 <= er && er <= 1e25)) return; total += er; } bool chk(auto it) { Line l = *it, pl = *adv(it, -1), nl = *adv(it, +1); T4 x, y; T2 d; tie(x, y, d) = LineIntersection(pl, nl); // auto [x, y, d] = LineIntersection(pl, nl); T4 sat = l.a * x + l.b * y - (T4)l.c * d; if (d < 0 && sat < 0) { each(t,*this) deleted.pb(t); return clear(), 0; // unsat } if ((d > 0 && sat <= 0) || (d == 0 && sat < 0)) { deleted.pb(*it); add_contrib(it, -1); return erase(it), 1; } return 0; } tuple get_vertex() { return LineIntersection(*begin(), *next(begin())); } void add_contrib(multiset::iterator it, int sgn) { // dbg("BEF",total); // cout << *it << "\n"; if (size() >= 4) { contrib(*adv(it, -2), *adv(it, -1), *adv(it, 1), -sgn); contrib(*adv(it, -1), *adv(it, 1), *adv(it, 2), -sgn); } // dbg("MID",total); if (size() >= 3) { contrib(*adv(it,-2), *adv(it,-1), *it, sgn); contrib(*adv(it,-1), *it, *adv(it,1), sgn); contrib(*it,*adv(it,1),*adv(it,2), sgn); } // dbg("AFT",total); } void Cut(Line l) { // add ax + by <= c if (empty()) return; auto it = insert(l); // dbg("BEFORE", total); add_contrib(it, 1); // dbg("AFTER", total); if (chk(it)) return; for (int z : {-1, +1}) while (size() && chk(adv(it, z))); } // db Maximize(T a, T b) { // max ax + by // if (empty()) return -1/0.; // auto it = lower_bound({a, b}); // if (it == end()) it = begin(); // auto [x, y, d] = LineIntersection(*adv(it, -1), *it); // return (1.0 * a * x + 1.0 * b * y) / d; // } db Area() { if (empty()) return 0; return this->total * 0.5; // // return this->total * 0.5; // db total = 0.; // for (auto it = begin(); it != end(); ++it) { // T4 x1, y1, x2, y2; T2 d1, d2; // tie(x1, y1, d1) = LineIntersection(*adv(it, -1), *it); // tie(x2, y2, d2) = LineIntersection(*it, *adv(it, +1)); // // auto [x1, y1, d1] = LineIntersection(*adv(it, -1), *it); // // auto [x2, y2, d2] = LineIntersection(*it, *adv(it, +1)); // total += (1.0 * x1 * y2 - 1.0 * x2 * y1) / d1 / d2; // } // if (abs(this->total-total)/max(this->total,total) > 1e-6) { // dbg("WHOOPS",this->total,total); // exit(0); // } // // dbg("CUR TOTAL",this->total, total); // return total * 0.5; } }; } /** * Description: Use in place of \texttt{complex}. * Source: https://codeforces.cc/blog/entry/22175, KACTL * Verification: various */ using T = R; // or ll const T EPS = 1e-9; // adjust as needed using P = pair; using vP = V

; using Line = pair; int sgn(T a) { return (a>EPS)-(a<-EPS); } T sq(T a) { return a*a; } bool close(const P& a, const P& b) { return sgn(a.f-b.f) == 0 && sgn(a.s-b.s) == 0; } T norm(const P& p) { return sq(p.f)+sq(p.s); } // T abs(const P& p) { return sqrt(norm(p)); } // T arg(const P& p) { return atan2(p.s,p.f); } P conj(const P& p) { return P(p.f,-p.s); } P perp(const P& p) { return P(-p.s,p.f); } // P dir(T ang) { return P(cos(ang),sin(ang)); } P operator-(const P& l) { return P(-l.f,-l.s); } P operator+(const P& l, const P& r) { return P(l.f+r.f,l.s+r.s); } P operator-(const P& l, const P& r) { return P(l.f-r.f,l.s-r.s); } P operator*(const P& l, const T& r) { return P(l.f*r,l.s*r); } P operator*(const T& l, const P& r) { return r*l; } P operator/(const P& l, const T& r) { return P(l.f/r,l.s/r); } P operator*(const P& l, const P& r) { return P(l.f*r.f-l.s*r.s,l.s*r.f+l.f*r.s); } P operator/(const P& l, const P& r) { return l*conj(r)/norm(r); } P& operator+=(P& l, const P& r) { return l = l+r; } P& operator-=(P& l, const P& r) { return l = l-r; } P& operator*=(P& l, const T& r) { return l = l*r; } P& operator/=(P& l, const T& r) { return l = l/r; } P& operator*=(P& l, const P& r) { return l = l*r; } P& operator/=(P& l, const P& r) { return l = l/r; } // P unit(const P& p) { return p/abs(p); } T dot(const P& a, const P& b) { return a.f*b.f+a.s*b.s; } T dot(const P& p, const P& a, const P& b) { return dot(a-p,b-p); } T cross(const P& a, const P& b) { return a.f*b.s-a.s*b.f; } T cross(const P& p, const P& a, const P& b) { return cross(a-p,b-p); } P reflect(const P& p, const Line& l) { P a = l.f, d = l.s-l.f; return a+conj((p-a)/d)*d; } P foot(const P& p, const Line& l) { return (p+reflect(p,l))/(T)2; } bool onSeg(const P& p, const Line& l) { return sgn(cross(l.f,l.s,p)) == 0 && sgn(dot(p,l.f,l.s)) <= 0; } int main() { ios::sync_with_stdio(0); cin.tie(0); ints(N,M); // rep(10000) { // Retro::HalfplaneSet HS; // rep(10) { // P a{rng()%1000000,rng()%1000000}; // P b{rng()%1000000,rng()%1000000}; // HS.Cut(Retro::LineFromPoints(a.f,a.s,b.f,b.s)); // cout << HS.Area() << "\n"; // } // // dbg("WUT"); // } // dbg("OK"); // exit(0); // assert(N == 4 && M == 2); dbg("??"); vP v(N); re(v); Retro::HalfplaneSet HS; F0R(i,N) { int j = (i+1)%N; HS.Cut(Retro::LineFromPoints(v[j].f, v[j].s, v[i].f, v[i].s)); dbg("CUTTING"); } R cur_area = HS.Area(); dbg((db)cur_area); // dbg("HA",cur_area); rep(M) { // if(_%10000 == 0) dbg("WHOOPS",_); P a, b; re(a,b); // dbg("GOT"); // auto HS_copy = HS; // HS.Cut(Retro::LineFromPoints(a.f,a.s,b.f,b.s)); // dbg(sz(HS)); auto [x,y,z] = HS.get_vertex(); P p{x/z,y/z}; // dbg((db)p.f,(db)p.s); if (cross(a,b,p) > 0) swap(a,b); // dbg("OH",_); Retro::deleted.clear(); auto wut = Retro::LineFromPoints(a.f,a.s,b.f,b.s); HS.Cut(wut); // dbg(a,b,p,HS.Area()); // assert(HS.Area() > 0); if (2*HS.Area() < cur_area) { Retro::HalfplaneSet new_HS; each(t,HS) if (!(t == wut)) { new_HS.Cut(t); } each(t,Retro::deleted) new_HS.Cut(t); new_HS.Cut(Retro::LineFromPoints(b.f,b.s,a.f,a.s)); swap(HS, new_HS); } else { // dbg("OK"); } cur_area = HS.Area(); } dbg_time(); // assert(abs(cur_area-21) < 1e-9); cout << fixed << setprecision(9) << (db)cur_area << "\n"; // ifstream fin("camera.in"); // ofstream fout("camera.out"); // int n; fin >> n; // vector x(n), y(n); // for (int i = 0; i < n; ++i) // fin >> x[i] >> y[i]; /* cout << "Polygon("; for (int i = 0; i < n; ++i) { if (i != 0) cout << ","; cout << "(" << x[i] << "," << y[i] << ")"; } cout << ")" << endl; */ // db ans = 0; // for (int rev = 0; rev < 2; ++rev) { // HalfplaneSet HS; // for (int j = n - 1, i = 0; i < n; j = i++) { // HS.Cut(LineFromPoints(x[j], y[j], x[i], y[i])); // //HS.Dump(); // } // if (HS.size()) { // cerr << "FINAL\n"; // for (auto x : HS) cerr << x << "\n"; // } // ans = max(ans, HS.Area()); // reverse(x.begin(), x.end()); // reverse(y.begin(), y.end()); // } // fout << fixed << setprecision(2) << ans << endl; // return 0; } Coldstart: All you needed to do was modify one of huikang's solutions to last year's Quora challenge. :) Coldstart Code#!/usr/bin/env python # coding: utf-8 # In[3]: import sys import numpy as np import lightgbm as lgb # In[1]: DEBUG = False # In[2]: if DEBUG: with open("example_input.txt", "r") as f: lines = f.readlines() else: lines = sys.stdin.readlines() # In[14]: k,t,n,m,u = map(int,lines[0].split()) train_lines = lines[1:1+2*n] train_data = [[0]*u for _ in range(n)] targets = [] for i in range(n): for critic in train_lines[i].split(): label, val = map(int,critic.split(":")) train_data[i][label] = 2*val-1 targets.append(int(train_lines[n+i])) # In[13]: k,t,n,m,u # In[6]: test_lines = lines[1+2*n:1+2*n+m] test_data = [] for line in test_lines: lst = [list(map(int,x.split(":"))) for x in line.split()] features = [0]*u for label, val in lst: features[label] = 2*val-1 test_data.append(features) # In[7]: import pandas as pd # In[17]: train_data_p = train_data test_data_p = test_data target_train = np.array(targets) df_train = pd.DataFrame(train_data_p) df_test = pd.DataFrame(test_data_p) # In[18]: df_train.shape # In[12]: target_train.shape # In[20]: eval_set = np.array([True if i < len(df_train)*0.2 else False for i in range(len(df_train))]) lgb_train = lgb.Dataset(df_train[~eval_set], target_train[~eval_set]) lgb_eval = lgb.Dataset(df_train[eval_set], target_train[eval_set], reference=lgb_train) lgb_all = lgb.Dataset(df_train, target_train) # In[22]: params = { 'objective': 'regression', 'verbose': -1 if not DEBUG else 0, } gbm = lgb.train(params, lgb_train, valid_sets=lgb_eval, verbose_eval=DEBUG, early_stopping_rounds=5) # In[23]: res = gbm.predict(df_test, num_iteration=gbm.best_iteration) if not DEBUG: print("\n".join(str(int(x)) for x in res)) else: print(t,res) # In[ ]: 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 ...

 » 3 months ago, # |   0 How to solve C?
•  » » 3 months ago, # ^ |   +32 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.
•  » » » 3 months ago, # ^ |   +10 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.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 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 LibraryThere 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. Code#include using namespace atcoder; void solve(){ int N; cin >> N; string str; cin >> str; vi ans(N, 0); vector> pairs = {{'A', 'T'}, {'T', 'A'}, {'G', 'C'}, {'C', 'G'}}; for(pair p: pairs){ vi odd(N, 0), eve(N, 0); for(int i = 0; i < N; i++){ if(str[i] == p.first && i%2 == 1) odd[i/2]++; if(str[i] == p.second && i%2 == 0) eve[i/2]++; } vi c = convolution(odd, eve); for(int i = 0; i < N; i++) ans[i] += c[i]; } int index = max_element(all(ans)) - ans.begin(); cout << index+1 << " " << ans[index] << endl; } 
 » 3 months ago, # |   0 Where can we find the full standing of the contest?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0
•  » » » 3 months ago, # ^ |   0 Yes I know, I need the full standing not just the top 150
•  » » » » 3 months ago, # ^ |   +6 The reply here says: We may release the ranking when we finish vetting the solutions.
•  » » » » » 3 months ago, # ^ |   0 Thanks
 » 3 months ago, # |   0 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
•  » » 3 months ago, # ^ |   +7 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.
•  » » » 3 months ago, # ^ |   0 ancestor i mean any node up in the tree (parents of parents .... etc)
•  » » 3 months ago, # ^ |   0 distance = distance from ancestor?
•  » » » 3 months ago, # ^ |   +3 yes
•  » » 3 months ago, # ^ |   -10 It should be true, maybe overflow?
 » 3 months ago, # |   +42 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)
 » 3 months ago, # |   0 What was the solution for DNA?I see a lot of people solved it, but I still can't figure out a linear solution
•  » » 3 months ago, # ^ | ← Rev. 3 →   +17 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)$.
 » 3 months ago, # |   +2 Not even able to solve the first problem, the challenge is ended, can u share ur code here. (i mean the IP BLOCKs}
•  » » 3 months ago, # ^ |   +46 import ipaddress n = int(input()) lol = [] for i in range(n): lol.append(ipaddress.ip_network(input())) result = ipaddress.collapse_addresses(lol) for x in result: print(x) 
•  » » » 3 months ago, # ^ |   0 I have seen this before just forgot to say thanks, now here to say thanks. Thanks mate!
 » 3 months ago, # |   +35 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.
 » 3 months ago, # |   0 Have people received invitations for interviews or similar?