kostka's blog

By kostka, 4 months ago,

Round F starts in less than an hour! See you on the scoreboard!

http://goo.gle/KS-2022-F

• +64

 » 4 months ago, # |   0 Good luck everyone!
 » 4 months ago, # |   +24 Runtime Error on Test Set 1 of problem B when I would have passed Test Set 2, because N is bigger for Test Set 1. Damn.
 » 4 months ago, # | ← Rev. 3 →   0 Could have got 12 more points if I had 2 more minutes. Spoiler
 » 4 months ago, # |   +5 In D2, I used some algorithm for the first time I don't even know to get AC. The trick basically updates the sum of first $k$ people's cancelled meetings from an ordered set of $n$ people (sorted by count of cancelled meetings).Can anybody quote the algorithm? Or is it just a random one?
•  » » 4 months ago, # ^ |   0 Are you challenging us to guess what you did, or are you asking us whether what you did has a formal name?
•  » » » 4 months ago, # ^ |   0 Yeah, I am actually interested in the formal name for what I did. Apologies that I didn't quoted my submission. AC Code:////////////////////////////////////////////////////////////////// ///// // //// Credits: Rahul Verma (CC @vrintle, CF @BlindingKnight) /// /// Institution: Delhi Technological University (aka. DCE) //// // ///// ////////////////////////////////////////////////////////////////// #include #include #include using namespace std; using namespace chrono; using namespace __gnu_pbds; template using pbds = tree, rb_tree_tag, tree_order_statistics_node_update>; // find_by_order(K): Returns an iterator to the Kth largest element (counting from zero) // order_of_key (K): Returns the number of items that are strictly smaller than K /* ~ You don't know the power of the dark side! ~ ..-..,'".- BM\dF. jM@' !MMM.&^'jjjM#*... !*m.F. ..... -.'^-".^. ._'-".  "#.# .]MF. _. __-gg.. jMg. ...... '......._ j#M' jMf jg_jm..- .Mf_ ja " . ^" ,_ 4g."@!. ...,., ',3&^jCgf ._""'. . """!. .^^ ..... .""LTgJf. =/<., _@#MMQK##-@"^ .. .'QK_. .!$AGz MM&�$#yF. !-M. .gmMM@! ."q. ..K#MD ZM#ZM#$. q4M. ..__,,yg_. ^\. ..M0# A0NWM@. jggp. .,m* .#MMMMM#'.. ' ."M0 BMM$@" !MM#'.. -*' ."QMMMM#.. ..^$BMMM' .^@#.'' _ ,yy___"". . ' MMMP ... j. 1.L .""9*qwwwJ,. .. @@@. . ...P', .F' .'. .. 0T' .P. . F' :"~~- ._.e.,wyyw..,,.... yg. ' _g0M0g. .-'''^'Q$_ Mf .jMMMMML .-"0M# @. . ."MMMM@^ ."". f . -. ... . . ._ ... . . . .. .. -' ., .., ..,. . . ..*. . _ , .p_ .-,'jb. _ jgg, -'-+..--!.!!! !' .~. _0MM/.-.-/@. .yyygggMM M0gyy__________. ^0M' "MM^ ...". ^MMMMMM MMMMMMMMMMMMMM'. .. . */ #define F first #define S second #define db double #define ld long db #define M 1000000007 #define pb push_back #define ll long long #define lll __int128 #define vl vector #define vd vector #define vld vector #define vvl vector #define pl pair #define pd pair #define vpl vector #define vpd vector #define lld __float128 #define ull unsigned ll #define sz(a) ((ll) a.size()) #define PI 3.141592653589793238 #define all(v) v.begin(), v.end() #define each(seq) for(auto e: seq) #define inf numeric_limits::max() #define acc(a) accumulate(all(a), 0ll) #define shuff(a) random_shuffle(all(a)) #define F0(n, i) for(ll i = 0; i < n; i++) #define F1(n, i) for(ll i = 1; i <= n; i++) #define google cout << "Case #" << i << ": "; #define dbgpr(pr) cout << ' ' << #pr << " {" << pr.F << ',' << pr.S << "} " #define dbgprs(seq) cout << #seq << " <"; each(seq) { dbgpr(e); } cout << ">\n" #define dbgarr(seq) cout << #seq << " < "; each(seq) { cout << e << ' '; } cout << ">\n" #define dbgmtx(mat) cout << #mat << " {\n"; each(mat) { cout << ' '; dbgarr(e); } cout << "}\n" #define lrot(a, l, r, k) rotate(a.begin() + l, a.begin() + l + (k % (r - l + 1)), a.begin() + r + 1) #define rrot(a, l, r, k) rotate(a.begin() + l, a.begin() + r + 1 - (k % (r - l + 1)), a.begin() + r + 1) #define dbgmap(hash) cout << #hash << " { "; each(hash) { cout << e.first << ':' << e.second << ' '; } cout << "}\n" #define dbgtree(tree) cout << #tree << " {\n"; each(tree) { cout << e.first << ": "; dbgarr(e.second); } cout << "}\n" // Debug Template, copied from Mikel_Arteta_8 (https://codeforces.com/blog/entry/68809) void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template void __print(const pair &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef VRINTLE #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif // End of debugging template /* ostream& operator<<(ostream& o, const __int128& x) { if (x == numeric_limits<__int128>::min()) return o << "-170141183460469231731687303715884105728"; if (x < 0) return o << "-" << -x; if (x < 10) return o << (char)(x + '0'); return o << x / 10 << (char)(x % 10 + '0'); } */ ll sieve_size = 0, facto_size = 0; vector F(facto_size+1); vector state(sieve_size+1, 1); // exp() for (N^K)%M is only valid, when N%M != 0, else return 0 ll exp(ll n,ll k,ll m=M){ll r=1,a=n%m;do{r=k&1?r*a%m:r;a=a*a%m;}while(k/=2);return r;} ll imod(ll a,ll m=M){return exp(a,m-2,m)%m;} ll C(ll n,ll r,ll m=M){return r?(F[n]*imod(F[r],m)%m*imod(F[n-r],m)%m)%m:1;} void facto(ll n=facto_size,ll m=M){F[0]=1;F1(n,i)F[i]=(F[i-1]*i)%m;} void sieve(ll n=sieve_size){for(ll i=4;i<=n;i+=2)state[i]=0;for(ll i=3;i<=n;i+=2)for(ll j=i*i;j<=n;j+=i)state[j]=0;} // when floor(-1 / 4) = -1, use this one templateT fdivf(T a,T b){return a/b-((a^b)<0&&a%b);} void solve() { ll n, k, x, d, m; cin >> n >> k >> x >> d >> m; vl blk(n); vvl st(d + 1), en(d + 1); pbds obs; F0(n, i) { obs.insert({blk[i], i}); } while(m--) { ll i, l, r; cin >> i >> l >> r; i--; st[l].pb(i); en[r].pb(i); } ll sum = 0; function remove = [&](ll i) { ll v = blk[i]; ll j = obs.order_of_key({v, i}); if(j < k) { if(sz(obs) > k) { sum += obs.find_by_order(k)->F; } sum -= v; } obs.erase({v, i}); }; function update = [&](ll i, ll v) { remove(i); ll j = obs.order_of_key({v, i}); if(j < k) { if(sz(obs) >= k) { sum -= obs.find_by_order(k - 1)->F; } sum += v; } obs.insert({v, i}); blk[i] = v; }; ll ans = inf; for(ll h = 1; h <= x; h++) { each(st[h - 1]) { ll v = blk[e]; update(e, v + 1); } } ans = min(ans, sum); for(ll h = x + 1; h <= d; h++) { ll h0 = h - x; each(en[h0]) { ll v = blk[e]; update(e, v - 1); } each(st[h - 1]) { ll v = blk[e]; update(e, v + 1); } ans = min(ans, sum); } cout << ans; } int32_t main() { auto start = high_resolution_clock::now(); ios_base::sync_with_stdio(false); cin.tie(NULL); ll t = 1; cin >> t; F1(t, i) { google solve(); cout << '\n'; } auto stop = high_resolution_clock::now(); auto duration = duration_cast(stop - start); debug(duration.count(), " µs!"); return 0; } 
•  » » » » 4 months ago, # ^ |   0 Looks like you're using the kth order statistic feature of ordered set, a policy based data structure based on red-black trees.I'm not aware of a formal name for what you're doing here; just that you are using the features of the data structure.
 » 4 months ago, # |   +8 The second problem had a natural problem statement, however as obvious as it may seem to lot of readers, authors should specify enviroment variables such as the bottomost container indicates it is kept on surface of some body with gravity because the principle linked in editorial only works with certain conditions IIRC(bottom level is closer to the body exhibiting gravitation force on water, there is gravitational force). The problem also incentivisted people who have studied a little bit about fluid mechanics and seen this experiment.
•  » » 4 months ago, # ^ |   +23 When I read the statement I initally thought this was unclear too. One of the examples does clear up any ambiguity, but I agree that it should be in the statement.
 » 4 months ago, # |   +19 The constraints on B were evil. I just looked at test set 2 and got a Runtime error because of it.
 » 4 months ago, # |   +2 Problem C (Story of Seasons) Test Set 1 is very similar to this AtCoder problem: ABC137d
 » 4 weeks ago, # |   0 Can anybody help me figure out why I am getting a wrong answer on test 2 in Problem C !!The link for the submission is https://pastebin.com/x5hSZaPp.Please help !! Thanks in advance :)
•  » » 4 weeks ago, # ^ |   +4 I was getting TLE from the debug lines (I guess Google doesn't have ONLINE_JUDGE defined), and then there's a small mistake. Maybe this test case can help you find it? Spoiler1 100 2 1 1 1 1 10 99 1 (the solution) SpoilerLine 141: tot = /*tot + */(curr - next)*x; We can't store up times to plant the seeds so we should always assume tot` starts at 0.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +9 Thanks mixed_juice717 Sir for helping me once again :).Got my mistake.