Quora Programming Challenge 2022

3 года назад, # |

+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!

→ Ответить

tiasmondal

3 года назад, # ^ |

← Rev. 2 →

+12

On what basis are participants divided into div 1 and div 2? I did not find any such preference during registration.

→ Ответить

3 года назад, # ^ |

+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.

→ Ответить

cmplx-xyttmt

3 года назад, # |

Is there somewhere we can submit solutions to last year's problems?

→ Ответить

3 года назад, # ^ |

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.

→ Ответить

cmplx-xyttmt

3 года назад, # ^ |

Ok, thanks.

→ Ответить

grekiki

3 года назад, # |

Why are people from balkans not allowed to compete?

→ Ответить

3 года назад, # |

+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 programming-challenge@quora.com.

→ Ответить

3 года назад, # |

+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!

→ Ответить

VLamarca

3 года назад, # ^ |

Should we have received the registration email already?

→ Ответить

3 года назад, # ^ |

You asked in a perfect time, just around the announcement: https://qr.ae/pGExeF

(and for now yes, ofc)

→ Ответить

Blinding_Lights

3 года назад, # |

What are the level of problems according to codeforces rating?

→ Ответить

3 года назад, # ^ |

Hard to tell, there are easy to hard problems, as well as ML problems integrated into challenge

→ Ответить

CheeseBoi

3 года назад, # |

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 года назад, # ^ |

Details are in here: https://qr.ae/pGExeF

→ Ответить

komolakanto

3 года назад, # |

Thank you so much for the amazing problems. Can we get something like an editorial after it ends?

→ Ответить

TripleM5da

3 года назад, # |

+23

I CAME TO WHINE

HOW THE FUCK DO YOU WRITE DCHT WITH ROLLBACK?

→ Ответить

3 года назад, # ^ |

← Rev. 2 →

+14

Test are weak, my solution with copying cht for every children got 100 lol

→ Ответить

mraron

3 года назад, # ^ |

← Rev. 2 →

+14

You can use HLD technique and have $$$O(n \log^2 n)$$$ solution.

→ Ответить

3 года назад, # ^ |

I suppose that we need keep cht for every path?

→ Ответить

mraron

3 года назад, # ^ |

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.

→ Ответить

Bedge

3 года назад, # ^ |

← Rev. 2 →

You can use heavy light decomposition, maintaining O(log n) dynamic converx hull for chains from current node to root.

→ Ответить

TripleM5da

3 года назад, # ^ |

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.

→ Ответить

Svlad_Cjelli

3 года назад, # ^ |

I tried persistent Li Chao tree but it ran out of memory. I wonder if it's possible to get it within bounds...

→ Ответить

3 года назад, # ^ |

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.

→ Ответить

Svlad_Cjelli

3 года назад, # ^ |

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 года назад, # ^ |

No, I changed everything to int64_t, and also changed the maximum from 1e9 to 4e18.

→ Ответить

Fortin

3 года назад, # ^ |

I did it. I created static array with 7'500'500 nodes instead of pointers.

→ Ответить

TripleM5da

3 года назад, # ^ |

I would get literally sick if I tried doing something like that :(

→ Ответить

3 года назад, # ^ |

+15

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

→ Ответить

taran_1407

3 года назад, # ^ |

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).

→ Ответить

Vercingetorix

3 года назад, # ^ |

← 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.

→ Ответить

LastDance

3 года назад, # ^ |

← Rev. 2 →

I simply saved the changed values on the Li Chao Tree and then rollback. The complexity is O(nlogn)

→ Ответить

3 года назад, # |

+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.

→ Ответить

ALuca_Rd

3 года назад, # |

← Rev. 2 →

How to solve Xuora?

→ Ответить

BaaaaaaaaaaaaaaarkingDog

3 года назад, # ^ |

+14

Case work (n = 4k, n = 4k+1, n = 4k+2, n = 4k+3)

→ Ответить

ALuca_Rd

3 года назад, # ^ |

Can you please explain, how will you find the (m — n) numbers.

→ Ответить

m_vid

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.

→ Ответить

Mindjolt

3 года назад, # ^ |

← Rev. 4 →

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$$$.

→ Ответить

xiaowuc1

3 года назад, # |

+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

→ Ответить

Thallium54

3 года назад, # ^ |

← Rev. 2 →

My code passed the Google one but failed the Quora one :( can you share your code?

→ Ответить

https://ideone.com/HuFtnH

3 года назад, # |

Why 96 for problem IP?

→ Ответить

Ioana

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.

→ Ответить

aditi062519

3 года назад, # ^ |

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?

→ Ответить

aadarsh_aadi

3 года назад, # ^ |

can u share the code please

→ Ответить

smax

3 года назад, # ^ |

→ Ответить

ecnerwala

3 года назад, # ^ |

+32

One possible issue is that (1 << 32) doesn't work, you need to use (1LL << 32).

→ Ответить

Temotoloraia

3 года назад, # ^ |

I had 56 in problem IP and have no idea why. Did anyone experience a similar thing?

→ Ответить

leafvillageninja

3 года назад, # |

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?

→ Ответить

Benq

3 года назад, # |

+11

How to solve "subtracting?"

→ Ответить

3 года назад, # ^ |

+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.

→ Ответить

tourist

3 года назад, # ^ |

+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 <person; upvoted> in common with the query, then taking some kind of an average.)

→ Ответить

Benq

3 года назад, # ^ |

← Rev. 8 →

+28

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 ...

Cake Code

...

#include <bits/stdc++.h>
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<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;
#define mp make_pair
#define f first
#define s second

#define tcT template<class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;

// 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<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }
tcT> int upb(V<T>& 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<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;

// 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<<x; }
constexpr int msk2(int x) { return p2(x)-1; }

ll cdiv(ll a, ll b) { return a/b+((a^b)>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<T>& 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<T, void_t<decltype(begin(declval<T>())),
                                    decltype(end(declval<T>()))
                                   >
                         > : true_type {};
  tcT> constexpr bool is_iterable_v = is_iterable<T>::value;

  //////////// is_readable
  tcT, class = void> struct is_readable : false_type {};
  tcT> struct is_readable<T,
          typename std::enable_if_t<
              is_same_v<decltype(cin >> declval<T&>()), istream&>
          >
      > : true_type {};
  tcT> constexpr bool is_readable_v = is_readable<T>::value;

  //////////// is_printable
  // // https://nafe.es/posts/2020-02-29-is-printable/
  tcT, class = void> struct is_printable : false_type {};
  tcT> struct is_printable<T,
          typename std::enable_if_t<
              is_same_v<decltype(cout << declval<T>()), ostream&>
          >
      > : true_type {};
  tcT> constexpr bool is_printable_v = is_printable<T>::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<T> && is_iterable_v<T>;
  tcTUU> void re(T& t, U&... u);
  tcTU> void re(pair<T,U>& p); // pairs

  // re: read
  tcT> typename enable_if<is_readable_v<T>,void>::type re(T& x) { cin >> x; } // default
  tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; } // complex
  tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i); // ex. vectors, arrays
  tcTU> void re(pair<T,U>& p) { 
    str x,y; re(x,y);
    p.f = stold(x);
    p.s = stold(y);
     }
  tcT> typename enable_if<needs_input_v<T>,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>& t, U&... u);
  template<class...U> void rv(size_t, size_t N2, U&... u);
  tcTUU> void rv(size_t N, V<T>& t, U&... u) {
    t.rsz(N); re(t);
    rv(N,u...); }
  template<class...U> 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<T> && is_iterable_v<T>;

  // ts: string representation to print
  tcT> typename enable_if<is_printable_v<T>,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<bool> v) { return bit_vec(v); }
  template<size_t SZ> str ts(bitset<SZ> b) { return bit_vec(b); } // bit vector
  tcTU> str ts(pair<T,U> p); // pairs
  tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v); // vectors, arrays
  tcTU> str ts(pair<T,U> p) { return "("+ts(p.f)+", "+ts(p.s)+")"; }
  tcT> typename enable_if<is_iterable_v<T>,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<needs_output_v<T>,str>::type ts(T v) {
    return "{"+ts_sep(v,", ")+"}"; }

  // for nested DS
  template<int, class T> typename enable_if<!needs_output_v<T>,vs>::type 
    ts_lev(const T& v) { return {ts(v)}; }
  template<int lev, class T> typename enable_if<needs_output_v<T>,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<lev-1>(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<class T> void pr_sep(ostream& os, str, const T& t) { os << ts(t); }
  template<class T, class... U> 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<class ...T> void pr(const T&... t) { pr_sep(cout,"",t...); } 
  // print w/ spaces, end with newline
  void ps() { cout << "\n"; }
  template<class ...T> void ps(const T&... t) { pr_sep(cout," ",t...); ps(); } 
  // debug to cerr
  template<class ...T> void dbg_out(const T&... t) {
    pr_sep(cerr," | ",t...); cerr << endl; }
  void loc_info(int line, str names) {
    cerr << "Line(" << line << ") -> [" << names << "]: "; }
  template<int lev, class T> void dbgl_out(const T& t) {
    cerr << "\n\n" << ts_sep(ts_lev<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<lev>(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 <bits/stdc++.h>
 
// 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<T4, T4, T2> 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<Line> deleted;
 
struct HalfplaneSet : multiset<Line> {
  __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<T4, T4, T2> get_vertex() {
    return LineIntersection(*begin(), *next(begin()));
  }
  void add_contrib(multiset<Line>::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<T>}.
 * Source: http://mirror.codeforces.com/blog/entry/22175, KACTL
 * Verification: various
 */

using T = R; // or ll
const T EPS = 1e-9; // adjust as needed
using P = pair<T,T>; using vP = V<P>; using Line = pair<P,P>;
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<T> 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 ...

→ Ответить

denniskim

3 года назад, # |

How to solve C?

→ Ответить

Mindjolt

3 года назад, # ^ |

+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.

→ Ответить

Eryx

3 года назад, # ^ |

+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.

→ Ответить

Dragonado

3 года назад, # ^ |

← Rev. 2 →

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.

Code

#include <atcoder/convolution>
using namespace atcoder;

void solve(){
	int N;
	cin >> N;

	string str; cin >> str;

	vi ans(N, 0);

	vector<pair<char, char>> pairs = {{'A', 'T'}, {'T', 'A'}, {'G', 'C'}, {'C', 'G'}};

	for(pair<char, char> 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 года назад, # |

Where can we find the full standing of the contest?

→ Ответить

Rajat101

3 года назад, # ^ |

← Rev. 2 →

Top 150

→ Ответить

3 года назад, # ^ |

Yes I know, I need the full standing not just the top 150

→ Ответить

llc5pg

3 года назад, # ^ |

The reply here says: We may release the ranking when we finish vetting the solutions.

→ Ответить

3 года назад, # ^ |

Thanks

→ Ответить

Pepe.Chess

3 года назад, # |

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

→ Ответить

DivakarSingh

3 года назад, # ^ |

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.

→ Ответить

Pepe.Chess

3 года назад, # ^ |

ancestor i mean any node up in the tree (parents of parents .... etc)

→ Ответить

komolakanto

3 года назад, # ^ |

distance = distance from ancestor?

→ Ответить

Pepe.Chess

3 года назад, # ^ |

yes

→ Ответить

3 года назад, # ^ |

-10

It should be true, maybe overflow?

→ Ответить

jonathanirvings

3 года назад, # |

+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)

→ Ответить

komolakanto

3 года назад, # |

What was the solution for DNA?

I see a lot of people solved it, but I still can't figure out a linear solution

→ Ответить