### k790alex's blog

By k790alex, history, 16 months ago,

Hi,

The 2019 ICPC Mexico Finals starts in 30 minutes.

Let's discuss the problems after the contest.

There are some mirror contests starting 1h after the real one:

Streaming:

Good luck to all the teams.

UPDATE The contest has started.

UPDATE Live scoreboard: https://global.naquadah.com.br/boca/score/index.php (use this if the previous one doesn't work https://global.naquadah.com.br/boca/scoreglobal.php?h=AT2oE0HBeAg8eox30q5wZOdk8SY_bIZ-hGKuX9OTrY661HqiWgHRra4KBYyrxV6IDqZeTVr7yJ6EpBVje50BxzQBkGZoTKMNPwb3UZpD_G79M9PmveqUhUUrtO04BJUpMwqPvrz_7o-QWTc)

UPDATE Problems available:

Congrats to the winners!!!

UPDATE These are the teams going to the world finals, there were 4 extra spots:

- UH++,CUBA
- Limitless, CUBA (new)
- Norman is Hunting, MEXICO
- E3, MEXICO
- #define TriLCI(404.0) :v, MEXICO
- pu+os, MEXICO (new)
- Guerreros de RodriGOD, COSTA RICA
- InChaVoLa, ARGENTINA
- GG Dem, ARGENTINA
- #NuevaConstitución UChile1, CHILE
- Rating MiSeRable, PERU (new)
- descomUNAL, COLOMBIA
- La bomba de tenedores, VENEZUELA
- Time com T, BRASIL
- Campinas Grande, BRASIL
- Amigos do Beto, BRASIL
- Rock Lee do Pagode Namora D+, BRASIL
- Rábalabaxúrias, BRASIL
- Triple G, BRASIL (New)



UPDATE MarcosK uploaded the contest and the official standings to the gym: 2019-2020 ACM-ICPC Latin American Regional Programming Contest

• +128

 » 16 months ago, # |   0 Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).
 » 16 months ago, # |   0 Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).
 » 16 months ago, # |   0 Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).
 » 16 months ago, # |   0 Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).
 » 16 months ago, # |   0 Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).
 » 16 months ago, # |   0 Is there another way to solve K problem avoiding FFT?
•  » » 16 months ago, # ^ |   0 Sure, naive multiplication does the job pretty well here. Expected complexity in this problem is $O(n^2)$.
•  » » 16 months ago, # ^ |   0 We tried FFT with divide and conquer but the precision error is too big to handle up to 2^63 -1. In the end 10^4 for 0.1 seconds troll us :P
•  » » » 16 months ago, # ^ |   +5 Because of the 2^63-1 constraint, the real limit is actually $n \le 16$. So you can do multiplication as slowly as you want...
•  » » » » 16 months ago, # ^ |   0 :O i am dumb
•  » » » » 15 months ago, # ^ |   0 That's true O_O!I actually didn't notice that so I coded it with divide and conquer NTT and then used BigInt to reconstruct the answer, which took like 90 minutes to implement, I think it has to do with the fact that I was learning NTT last week, so I had the topic fresh and didn't try to come up with an alternative approach. Funny enough, when I saw 2^63 I thought why not 10^18 that way it fits without having to use BigInt heheWell at least I can say that I learnt it good since I managed to get it AC :)https://codeforces.com/gym/102428/submission/65614985
•  » » » » » 11 months ago, # ^ |   0 We are not allowed to see others' submissions. Could you share it in another way?
 » 16 months ago, # |   0 In problem E we have to create a List with all the positions of E from 0 to n+sThen we need to iterate the string if the position has an E, then we sum S to the ans if not we look for the closest E to this relative position and if its distance is less than S we add (s — distance from the closest E) to the answer.Code for preview: Code#include typedef long long int ll; typedef long double ld; #define pii pair #define pb push_back #define vi vector #define vii vector #define mp make_pair #define F first #define S second #define B begin() #define E end() #define INF 1e18 #define MOD 1e9 + 7 using namespace std; int main () { string b; cin>>b; int s; int n = b.length(); cin>>s; vi v; ll c1=0,c2=0; for(int i = 0; i < n; i++){ if(b[i]=='E') c1++; else c2++; } if(c1 == n){ cout<<(c1*s)<<"\n"; return 0; } else if(c2 == n){ cout<<"0\n"; return 0; } for(int i = 0; i < n+s-1; i++){ if(b[i%n]=='E') v.pb(i); } if(s == 1){ cout<<(v.size())<<"\n"; return 0; } ll ans = 0; for(int i = 0; i < n; i++){ if(b[i]=='E') ans+=s; else{ int k = lower_bound(v.B,v.E,i)-v.B; k = v[k]; if(abs(i-k)
 » 16 months ago, # |   0 Can someone please tell me why this solution for I is wrong? https://ideone.com/61vnoj
•  » » 16 months ago, # ^ |   +3 If a client i is sent an email k*(1e9 + 7) times, dp[i] is zero, but that client still needs to be counted towards the "number of emails after the improvements".
•  » » 16 months ago, # ^ |   +3 You should count separately the number of messages before the optimization and after the optimization because of the mod. Test case that breaks this solution was added one day before the competition.
 » 16 months ago, # |   0 How to solve G and F ?
•  » » 16 months ago, # ^ |   +5 Problem G could be easily solved with Suffix Automaton, you could build a Suffix Automaton of S in $O(n*log(n))$ and then for each query start at the root of the automaton and do the following: If there is a transition from the current node with the current letter of the query, move through it. Otherwise, if you are not on the root, go to the root and add $1$ to the answer, if you are on the root, then the answer is $-1$. For Problem F, you have to solve the problem recursively. Consider you'll be putting floors from bottom to top, if you have $s$ remaining blocks and the last floor you put had $n$ blocks then the number of ways to put the rest is: $dp(s, n) = dp(s, n-1) + \sum_{x=1}^{min(s,n)} dp(s-x, x)$This is, if the next floor doesn't start in the first block of the last floor, then there are $dp(s, n-1)$ ways to put the rest, otherwise, you can pick any valid size for the next floor and you know where it will be.This is $O(n^3)$ if implemented naively, but it can be optimized to run in $O(n^2)$ by pre-calculating some sums.
•  » » » 15 months ago, # ^ | ← Rev. 3 →   +5 About problem F, I'm not sure if I'm understanding correctly. Shouldn't the $dp(s,n)$ recurrence be: $dp(s,n) = \sum_{x=1}^{\min(s,n)} (n-x+1) \times dp(s-x,x)$Because $x$ basically means how wide you want the current floor to be, therefore you have $n-x+1$ positions to place a floor of width $x$ on top of a previous floor of width $n$ without going beyond its margins.About precomputing some sums to reduce the complexity to $O(n^2)$, can you explain that part more in detail?
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   +5 both are correct, for CrazyDiamond's formula you can think of:the next floor will (A) start in the leftmost position of the previous floor or (B) it won't start there.for (A) you have to choose where it ends: $\sum_{x=1}^{min(s,n)}dp(s-x,x)$, and for (B) you can reduce it to the same problem but forgetting about the first position of the previous floor: $dp(s, n-1)$This formula is a bit nicer because it needs an easier precomputation, although your formula can also be optimized to run in $O(n^2)$ If you keep thinking, with similar reasoning, you can get to martins formula (comment below) which is even nicer (very simple dp with no precomputation)My recommendation to understand the optimization is to look at the memo matrix and what the sum we need to compute ($\sum_{x=1}^{min(s,n)}dp(s-x,x)$) looks like in the matrix. You can build prefix sums over that matrix (in this case, over some diagonals of the matrix) such that you can compute $\sum_{x=1}^{min(s,n)}dp(s-x,x)$ in $O(1)$
•  » » 15 months ago, # ^ | ← Rev. 2 →   +13 Another way to solve F is the following. First, you can ignore the first level of blocks. Let $DP(s,b)$ be the number of ways to put the remaining blocks. To calculate this you look at three cases: The first level of blocks is full The leftmost stack is empty The rightmost stack is empty You can calculate the first case by simply ignoring $s$ blocks. The second and third case are analogous, and you can calculate them by ignoring one stack. However, the cases eventually overlap, since the scenario where both the leftmost stack and the rightmost stack are empty can be reached from both cases. This can be solved by subtracting the value for the overlap. This is the formula:$DP(s,b) = DP(s, b-s) + 2 \cdot DP(s-1, b) - DP(s-2, b)$
•  » » » 15 months ago, # ^ |   0 That's incredible hahaha literally blew my mind... During contest my team and I spent the last hour trying to solve this problem and now I feel stupid hahaha
•  » » » 12 months ago, # ^ |   0 This is awesome.
•  » » » 11 months ago, # ^ |   0 Is this $O(N)$ complexity?
•  » » » 5 weeks ago, # ^ |   0 This is amazing, dude. So clean and simple
•  » » 15 months ago, # ^ | ← Rev. 2 →   +5 For problem G another option is to use suffix array. Build a suffix array of the main string in $O(n \cdot log(n))$, and then for each query iterate over its characters and each time do 2 binary searches (a lower bound and upper bound) so that each time you keep narrowing the range of suffixes that still match with the query. To make it clearer, you start with the first character of the query, and with 2 binary searches you find the range of all suffixes having the first character as prefix, then you do 2 additional binary searches and find the range of all suffixes having the first 2 characters as prefix (inside the previous range) and so on. If the range becomes empty, increase your counter by 1 and start all over again from where you left off. In case you can't match even 1 character, then print -1.
•  » » 2 weeks ago, # ^ |   0 Have some corner case for G?, It fails in test12 :/
•  » » » 2 weeks ago, # ^ |   0 You can download the test cases (input and output) from: http://maratona.sbc.org.br/hist/2019/index.htmlThe tests cases at the gym are the same as the ones used in the original contest.
•  » » » » 2 weeks ago, # ^ |   0 OMG a lot of thanks
 » 16 months ago, # |   0 In general I think it was good that problem-setter name was removed from each problem (I used to check the name of the problem-setter to try to guess complexity). Although, after reading problem C I feel bad the authors are not getting any recognition, very creative statement indeed.
•  » » 16 months ago, # ^ |   +16 - A {Algorithm Teaching} {Marcelo Fornet, Cuba} - B {Build the Perfect House} {Marcelo Fornet, Cuba} - C {Cut Inequality Down} {Mariano Crosetti, Argentina} - D {Dazzling Stars} {Mário da Silva, Brasil} - E {Eggfruit Cake} {Moroni Silverio, México} - F {Fabricating Sculptures} {André Amaral de Sousa, Brasil} - G {Gluing Pictures} {Nicolás Álvarez, Argentina} - H {Hold or Continue?} {Pablo Zimmermann, Argentina} - I {Improve SPAM} {Paulo Cezar Pereira Costa, Brasil} - J {Jumping Grasshopper} {André Amaral de Sousa, Brasil} - K {Know your Aliens} {Mário da Silva, Brasil} - L {Leverage MDT} {Carlos Mendoza, Peru} - M {Mountain Ranges} {Vinicius Santos, Brasil} 
•  » » » 15 months ago, # ^ | ← Rev. 3 →   0 Thanks for the problems. They were pretty brutal.
•  » » » » 15 months ago, # ^ |   0 In case you are referring to the first two problems here is an outline of the solution:Problem A: build the graph where every possible set is a node, and there is a directed between A and B if B contains exactly one element more than A. This is of course a DAG and we need to find maximal anti chain here. Applying Dilworth to this graph is enough to find the solution. Notice that number of edges in the transitive closure is at most $N \cdot 3^K$.Problem B: Every point can be rotated 90 degree several times without affecting the answer. Do this until every point is in the first quadrant. Let's find where is the corner of the optimal square in the first quadrant. Binary search over the length of the diagonal (it is proportional to the perimeter) and try to find a rotation of the square such that it doesn't contain any point. Each point will give you a possible interval to rotate the square. Find if the intersection of all intervals is not empty. The time complexity was $O(\log(-PREC) \cdot \log n \cdot n)$.There was also a beautiful solution for this problem with expected complexity $O(n)$, similar to the algorithm that find minimal enclosing circle. Random shuffle points at the beginning, and try to find a valid square for all prefix. Suppose you have a maximal square for first $x$ points, if point $x+1$ is outside this square, no action needs to be taken, otherwise, recompute the square, but letting this point belonging to one side of the square. This solution is a little bit trickier to implement, since a pair of point can define two possible maximal (not both maximum) squares.
•  » » » » » 15 months ago, # ^ |   +16 $N \times 3^K$ is still a heck of a lot. As the problem stands, you're expecting contestants to submit an $O(E\sqrt{V})$ algorithm with $E \approx 6\times10^6$, which is a gamble I expect most people to not be willing to make (the scoreboard agrees with me). Did you ever consider decreasing limits for this problem?
•  » » » » » » 15 months ago, # ^ |   +15 Yes sure, but in practice the solution works extremely fast since the graph is not arbitrary. I stress my solution against tons of random (and not some random) distributions and it turns out that number of bfs required by Dinic was $O(log V)$ opposed to $O(\sqrt{V})$ (empirical result). Moreover there was a very nice property that we didn't proved, it looks like transitive closure was not necessary to find minimum chain decomposition. Reference solution used transitive closure and run in less than a second.I agree with you that it still sounds like this solution is a gamble, and maybe this problem doesn't fit quite well in this format of contest, but I still believe it is a nice problem. For the purpose of the problem we could decrease the limits, but it turned out hard to kill some greedies with small restriction, since we don't have so much control on the graph.
•  » » » » » » » 15 months ago, # ^ |   +8 A complement to your empirical findings: https://link.springer.com/article/10.1007%2Fs00224-005-1254-y
•  » » » » » » 15 months ago, # ^ |   +8 Is it really a gamble though? Worst case analysis here seems too pessimistic and despite being a valuable tool is no silver bullet.To reach N*2^K vertices and N*3^K edges there's no intersection between algorithms known by teachers so actually we have N independent graphs with 2^K vertices and 3^K edges each (in practice we are running N bipartite matchings on really small graphs, that translates into something close to 10^7 operations, given a proper hopcroft-karp implementation I'd be more concerned about the cost of constructing the graph than with calculating that).On top of that these graphs are quite sparse and for those on average hopcroft-karp runs in near linear time.
•  » » » » » » » 15 months ago, # ^ |   +8 This is an ICPC contest; your code has to pass all test cases so average case analysis is meaningless.marX made a valid argument that the worst case for these specific kinds of graphs is fast, and I have no reason to believe this is not true. But the only proof of this is empirical findings, which make it a gamble from a competition standpoint in which implementing flow and checking that it runs fast consumes precious time.
•  » » » » » » » » 15 months ago, # ^ |   0 The near linear average analysis part is mostly an addendum, what I really wanted to point is that just replacing E = 6e6 in O(E sqrt(V)) is too pessimistic as we don’t really calculate bipartite matching for such big graphs.But yeah, I guess that not calculating the actual size of the biggest graph we can have and just extrapolating from this case where there are N independent graphs might be also seen as a gamble.
•  » » » » » » 15 months ago, # ^ | ← Rev. 2 →   +23 We agree with you ffao. We are very sad that this problem has not been solved.We started working late this year and nobody really helped marX until the last week. I have to admit that I misread the problem and understood that there were only 10 algorithms in total. I only realized that 3 days before the competition.By the way, I think that most wrong-solutions were WA, not TLE.
•  » » » » » 15 months ago, # ^ |   0 Could you elaborate a bit more on how to rotate the square for a given diagonal length for B's solution? Or maybe just send some resources so I can figure it out?
•  » » » » » 15 months ago, # ^ |   0 In A there is no need to build edges between every pair of sets X and Y, where Y is a subset of X. You can build an edge only when (size of X = size of Y + 1), so there will be N*(2^K)*K/2 edges, for N=100 and K=10 it is about 5*10^5 edges.
•  » » » » » » 15 months ago, # ^ |   0 We were aware of this, but... Do you know why it works?
•  » » » » » » » 15 months ago, # ^ |   0 well, it seems obvious that there will always be a path from X to Y if Y is a subset of X
•  » » » » » » » » 15 months ago, # ^ |   0 That's not enough, you usually need to find the transitive closure of the graph to find minimum chain decomposition.Take for example this directed graph: 5(nodes) 4(edges) 1 3 2 3 3 4 3 5 The minimum chain decomposition is 2 (1,3,5; 2,4), but to find it you need to find the transitive closure. The underlying graph structure allows in this particular problem not to find the transitive closure. This tells that the optimal chain decomposition can be built using only edges between sets that differ in exactly one element. But I hadn't proof that yet.
•  » » » » » » » » » 15 months ago, # ^ |   0 You're right, I'm dumb.
•  » » » » » » » » » 15 months ago, # ^ | ← Rev. 2 →   0 I also submitted the solution without the transitive closure and it worked, is it weak testcases or is there proper reasoning why it would work? marX
•  » » » » » » » » » 15 months ago, # ^ |   +8 vivace_jr We noticed before the competition that this strategy passed all testcases. I personally invested some time trying to break such solution, but unfortunately, didn't find any counter-example, also neither proved that it was legit.So regarding your question about weak testcases: It depends if it is actually correct solution or not, which I don't know yet. My guess is that it is ok. At least testcases were not deliberately weak in that sense.This wasn't a big deal since model solution used transitive closure.
•  » » » » » » » 13 months ago, # ^ |   +10 There is a method to find maximum antichain (as well as minimum chain decomposition) without transitive closure. In this problem, the partial order is the same as what danya090699 said and we construct a special network $G=(V,E)$. In this network, each edge has both minimum capacity and maximum capacity, meaning that in a feasible flow the real flow $f(u,v)$ of edge $(u,v,c,d)$ must satisfies: $c(u,v)\le f(u,v)\le d(u,v)$. Assuming we can solve this, we construct a network as follow: $V=\{s,t\}\cup V_0 \cup V_1$ where $V_0$ and $V_1$ are two copies of vertices in partial order meaning indegrees and outdegrees respectively $(s,u,0,\inf)\in E \space\space \forall u\in V_0$ $(v,t,0,\inf)\in E \space\space \forall v\in V_1$ $(u,u',1,\inf)\in E \space\space \forall u\in V_0, \forall u'\in V_1$ and $u$ and $u'$ represent the same vertex in original partial order Then a feasible flow corresponds to a chain decomposition of original partial order and the minimum one is the answer. Because each vertex $u$ in original partial order corresponds to $u\in V_0$ and $u'\in V_1$ and edge $(u,u',1,\inf)$ in network. So, the minimum capacity restricts that there must be a flow through this vertex. To solve this kind of network, we just put another source $ss$ and sink $tt$. And turn each edge $(u,v,c,d)$ with minimum capacity into 3 edges:$(ss,v,c),(u,tt,c),(u,v,d-c)$ in normal network. (edges $(u,v,c)$ are described as there is a edge from $u$ to $v$ with capacity $c$) Since $s$ and $t$ don't satisfy flow conversation, we add a edge $(t,s,\inf)$. The meaning is that for edge $(u,v,c,d)$, there are $c$ units of flow into $v$ and $c$ units of flow out of $u$ compulsorily.Then, we apply dinic on $(ss,tt)$ and check whether all edges from $ss$ are full. If yes, we have a feasible flow. If no, there is no feasible flow.And finally, we need a minimum feasible flow. Apply dinic on $(t,s)$ to reduce the useless flow while satisfying those minimum capacities. (since all change of flow will not have an influence on those minimum capacities)It works like this: void dinic ( int s , int t ) { while ( makelevel ( s , t ) == true ) //if there is a path find ( s , inf , t );//augment } dinic ( ss , tt ); delete_edge ( t , s );//this edge is not needed in the second dinic dinic ( t , s ); You can see this for more about this kind of network. (I know some Chinese reference about it but not in English, sorry)In this way, time complicity is $O(maxflow(100*1024 \space vertices,3*5*10^5\space edges))$ (we triple the number of edges in construction, though a bit less than that)I implemented this and got TLE (sigh) while a normal solution got AC in 904ms. (they are similar except construction of network)Because dinic performs not so well in non-bipartite graphs. ($O(m\sqrt n)$ and $O(maxflow)$)But even if i had got AC with this method, there are still too many vertices and edges to apply a network algorithm and it is still a gamble. And I was thinking about some greedy strategies or so to solve this problem instead of using network directly before checking editorial :P
•  » » » » » » » » 11 months ago, # ^ |   0 can you share the chinese references?
•  » » » » » » » » » 11 months ago, # ^ | ← Rev. 3 →   0 "上下界网络流" is Chinese name for network with minimum capacity. You can search it and find lots of blogs in Chinese.For example, link1, link2 and I like this best.They talked about find a feasible solution for a network with minimum capacity but without source and sink (capacity that flow in every vertex must equals to the capacity that flow out of it); find a feasible solution for a network with minimum capacity and with source and sink; maximum/minimum flow for a network with minimum capacity and with source and sink. You can even solve cost flow version by the same way.There is a problem about cost flow version.There is few (but there is! link3) discussion about solving maximum antichain problem by network since it's not stable compared with computing transitive closure. For we can't even say whether it will give the answer in 1 second.Btw, inspired by link3, I realized my implementation was so poor. You can see that in my solution, we use dinic(ss,tt) to find a feasible solution but we can construct it directly (cover every vertex by a chain). So, we only apply the second dinic(t,s) to reduce the answer.I got AC in 139ms. My code#include #include #include #include #include #include #include using namespace std; typedef unsigned long long ull; struct node { int v , f; node *next , *rev; } pool[5200000] , *g[520000]; int top; int n; map < string , int > ma; int a[120]; unordered_map < ull , int > ha; int index; int ss , s , t , tt; int level[520000]; int ans; ull getrand () { ull ret = 0; for ( int i = 1 ; i <= 64 ; i++ ) { if ( rand () % 2 ) { ret |= (1ull<<(i-1)); } } return ret; } void add ( int u , int v , int f , int rf ) { //printf ( "%d %d %d\n" , u , v , f ); node *tmp1 = &pool[++top] , *tmp2 = &pool[++top]; tmp1 -> v = v; tmp1 -> f = f; tmp1 -> next = g[u]; g[u] = tmp1; tmp1 -> rev = tmp2; tmp2 -> v = u; tmp2 -> f = rf; tmp2 -> next = g[v]; g[v] = tmp2; tmp2 -> rev = tmp1; //add edge:(u,v) with capacity f and (v,u) with capacity rf //meaning that there are some flow in each edge in advance } void add_edge ( int u , int v , int mn , int mx ) { if ( mn != 0 ) { add ( ss , v , 0 , mn ); add ( u , tt , 0 , mn ); } add ( u , v , mx - mn , 0 ); } bool makelevel ( int s , int t ) { int i , k; queue < int > q; for ( i = 1 ; i <= tt ; i++ ) { level[i] = -1; } q.push ( s ); level[s] = 1; while ( q.size () ) { k = q.front(); q.pop(); for ( node *j = g[k] ; j ; j = j -> next ) if ( j -> f && level[j->v] == -1 ) { level[j->v] = level[k] + 1; q.push ( j -> v ); if ( j -> v == t ) return true; } } return false; } int find ( int k , int key , int t ) { if ( k == t ) return key; //printf ( "%d %d %d\n" , k , key , t ); int s = 0 , i; for ( node *j = g[k] ; j ; j = j -> next ) if ( j -> f && level[j->v] == level[k] + 1 && s < key ) { i = find ( j -> v , min ( j -> f , key - s ) , t ); j -> f -= i; j -> rev -> f += i; s += i; } if ( s == 0 ) level[k] = -1; return s; } void dinic ( int s , int t ) { while ( makelevel ( s , t ) == true ) ans += find ( s , 999999 , t ); } void work () { int i , j , k , tmp , m; string str; scanf ( "%d" , &n ); for ( i = 1 ; i <= n ; i++ ) { scanf ( "%d" , &m ); for ( j = 1 ; j <= m ; j++ ) { cin >> str; if ( !ma[str] ) ma[str] = getrand(); a[j] = ma[str]; } for ( j = 1 ; j < (1< next ) { ans += l -> rev -> f; }*/ printf ( "%d\n" , index - ans ); } int main () { srand(678900); work (); return 0; } 
•  » » » » » » » » » 11 months ago, # ^ |   0 wow, thank you!
•  » » » » » 15 months ago, # ^ |   0 marX what is the extra logn for in the solution of B
•  » » » » » » 15 months ago, # ^ |   -8 Fix the length of the diagonal using binary search (this is $O(\log -PREC)$), then find for every given point the rotation intervals which are invalid. Now the problem is, given a set of intervals, find if there is a point no contained in any of the intervals. Sort them (this is $O(n \log n)$) and make a sweepline. It is possible to avoid the sorting part by finding the complement of each interval and intersect them.
 » 15 months ago, # |   0 Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).
 » 15 months ago, # | ← Rev. 2 →   0 Bonus: Can you solve problem D in $O(n \cdot log n)$. Hint 0This solution requires $O(n^2)$ number of restrictions. Try to use $O(n)$ restrictions instead. Hint 1Try to solve it first for the case where all brightness are different. Hint 1.1Order relationship is transitive. If brightness 1 is sorted before 2 and 2 is sorted before 3, then 1 is guaranteed to be sorted before 3. Hint 2Try to solve the problem for two brightness. (Points with repeated brightness are allowed this time). Hint 2.1You only care about points in the convex hull per brightness. Hint 2.2Polygon tangents.
•  » » 15 months ago, # ^ | ← Rev. 5 →   0 I can only come up with an $O(n^2 \cdot log(n))$ solution which should be good enough in theory but I'm getting TLE due to the constant :(. The idea is to iterate over all possible directions counter clockwise ($O(n^2)$ directions) and for each direction we have all straight lines parallel to this direction and for each straight line we have all the points intersected by this straight line (we can compute all this in $O(n^2 \cdot log(n))$ by considering each pair of points $p_i$ and $p_j$ and computing the vector $p_j - p_i$ and a hash for the straight line defined by them and storing things in maps / unordered_maps). Then we initially rank points based on the first direction in $O(n \cdot log (n))$ (given a direction vector, we can rotate it 90 degrees ccw and then sort everything by projecting using dot product) and then in $O(n^2)$ we can count how many pairs of points are wrongly ranked. Then we iterate over all remaining directions, so when we transition from one direction to the next direction ccw the points that were collinear in the previous direction now are ranked in a strictly increasing order, so we sort those subranges and check quadratically the ranking conflicts in those subranges, and the points that become collinear in the current direction they no longer have ranking conflicts. If at some point the counter of ranking conflicts becomes 0, we print "Y", otherwise we print "N". I think this should work but I'm getting TLE. How can I improve it?
•  » » » 15 months ago, # ^ |   0 This is a very nice, but complex, solution. It is very hard indeed remove the $O(n^2 \log n)$ in the beginning of your approach.The expected solution was: Every pair of points $p_i$, $p_j$ with different brightness $b_i < b_j$ defines a range of valid directions for this two points. Note that the range is 180 degrees wide. All directions $d$ such that the dot product between $d$ and $p_j - p_i$ is non negative is a valid direction for this two points. There is an answer if and only if the intersections of all such ranges is not empty. Finding the intersection of all this ranges can be done in $O(n^2)$ (no need to sort), but even sorting this intervals to find the intersection fit in time.
•  » » » » 11 months ago, # ^ | ← Rev. 3 →   0 For every $i,j$ such that $b_i < b_j$ we take the range: $angle(p_j-p_i)$ $+-$ $pi/2$ right?This is what I'm doing here then I do a sweep on the ranges, but I keep getting WA39, does anyone spot something wrong?Edit: I found my mistake. It was simply the case when there is no $b_i < b_j$ so my code never enters the sweep loop and returns N instead of Y.
 » 15 months ago, # |   0 Auto comment: topic has been updated by k790alex (previous revision, new revision, compare).
 » 15 months ago, # |   0 How to solve C?
•  » » 15 months ago, # ^ |   +10 I don't know what was the intended solution. Mine uses a segment tree to keep track of biggest and smallest prefix sum. Then (in $O(log(n))$) we can find the first moment in which we need to "cut" our value if we start at position $X$ with value $Y$. Then, precompute "jumps" between cuts with a sparse table and you are done.
•  » » » 15 months ago, # ^ |   0 What do you mean with "jumps" in a sparse table .. and why a sparse table?
 » 15 months ago, # |   +15 What is the intended solution for problem H?
•  » » 15 months ago, # ^ | ← Rev. 3 →   +30 This problem was planned as the most or second-most difficult of the set (with Problem J). There isn't any greedy approach. IdeaFirst of all, let’s start thinking an easier problem. We want to calculate the expected amount of turns which a player needs to score 75. Approach to the easier-problemIt seems like a dp-problem. So, we are going to call dp[x][y] to the expected number of turns that we need to get 75 if we have already x points and our total turn has actually y points. For example, dp[75][0] is 0, because we don’t need any turn and dp[74][0] is going to value infinite because we cannot get 75 from 74. For convenience, we count the turns after the “hold” or the “1-roll”, so dp[73][2] is 1 because after holding we get 75. We are going to calculate dp[x][0] in decreasing order of the x, so we assume that we already know all the dp[x1][0] for higher x1.Let’s think dp[73][0]. We have to roll a 2 because any other number makes that we lose the turn. So:dp[73][0] = ((1 + dp[73][0]) + dp[73][2] + dp[73][3] + dp[73][4] + dp[73][5] + dp[73][6]) / 6As we said, dp[73][2] is 1 and in all others we have to lose the turn. So:dp[73][0] = (5 * (1 + dp[73][0]) + 1 ) / 61/6 dp[73][0] = 1dp[73][0] = 6This example is easy, because basically we don’t need an strategy (we don’t need to choose between either hold or keep on rooling). In most cases, although that for any particular strategy we can calculate the probability of lose the turn without scoring any point (in the previous case was 5/6), we dont know which is the optimal strategy. So we can’t do a dp+Markov to solve the problem.The solution is calculated numerically: Solution to the easier-problemThe key is the value dp[x][0]. If we know previously the value of dp[x][0], we can guess an strategy for every state dp[x][y] (descending by 'y') because we know the probability of winning if we hold, if we continue and roll a 1 and if we continue and roll any other number. Formally, if dp[x][0] = k, and we know all the higher states (dp[x1][0] with x1 > x), we can iterate descending for all y (dp[x][y]) and see if we have to roll again or hold. In conclusion, if we get the real value of dp[x][0], we can know if this is the real answer.So, we have 2 different numerical solutions: We can make a binary search in the value of dp[x][0]. If after the iteration, rolling dp[x][0] we got a worse value means that the real value is, in fact, worse. Making a binary search, we solved the problem iterating for higuer-x to lower-x. Also we can calculate dp[x][0] improving step by step. So, inicially dp[x][0] = INFINITE and for all the other states the strategy is Hold. Next, we can improve each state with the possibility of Continue several times until we don’t improve any of them. This method has a precision of 1e-9 after 200 steps. Final ApproachLet’s return to the original problem. dp[x][y][z] means the probability of winning with the optimal strategy if you have x points, your opponent have y points and you have z points in this turn. In this case we are going to calculate dp[x][y][0] in decreasing order of x+y, so we assume that we know all the dp[x1][y1][0] for higher sum x1+y1.We are going to use the ideas of the 'expected amount of turns' problem. The difference is that we have to guess at the same time the states dp[x][y][0] and dp[y][x][0]. This is a problem because we have to guess 2 numbers. I don’t know how to solve with the binary search idea (see next comment of ffao), but we can solve using the 2nd idea of improving step by step. Final SolutionSo, we have to calculate dp[x][y][z] and dp[y][x][z] for all the z at the same time.For that, we create two arrays, lo[x][y][z] and hi[x][y][z] which are the low_bound and the high_bound of the solution. Inicially, lo[x][y][z] = 0 and hi[x][y][z] = 1.After each step, we can optimize lo[x][y][z] with the formula: lo[x][y][z] = max(hold, roll); where hold is ''1-hi[y][x+z][0]'' and roll generally is ''(lo[x][y][z+2] + ... + lo[x][y][z+6] + (1-hi[y][x][0]) ) / 6'' Also, we can reduce the high_bound using this formula: hi[x][y][z] = max(hold, roll); but where hold and roll are similar to the previous ones but using the opposite arrays. At any step, lo[x][y][z] could only increase, hi[x][y][z] could only decrease, and lo[x][y][z] <= dp[x][y][z] <= hi[x][y][z] as invariant.Finally we can use the values of the arrays to decide if you have to hold or continue.
•  » » » 15 months ago, # ^ |   0 I believe the first approach still works for the harder problem: IdeaLet $A$ be dp[x][y][0] and $B$ be dp[y][x][0]. Suppose you magically learn the value $A$. From this, it is pretty easy to compute $B$, since the expected returns from holding or continuing at any point are known. Let the function that gets $B$ from $A$ be $f(A)$.Similarly, you can compute $A$ from $B$. Let this function be $g(B)$.What you want is to find $A$ such that $g(f(A))=A$. You can do this by binary search: if $g(f(A))>A$, you guessed too low; if $g(f(A)) •  » » » » 15 months ago, # ^ | ← Rev. 2 → +18 Nice!Yes, I didn't have time to see carefully, but I'm pretty sure the AC solution in contest used your idea and also I think that mjhun used the same idea to solve the problem. :)By the way, for people who likes graphics, marX maked this one with the optimal strategy (played to 101 instead of 75): https://giphy.com/gifs/U1h7WtR89xHpkFpD6bAs he said: "The animation shows the following: The image X shows the matrix if my oponent have X points already what is the probability I win with each action, Continue (1st graph) and Hold (2nd graph). The axis stands for (My current points vs The points in the counter). The third graph is binary showing whether the best strategy is Continue or Hold." •  » » » » » 15 months ago, # ^ | 0 The AC solution in contest was the naive dp with an extra state for the amount of passed rounds. Turns out this converges quickly enough. •  » » » » » » 15 months ago, # ^ | ← Rev. 2 → 0 I know that you are from the same university and also I didn't read the code carefully :), but are you sure?I read these lines of code that makes me fell that your solution used ffao's idea: Spoilerdouble begin = 0.0, end = 1.0; for (int i = 1; i <= 50; i++) { guess = (begin + end)/2.0;  •  » » » » » » » 15 months ago, # ^ | 0 I'm not from the same university as them, I'm just saying what they told me after the contest. AFAIK, the CCL team "Chefes do Beto" tried to solve it using that binary search but the official team from USP solved it adding an extra state. •  » » » » » » » » 15 months ago, # ^ | 0 You are right, the AC solution was from SP not UFPE, my mistake. But anyway, these lines comes from this solution. •  » » » 15 months ago, # ^ | ← Rev. 2 → +10 We have this (very easy) solution link. I am not sure if it's the same as the solution tfg suggests above, but it seems to converge very quickly. Does anybody have an idea why it converges so quickly instead of exploding, for example? And does it depend on the initial values? (My guess to what happens here is that the implicit transition matrix$T(i, j, i', j')$that updates$M(i, j, 0)$at each step has some nice spectral properties, but I don't know enough linear algebra to prove). •  » » » » 15 months ago, # ^ | 0 Very interesting solution! :)I don't know linear algebra also but... Spoiler We can prove that if converges, converges to the solution. We can prove that it converges for all initial values :). To see why it converges so quickly in your solution probably you need linear algebra. But if you process layer by layer (modifying the order of the variables in the for loops), I suppose that the idea could be to define some measure related by the difference between M(i,j,0) and M(j,i,0) to the real values assuming that all the higher position of the matrix are the real ones. And we have to prove than this measure converges to 0 very quickly.  » 15 months ago, # | +10 How to solve problem J? •  » » 15 months ago, # ^ | ← Rev. 3 → +10 Hint 1For a fixed position we can find the positions to the left and to the right that we may end up. That is, the ones that we will be trapped if we stop there looking to some direction (any direction). Hint 2The answer is the one with biggest height between the two possible positions, the update is simple. ProofLets say that we started in position y and the best towers to the left/right are x and z respectively. Notice that after every jump we are looking in the direction of the start position, and also notice that we can only endup in x looking for z or in z looking for x.This problem is really beautiful and shows that a problem can be hard and simple •  » » » 15 months ago, # ^ | 0 Thanks! I did understand that... But how to update this?I mean in order to find the trapped point for position x while looking at left / right at first, we need to use a stack to find the nearest left / right one which can not find the right / left higher point right? But how to do update operation? I have no idea about that... •  » » » » 15 months ago, # ^ | ← Rev. 3 → 0 It's kinda casebash IdeaFor an update in y, lets x and z be the first values bigger than y in left/right. Notice that possible answers can't have both x and z, since we need to be bigger by one side, so everyone in [x+1 , z-1] is not an possible answer anymore if we have both x and z. Now we have 3 cases, when we have an x but not an z , when we have an z but not a x, and when we are the bigger tower, for the first case, everyone in the right of y can't be trapped looking to the left, and everyone between [x+1 and y-1] are not an possible answer anymore, for the second case is analogous, for the third-case, the suffix can't be trapped to the left, and the prefix to the right. •  » » » » 15 months ago, # ^ | 0 Just use iterative segment tree and I'm sure it fits TL with a binary search. Or you can do it in O(log) with a bit more code on iterative or directly on recursive seg tree. This also removes the need to updates make the height greater. •  » » » 14 months ago, # ^ | 0 Hint 1: For a fixed position we can find the positions to the left and to the right that we may end up. That is, the ones that we will be trapped if we stop there looking to some direction (any direction). If there were no updates, I think we can compute this for every position using DP + binary search + sparse table. Given a fixed position, we can binary search the first position to the right which is taller than the fixed position, and the same for the left (we use sparse table for maximum range query in the predicate of the binary search). Knowing this for every position, then it's easy to write a recursive function to find the final position we get trapped in if we start in every position and we can memoize this function (i.e. DP) to avoid recomputations. Unfortunately, this approach doesn't work due to the updates :(Any ideas on how to handle the updates efficiently? Hint 2: The answer is the one with biggest height between the two possible positions, the update is simple. I don't understand this. What do you mean by "two possible positions"? Proof: Lets say that we started in position y and the best towers to the left/right are x and z respectively. Notice that after every jump we are looking in the direction of the start position, and also notice that we can only endup in x looking for z or in z looking for x. I don't understand this either. What do you mean by "best towers"? "Best" in what sense?  » 15 months ago, # | 0 How to solve problem L? •  » » 15 months ago, # ^ | 0 I don't know if this is the official solution but here it goes:You need to get a square sub-matrix where each row is either full with G or full with B. Now, you can create a new matrix$B$with$N$rows and$M-1$columns, where$B_{i,j}$is 0 if$A_{i,j} = A_{i,j+1}$and$1$otherwise.Now, a square submatrix with side$L$in$A$will be a submatrix with$L$rows and$L-1$columns in$B$. You need to find the biggest$L$such that there is a submatrix in$B$with$L$rows and$L-1$columns full with zeros.You can do this with some preffix sums and binary search. Or you can even ignore the binary search, keeping track of the biggest$L$you have found so far. •  » » 15 months ago, # ^ | ← Rev. 2 → +5 An interesting and simple solution in$O(n*m)$, which is really similar to the algorithm used to find the biggest square of ones in a matrix of 0's and 1's:$dp(i,j)$= longest side of a valid square having lower-right corner in$(i,j)$We have two cases:$\underline{S_{i,j} == S_{i,j-1} \land S_{i-1,j} == S_{i-1,j-1}:}dp(i,j)=max(dp(i-1,j),dp(i,j-1),dp(i-1,j-1))+1\underline{Otherwise:}dp(i,j)=1$Note that the first condition is the only one necessary to extend by one the length of a valid square. Here is my code :)  » 15 months ago, # | 0 how to approach B  » 15 months ago, # | 0 Any more detailed idea of ​​how to solve problem C? :c •  » » 15 months ago, # ^ | +15 I think my solution is the same as MarcosKLet$h[i]$be the prefix sum of$a[i]$.Now write a segtree which can perform the following query:$query(l, r, x, y)$returns the smallest index$i$in the range$[l, r)$such that$h[i]$is outside of the range$[x, y]$. It also returns a type$t$which is 0 if$h[i] < x$and 1 if$h[i] > y$. This segtree can be used to find the first time the amount owned overflows (goes above U) or underflows (goes below L)Next build a sparse table$f[t][i][j]$.$f[0][i][j]$: assuming that, at time$i$we owned$L$, this stores the$2^j\text{-th}$smallest time$k$such that there is an over/underflow on index$k$. It also stores a type, 0 if it was an underflow, and 1 if it was an overflow.$f[1][i][j]$stores the same thing, except we assume that at time$t$we owned$U$.We can initialize$f[0][i][0]$and$f[1][i][0]$using the segtree.Then$f[0][i][j]$and$f[1][i][j]$can be computed as usual with a sparse table.Now, for each query:First, use the segtree to find the first location$i$after the beginning day where we encounter an overflow/underflow.Next, use the sparse table to find the last location$j$before the end day where we encounter an overflow/underflow.Finally, we know that between time$j$and the end day, there are no underflows or overflows (Otherwise$j$would have been larger). So we can just use$h[end]-h[j]\$ to find how much the amount owned changed.
•  » » » 15 months ago, # ^ |   0 Yes, it's exactly the same idea. It was a nice problem
•  » » 15 months ago, # ^ |   +18 There's an alternative really nice solution that avoids a segtree entirely by doing the queries offline, and simulating all the queries at once.We can sort the start/end times of the queries, and sweep from month 0 to the last month. As we encounter start times, we maintain the values for all of these queries by storing the values in a sorted list (a set), with a global OFFSET variable. After each month we can increment all our query values with the OFFSET variable. This might cause some values to exceed the bounds, so we can use our set to check if any queries exceed U-OFFSET or L-OFFSET, and merge those elements into one element (with a DSU or similar thing) since every element can be merged at most once.This way, we know the exact value for those queries when we encounter an end time.
 » 15 months ago, # | ← Rev. 2 →   -11 Nice
 » 12 months ago, # |   0 Sorry, Can someone please tell me why this solution for I is wrong? 72862637
•  » » 12 months ago, # ^ |   0 I submitted your solution using c++17 and it was AC. I presume the problem with c++11 is in the last line: cout << dp( 1 ) << ' ' << leafs.size() << '\n'; In this case you are populating leafs container inside the function dp, but maybe it is undefined the order in which dp(1) and leafs.size() is evaluated, or simply it changed from c++11 to c++17.Fixing it for c++11 should be straight forward, split it in two statements: cout << dp( 1 ) << ' '; cout << leafs.size() << '\n'; 
 » 2 weeks ago, # |   0 Have some corner case for G?, It fails in test12 :/