ko_osaga's blog

By ko_osaga, history, 19 months ago, , WHERE IS IT?

Edit : Ok because of the delay we are unable to participate :/ cant, find, in, Comments (41)
 » Where is it???
•  » » where is it??
•  » » » You should check out this blog post:http://codeforces.com/blog/entry/58674
 » April Fools?
 » We are in Moscow but we can't find the link too...
 » There is an onsite contest with the same problems (Moscode). I guess there was some trouble in the onsite contest.
 » 19 months ago, # | ← Rev. 2 →   https://official.contest.yandex.ru/opencupXVIII/contest/7895/enter : "The virtual contest is in progress. You are not allowed to participate"
•  » » Hi. How do you find this link? I couldn't find it at opencup.ru :(
•  » » » I used for i in seq 7836 8000; do wget "https://official.contest.yandex.ru/opencupXVIII/contest/\$i/enter/"; done; in bash :/
 » According to snarknews, the contest will start one hour later, at 12:00 Moscow time.
 » » 19 months ago, # | ← Rev. 2 →   Do anybody want to join today in team ext64 with me and savinov ?
•  » » Sure, why not.
 » 19 months ago, # | ← Rev. 2 →   7 minutes and still no link ?UPD: this one
•  » »
 » Where is 2nd division link?
•  » »
•  » » » 19 months ago, # ^ | ← Rev. 3 →   "Service not available"
•  » » » » http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=10387What is this? Why it shows this link :D
•  » » » » » This is previous year contest
 » how to solve B,H, E?
•  » » B: For each added point, consider all the points within the square with length equals to the twice of current answer and centered at this point. Try all the possible triples. There won’t be too many points.H: dp[i][j]=min length of si - 1 when si=p[0..j]
•  » » H: dynamic programming: dp[i][k] — what is the minimal length of sk - 1 such that there exists sk of length exactly i (it also should be a prefix of p). How to invent that state: think of brute force, understand that we should know lengths of sk, sk - 1 in order to generate sk + 1, then swap answer with one of dimensions (here I swapped the answer with |sk - 1|).Now recalculation is simple: if you have sk with a specific length and you know |sk - 1|, then you know minimal possible length of tk + 1, and you also know its maximal length (it's minimal value of z-function and |sk|; if you forget about the latter, you get WA 12).
 » I?
•  » » 19 months ago, # ^ | ← Rev. 2 →   It can always be achieved with at most two operations [1, n], [1, n - 1].So just check if it's possible to achieve in one operation. Otherwise, construct with the two intervals.
•  » » » Can you explain how you do it in two operations?
•  » » » » You can deduce each element one by one.For example, to make the sequence 10 4 3 5 7, the two constructed sequence should be 7 2 1 2 7 and 3 2 2 3
•  » » » » » LOL. Thanks
 » D?
•  » » 19 months ago, # ^ | ← Rev. 3 →   If there are no boundaries at 0 and L, you take n functions yi(x) = ai ± x, and position of k-th dog at time t, is k-th sorted value of all yi(t).With boundaries answer is periodical over time with period 2L, so you should do . Also you should add mirrored about the border lines and find k-th value in the interval [0, L]To find k - th value you can use binary search over answer, so you need to count number of yi <  = checkValue, and that's possible to do with 2 binary searches over lines of same type.That's •  » » » It's also possible to find k-th element of two merged arrays in O(logN) with few binary searches, instead of O(log2N).
•  » » » k-th value of union of two sorted arrays A and B in O(logn):Find the smallest i : A[i] >= B[k-i-1]. Return max(A[i-1], B[k-i-1]).Proof. We want to take k smallest numbers = i numbers from A and k-i numbers from B. Then the k-th value is f(i) = max(A[i-1], B[k-i-1]). f(i) decreases until B[k-i-1]  ≤  A[i] (i  →  i+1 means "change B[k-i-1] to A[i]").
 » How to solve C?
 » What is the expected solution for F ? I solved it with a general graph isomorphism algorithm.
•  » » Smart bruteforce + random?
•  » » Here I give a seemingly rigorous solution:Suppose we can somehow identify vertices with value . The idea is that number of multiples for values in the range are distinct.Vertices not adjacent to have value of prime number larger than . Call this set of vertices S.Then we can assign prime numbers greater than to S by its degree. e.g.: have same degree as the unknown vertices with value p1, p2, then we can arbitrarily give p1, p2 to v1, v2. Since somehow we cannot distinguish these 2 vertices.Now we identify all vertices with prime value. Hence we know prime factors each vertex has by its adjacent prime-valued vertices.The next step is to identify vertices with power of prime value (pe). Simply group vertices with single prime factor and sort them by degree, the larger degree the smaller exponent.For any other vertices, we can find exponents of its prime factors.
•  » » We tried the same, but failed to beat the TL. Can you share your code, please?
•  » » » 19 months ago, # ^ | ← Rev. 2 →   Here is the code. The backtrack function (and maybe other parts of the code) may still have some bugs that do not happen in this case. Spoiler#include #define FOR(i,n) for(int i=0;i<(n);++i) #define FORU(i,j,k) for(int i=(j);i<=(k);++i) #define FORD(i,j,k) for(int i=(j);i>=(k);--i) #define X(a) get<0>(a) #define Y(a) get<1>(a) #define Z(a) get<2>(a) #define W(a) get<3>(a) #define all(x) begin(x),end(x) #define pb push_back #define mt make_tuple #define mp make_pair using namespace std; using vi = vector; using pii = pair; using vvi = vector; using vii = vector; using vvii = vector; //------------------------------------------------------------------------------ struct WLGIso { vvi G; int n; vi ghashes; int partitionSize = 0; vvi partition; vi color; vi hash; vi inQ; vi Q; vector>>>> history; WLGIso(vvi G1, vvi G2) { G = G1; G = G2; n = G1.size(); assert(n == (int)G2.size()); ghashes.resize(2*n); FOR(i,2*n) ghashes[i] = rand()*rand()+rand(); FOR(ix,2) { color[ix].resize(n); hash[ix].assign(n,0ll); } // Initialize the partition { unordered_map> dPartition; FOR(ix,2) FOR(i,n) dPartition[G[ix][i].size()][ix].pb(i); for(auto const& p : dPartition) { array const& v = p.second; assert(v.size() == v.size()); FOR(ix,2) { partition[ix].emplace_back(); for(int i : v[ix]) { partition[ix].back().pb(i); color[ix][i] = partitionSize; } } inQ.pb(1); Q.pb(partitionSize); partitionSize++; } } // Initialize the hashes FOR(ix,2) FOR(i,n) for(int j : G[ix][i]) { hash[ix][i] += ghashes[color[ix][j]]; } history.emplace_back(); X(history.back()) = partitionSize; } void push(int i) { if(partition[i].size() > 1 && !inQ[i]) { inQ[i]=1; Q.pb(i); } } void split(int i, vector> const& w){ Y(history.back()).emplace_back(i,array{{partition[i],partition[i]}}); FOR(ix,2) for(int j : partition[ix][i]) for(int k : G[ix][j]) { push(color[ix][k]); hash[ix][k] -= ghashes[i]; } bool first = 1; for(auto const& v : w) { int pi = first ? i : partitionSize; if(!first) { FOR(ix,2) partition[ix].emplace_back(); inQ.pb(0); partitionSize += 1; }else{ FOR(ix,2) partition[ix][pi].clear(); } first = 0; FOR(ix,2) for(int j : v[ix]) { partition[ix][pi].pb(j); color[ix][j] = pi; for(int k : G[ix][j]) { hash[ix][k] += ghashes[pi]; } } push(pi); } } bool refine(){ while(!Q.empty()) { int i = Q.back(); Q.pop_back(); inQ[i]=0; unordered_map > hPart; FOR(ix,2) for(int j : partition[ix][i]) { hPart[hash[ix][j]][ix].pb(j); } for(auto const& q : hPart) { auto const& v = q.second; if(v.size() != v.size()) return false; } if(hPart.size() == 1) continue; vector> w; for(auto const& q : hPart) w.pb(q.second); split(i,w); } return true; } void backtrack() { int oldSize = X(history.back()); vector>>& v = Y(history.back()); FOR(ix,2) while((int)partition[ix].size() > oldSize) { int pi = partition[ix].size() - 1; for(int i : partition[ix].back()) for(int j : G[ix][i]) { hash[ix][j] -= ghashes[pi]; } partition[ix].pop_back(); } while(!v.empty()) { int i = X(v.back()); array const& w = Y(v.back()); if(i> w(2); FOR(ix,2) w[ix] = partition[ix][i]; swap(w[j],w.back()); FOR(ix,2) { w[ix].pb(w[ix].back()); w[ix].pop_back(); } split(i, w); if(run(i)) return 1; backtrack(); } backtrack(); return 0; } }; int main(){ cin.tie(0); ios::sync_with_stdio(0); int n,m; cin>>n>>m; vvi G(n); FOR(i,m) { int u,v; cin>>u>>v; --u; --v; G[u].pb(v); G[v].pb(u); } int hm=0; vvi H(n); FORU(i,1,n) for(int k=2; k*i<=n; ++k) { hm++; H[i-1].pb(i*k-1); H[i*k-1].pb(i-1); } assert(m==hm); WLGIso w(G,H); bool ok = w.run(0); assert(ok); vi ans(n); FOR(i,n) { ans[w.partition[i]] = w.partition[i]+1; } FOR(i,n) { cout << ans[i] << ' '; } cout << endl; return 0; }
•  » » » » Thank you veru much!
 » How to solve A?
•  » » Concentrate on one player at a time, suppose the cards he ends up with are a1, ..., ak, with a1 being the best. Let bi be number of cards the previous player (the player who passes cards to the current player) has which are better than ai. Now process the cards of the current player from best to worst.Card i either initially belonged to some starting hand out of which the previous player just drafted a better card (bi options) or it was the first card drafted from the starting hand of the current player (1 option). Exactly i - 1 of these options have already been taken away (by previously processed (better) cards of the current player), so bi + 1 - (i - 1) options remain, resulting in a total of ways to choose where the cards for the current player came from.The only thing left is to make sure that the current player started with at least one card, so we need to subtract the number of ways in which we never choose the second type of option, which is . The final answer is the product of the number of ways for each player. All this can be implemented in .