By RAD, 10 years ago, translation,

Initially the order of problems was A-C-E-D-B. But we were not sure about last two.

166A - Rank List

This is simple straight-forward problem — you were asked to sort the teams with the following comparator: (p1 > p2) or (p1 = p2 and t1 < t2). After that you can split the teams into groups with equal results and find the group which shares the k-th place. Many coders for some reason used wrong comparator: they sorted teams with equal number of problems by descending of time. Such submits accidentally passed pretests but get WA #13.

166B - Polygons

Polygon A is convex, so it is sufficient to check only that every vertex of polygon B is strictly inside polygon A. In theory the simplest solution is building common convex hull of both polygons. You need to check that no vertex of polygon B belongs to this hull. But there is a tricky detail: if there are many points lying on the same side of convex hull than your convex hull must contain all these points as vertices. So this solution is harder to implement and has some corner case.

Another solution: cut polygon A into triangles (by vertex numbers): (1, 2, 3), (1, 3, 4), (1, 4, 5), ..., (1, n - 1, n). The sequences of angles 2 - 1 - 3, 2 - 1 - 4, 2 - 1 - 5, ..., 2 - 1 - n is increasing. It means that you can find for each vertex of B to which triangle of A it can belong using binsearch by angle.

Similarly you can cut polygon A into trapezoids (with vertical cuts). In this case you'll need a binsearch by x-coordinate.

166C - Median

If the initial array doesn't contain number x, than you definitely need to add it (that's +1 to answer). Than do the following. While median is strictly less than x you need to increase it. Obviously the surest way to increase the median is to add a maximal possible number (105). Similarly while the median is strictly more than x, add a number 1 to the array. Constraints are small, so you can add the numbers one by one and recalculate the median after every addition.

Also there is a solution without any cases: while the median isn't equal to x, just add one more number x to array.

166D - Shoe Store

Let's sort the people by decreasing of shoes size. Observe that when considering the i-th man we are interested in no more than 2 pairs of shoes: with size li and li + 1. It allows solving with dynamics. The state will be (the number of first unconsidered man i, is pair of shoes with size li available, is pair of shoes with size li + 1 available). You have 3 options: leave the i-th man without shoes or sell him a pair of shoes of one of suitable size (if available).

166E - Tetrahedron

Obvious solution with dynamics: you need to know only how many moves are left and where is the ant. This is 4n states, each with 3 options – most of such solution passes. Observe that the vertices A, B, C are equivalent. This allows writing such solution:

int zD = 1;
int zABC = 0;
for (int i = 1; i <= n; i++) {
int nzD = zABC * 3LL % MOD;
int nzABC = (zABC * 2LL + zD) % MOD;
zD = nzD;
zABC = nzABC;
}
cout << zD;


Also this problem could be solved by log(n) with binary exponentiation of some 2 × 2 matrix into power n.

• +30

 » 10 years ago, # | ← Rev. 2 →   0 Edited -- Fixed my code! Thanks to Igel_SK!
 » 10 years ago, # | ← Rev. 2 →   0 Isn't the state for D too big?Also, I see people doing bipartite matching in a greedy way, why does this work?
•  » » 10 years ago, # ^ | ← Rev. 2 →   +2 Bipartite matching with sorting shoes works correctly, it can be proofed (in russian). I think it should get TLE but the tests were weak :)
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 I solved with the DP this way: you have the current person and a mask that represents if the 2 sizes of shoes that this person can use are available (costumers are sorted by shoe size), so it will be a dp[10⁵][4] table.
 » 10 years ago, # | ← Rev. 2 →   0 Great explainatiions:) Can you explain your second solution on Problem B in detail ? Thx How do you perform binsearch on angles to calculate whether every vertex is in Polygon A or not
 » 10 years ago, # |   0 I solved E:Tetrahedron using the problem (3^n+3*(-1)^n)/4 . Here is my solution . However it failed the system test and when I used BigInteger it passed.Here is the 2nd version. 2 question: 1.Why does the first solution fail... 2.Is there any thing I can do to avoid BigIntegers
•  » » 10 years ago, # ^ | ← Rev. 2 →   +5 Use longDoubles are not accurateYour code with long instead of double 1403711
•  » » 9 years ago, # ^ |   0 Got the same problem.
•  » » 9 years ago, # ^ |   0 Hi , can you explain your solution for this question some better ? I mean i know the your solution is true but how did you reach this solution ? Plz answer
•  » » 5 years ago, # ^ |   0 how did you arrive at this formula can you please explain??
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 do the adjacency matrix A (in this problem you will have a matrix where A[i][j] = 1 if i!=j and A[i][j] = 0 if i==j). now A^2 count paths with two edges, A^3 count paths with three edges and so on, do exponentiation using diagonalization i.e A = P*D*P^(-1)A^n = P*D^n*P^(-1)You have to find a formula for one element on the diagonal using matrix P, D^n and P^(-1), just there you will notice the formula (3^n+3*(-1)^n)/4. (all of elements on diagonal are equal for this reason you need to find the formula of only one of them)be carefull doing division using modulo, here you will find good information of how to do that https://codeaccepted.wordpress.com/2014/02/15/output-the-answer-modulo-109-7/
•  » » » » 11 months ago, # ^ |   0 I don't understand how A^2 counts paths of length 2 and A^3 counts paths of length three etc. Am I missing some concept?
•  » » 5 years ago, # ^ |   0 Hey! I am a beginner learning coding. I was solving 166E in problem set but couldn't. Read your comment and solution can you please explain me your code after ans%=mod on line 34? I will be thankful to you.
• »
»
2 years ago, # ^ |
0

mod function in my code is not working

# include <bits/stdc++.h>

using namespace std; //#define int ll; // [9,223,372,036,854,775,807 to -9.....808] 19 digits

# define len(x) (int)((x).length())

template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;} template<typename T,typename T1>T amin(T &a,T1 b){if(b<a)a=b;return a;}

//const int mod=998244353; const int mod = 1000000007; const int N=1000000+6;

# define M_PI 3.14159265358979323846

const int maxn=1e5+5;

int main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int n;cin>>n;
int abc=3,d=0,abcp=3,dp=0;

rep(i,2,n+1)
{
abc=((dp*3)%mod+(abcp*2)%mod)%mod;
d=abcp;
abcp=abc;
dp=d;
}
cout<<d;

}

can you plz tell me why??

 » 10 years ago, # |   +1 What 2 x 2 matrix can be used in E? I've only seen it solved with a 4 x 4 matrix with diagonal = 0 and rest = 1.
•  » » 10 years ago, # ^ |   0 See Egor's solution: 1390234
•  » » » 10 years ago, # ^ |   0 Can you explain the idea behind this solution?
•  » » » » 10 years ago, # ^ |   0 In general, you can do matrix exponentiation (that is, raising matrix M to the N-th power) in O(logN) time, where N is the exponent. If you exploit a "matrix notation" for your dp recurrence, then you can reduce it to this problem, thus solving it in O(logN).For example, it is possible to find the N-th fibonacci number using this method. For a better explanation, check out the "Fibonacci log N" tutorial on e-maxx.ru
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 let A be a matrix of 4X4 where, A[i][j] = 1 if i != j, and 0 otherwiseNow, A represents the number of paths from i to j using 1 edge. Using some basic intuitions we can prove that A*A will represent the same but using 2 edges. So, we can A^n will represent all the paths from i to j using n number of edges. Now, you can exponent it or derive a formula. I derive a formula, see it here 51966083
•  » » » » » 23 months ago, # ^ |   0 Thank you for the explanation! Can you share a proof also?
•  » » » » » » 21 month(s) ago, # ^ |   0 There was this video I watched today on matrices which gave me the insight regarding how to solve this problem. If you're really short on time then you can just watch it from the timestamp.Link to the video
•  » » » » » » » 18 months ago, # ^ |   0 thanks
 » 10 years ago, # | ← Rev. 2 →   0 Sorry about that, just ignore the post.
 » 10 years ago, # |   0 from math import *def fast_exponentiation(base, n): if n == 1: return base else: if n % 2 == 0: base1 = fast_exponentiation(base, n/2)**2 return base1%1000000007 else: return (base*fast_exponentiation(base,(n-1)/2)**2)%1000000007t = int(raw_input()) if t%2 == 0: print ((fast_exponentiation(3,t) + 3)/4)%1000000007 else: print ((fast_exponentiation(3,t) — 3)/4)%1000000007Why is this code in Python wrong for thetraedron?
•  » » 10 years ago, # ^ |   0 Note: you can use the built-in function pow for fast modular exponentiation: pow(3, t, 1000000007)
•  » » » 10 years ago, # ^ |   0 I keep getting wrong answer... I get right values if I put modulus outside all the expression, so:print ((fast_exponentiation(3,t) + 3)/4)%1000000007 gives correct value, but slow and print ((fast_exponentiation(3,t) + 3)/4) within the fast exp with mod gives WA, why?
•  » » » » 10 years ago, # ^ |   0 You can't divide by 4 if you use mod before it. You should multuply pow(4, p-2, p) instead
•  » » » » 10 years ago, # ^ |   0 Try ((fast_exponentiation(3,t) + 3) * 250000002) % 1000000007, and take modulo on each fast_exponentiation step.
•  » » » » » 10 years ago, # ^ |   0 ant.ermilov thank you for the tip, I have seen it in a solution as well, but can you explain to me, or point me to somewhere that can tell me, why is that particular number used?
•  » » » » » » 10 years ago, # ^ |   +3 At first, let's try to understand, why your approach does not work. For example, we haveY = M+1, Y % M = 1,but (Y / 4) % M != (Y % M) / 4. So division can be substituted by multiplication. In general, we have modulo M, divisor D and want to find such Z that for each X: (X / D) % M = ((X % M) * Z) % M.After simple transformation we will get (X * Z) % M = 1.For particular case 250000002 * 4 = 109 + 7 + 1.Some extra info: Z can be found iff gcd(X, D) = 1, and simpliest way described at riadwaw's comment above. From Euler's theorem we get Z = (DM - 2) % M.
•  » » » » » » » 10 years ago, # ^ |   0 Thank you very much to both :D I got axcepted :)
•  » » » » » » » 9 years ago, # ^ |   0 Amazing explanation! Thanks
 » 8 years ago, # | ← Rev. 2 →   -8 What does non-degenerate mean in 166B - Polygons (Div2 B) ?
•  » » 8 years ago, # ^ |   0 Found myself : link
 » 8 years ago, # |   0 @riadwaw Can you please explain In the solution to E why has nzABC been multiplied by 2 in the fifth line?int nzABC = (zABC * 2LL + zD) % MOD;Thanks a lot.
•  » » 8 years ago, # ^ |   0 Let Ai denote number of ways to finish near the vertex A after i moves (same for Bi, Ci, Di). Easily, Ai = Di - 1 + Bi - 1 + Ci - 1 Bi = Di - 1 + Ai - 1 + Ci - 1 Ci = Di - 1 + Ai - 1 + Bi - 1 Di = Ai - 1 + Bi - 1 + Ci - 1with the initial conditions A0 = 0, B0 = 0, C0 = 0, D0 = 1Due to the symmetry $A_i=B_i=C_i=ABC_i$, so ABCi = Di - 1 + ABCi - 1 + ABCi - 1 = Di - 1 + 2 * ABCi - 1 Di = ABCi - 1 + ABCi - 1 + ABCi - 1 = 3 * ABCi - 1
•  » » » 8 years ago, # ^ |   0 Thanks a lot!!
•  » » » 8 years ago, # ^ |   0 Nice Explanation :)
•  » » » 8 years ago, # ^ |   0 A path like A-B-D-C-D is valid, is it?
•  » » » » 5 years ago, # ^ |   0 yes
•  » » » 7 years ago, # ^ |   0 thanks a lot
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 meshanya How do you know that points A, B, C are symmetric? What do mean by symmetric? Geometric symmetry or some other symmetry?
•  » » » » 23 months ago, # ^ |   0 Its like, in one jump the ant can move from any vertex to any other vertex(all are adjacent to one another).So the penultimate vertex(second vertex from the end) can be any of the three as the jump is independent.
•  » » » 5 years ago, # ^ |   0 Great explanation Indeed!
 » 7 years ago, # |   0 TETRAHEDRON : can this problem be think in a way that if u want to reach at D in n steps, then to travel n — 1 steps 3 ^ (n — 1) ways possible, now this case include that if u reached at D in n — 1 steps therefore to reach in n steps ans(in n steps) = 3 ^ (n — 1) — ans(in n — 1 steps); which is a DP solution eg — to reach in 1 steps = 0 to reach in 2 steps — 3 ^ (2 — 1) — 0; to reach in 3 steps — 3 ^ (3 — 1) — 3 = 6 to reach in 4 steps — 3 ^ (4 — 1) — 6 = 21 to reach in 5 steps — 3 ^ (5 — 1) — 21 = 60
•  » » 6 years ago, # ^ |   0 Thanks for the explanation.
•  » » 5 years ago, # ^ |   0 Nice Explanation thank you
•  » » 5 years ago, # ^ |   0 beautiful explanation.
•  » » 23 months ago, # ^ |   0 your explanation is too good i am searching for such type of explanation
•  » » 21 month(s) ago, # ^ |   0 Thanks a lot brother . I was so confused at others' explanations but Yours Just cleared up all The confusions
 » 5 years ago, # | ← Rev. 2 →   0 I'm interested in E,whether there is any simple formula without matrix.i can't get it,anybody got it and coubld you share it?
•  » » 5 years ago, # ^ |   0 CAN anybody explain E in detail? Can't get it.Thanks!
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Let f[A][j] is the number of ways from D to A by going j steps,as same,f[B][j], f[C][j] and f[D][j], we know f[D][0] = 1, f[A, B, C][0] = 0(because the ant starts at D).then you get four equations below:f[A][j] = f[B][j - 1] + f[C][j - 1] + f[D][j - 1]f[B][j] = f[A][j - 1] + f[C][j - 1] + f[D][j - 1]......f[D][j] = ...you can solve this problem in O(n),the answer is .but it's too slow.you can express the four equations by matrix.then it's obvious to solve the problem by Successive Square Method with matrix in .
•  » » » » 23 months ago, # ^ |   0 Thank you, I finally understood it!
•  » » » » 13 months ago, # ^ |   0 Can you please share you code for this problem?
 » 5 years ago, # | ← Rev. 2 →   0 @RAD In question B Polygons, What's the problem if we directly compute the convex hull of all points and check if any point of B is present in it ? I couldn't understand the mistake!!
 » 5 years ago, # |   0 Hi... . Could you please explain why is the output for testcase #13 of problem 166A - Rank List 1?
 » 4 years ago, # |   0 I am getting a RTE when I am submitting the solution for A. I have used a custom sort function and am baffled as to why I am getting the RTE sometimes (it is giving RTE sometimes only). Here is the code35896046Thanks in advance!
 » 3 years ago, # |   -6 My Python 3.6 solution fails with O(n) complexity.
 » 3 years ago, # |   0 I was able to solve Div 2 C Median using an O( 1 ) approach. Submission is here: https://codeforces.com/problemset/submission/166/52647089 .Basic Idea: We have to ensure that the element we have to make as median (x) has to be at the central position. Now there can be 3 types of elements obviously: (i) smaller than x (ii) equal to x (iii) larger than xNote that there can be duplicates so the number of elements equal to x can be more than 1 (or even 0). Our final aim is to ensure one of the elements equal to x lands up at the central position at the end. We know that in the final answer, 0 <= number of elements on right of median — number of elements on left <= 1 In case there are more than one equal elements, we can observe that the optimal answer will always have more of the extra equal elements on the side with less number of elements ( smaller or larger ). And the situation will look like this:Now we have to find the number of elements that need to be added: Case 1: When number of smaller elements < number of larger As the left side can have one lesser elements than the right, number of elements we need to add is (elements greater than median — elements less than median — (elements equal — 1) — 1). Why elements equal — 1 ? Because one of these elements shall be at the median position. Obviously, it can't be less than 0, so we have to max it with 0. And also we subtract an additional -1 as we are allowed to have left side smaller.Similarly we can devise Case 2 and 3 where elements on both side are qual or smaller > larger. I guess code will be able to explain itself better now !
 » 3 years ago, # |   0 I can't get the E problem n = 4; D-A-B-C-D (3!) D-A-D-B-D (2!) D-B-D-C-D (2!) D-A-D-C-D (2!) D-A-D-A-D D-B-D-B-D D-C-D-C-D That's 15 not 21 or I missed something?
•  » » 23 months ago, # ^ |   0 D-A-B-C-D D-A-C-B-D D-A-D-A-D D-A-C-A-D D-A-B-A-D D-A-D-C-D D-A-D-B-D Similarly for D-B AND D-C. therefore we get 3*7 i.e 21
 » 3 years ago, # |   0 For 166 C — Is their a direct mathematical (formula based) approach in which we dont have to use a loop once we have taken the input?
•  » » 2 years ago, # ^ |   0 If you want to see a non-loop solution. Here is mine. I sorted the input, checked if I already have the median position satisfied with k (print 0 in this case), otherwise there will be 2 cases: 1) There is a smaller element at the position we require. In this case I used lower_bound to find the first possible place for the given k. This position, temp = [new_size + 1 / 2 ] so calculate the new_size from this formula. Rest is trivial. 2) There is a larger element at this position. Using the same thing we did in the last case. But here I use upper_bound (think why). This will be temp (not exactly, think why) and use the same formula. Rest is trivial and understandable from code. https://codeforces.com/contest/166/submission/78018358
 » 2 years ago, # | ← Rev. 3 →   0 Hello! I am new to dynamic programming and I tried to solve E. My method for n steps was for n-1 moves I considered 3 ways for the ant to move and for the last move I considered only 1 way to move. Then I subtracted the the answer of (n-1)th step from the answer I got so that all the possibilities where the ant would be at point D at the (n-1)th step would get subtracted. is this the right approach? Just curious. Thanks.
 » 2 years ago, # | ← Rev. 3 →   0 In case someone did not understand the editorial of 166E — Tetrahedron, here is a simple way of looking at the solution : zD is the number of ways of reaching D in i steps and zABC is the number of ways of reaching A or B or C in i steps(A , B, C are equivalent points). Since the ant starts of from D, initially (at i = 0) zD = 1 and zABC = 0.Now in each subsequent step, 2 things can occur : If the ant was at D, it will come down to any of the A,B,C points. That means it has 3 options. Hence , nzABC = zD. If the ant was at either of the A,B,C positions, it can either climb upto point D or go to any of the 2 other equivalent points i.e. if the ant was at A, it can go to D and hence nzD= 3*nzABC ; or it can go to either B or C (2 available options) which increases nzABC by 2*zABC and hence nzABC += 2*zABC. Therefore at last nzABC = 2*zABC + zD and nzD = 3*nzABC.
•  » » 2 years ago, # ^ |   0 Thanks to you,i understood this. Can you help me whats wrong with my way. Two choices - To reach D in N steps means, we jump between points A,B,C for n-2 steps.(3*(2^(n-2)))(3,because we start from D to A,D to B,D to C).(in this choice we didn't go to D in between N steps) - To reach D in (N-2) steps +(N-3) steps+(N-4) steps+...+(N-N-1)steps.In this choice,we return to D in first 2 steps and then again in (N-2) steps.(Similarly for 3 ,4,..... steps).TO GET THE TOTAL SOLUTION, ADD CHOICE 1+CHOICE 2. I submitted this got WA in Test case 6.
 » 2 years ago, # |   0 In question E.Tetrahedron.We can we can transform the tetrahedron into a graph with node 0,1,2,3 so the adjacency matrix would be A={{0,1,1,1},{1,0,1,1},{1,1,0,1},{1,1,1,0}},no. of path between any two nodes(i,j) of length n is element at (i,j) in A^n.We can do matrix multiplication in O(logN) time.This approach can also be used.Hope this helps :)
 » 22 months ago, # |   0 here's my code of problem E with matrix exponentiation taking 4X4 matrix https://codeforces.com/contest/166/submission/87237788
•  » » 13 months ago, # ^ |   0 why you are calculating A^(n-1 ?
 » 22 months ago, # |   0 I am getting TLE in problem E,i am using dp approach.Anyone please help code submission: https://codeforces.com/contest/166/submission/88417439
•  » » 22 months ago, # ^ |   0 declear dp array globally then you will not be needed to make whole array zero .may be thats why you are getting tle
•  » » 16 months ago, # ^ |   0 As far as I can see in your code, you are initializing every entry to 0, which is taking $O(n^2)$complexity. But the code should work in linear time. If you notice your recursion relation then you will see that dp[i][0] or dp[i][1] is related only to dp[i-1][0] or dp[i-1][1]. So you need only the previous row to calculate the new row. So just maintain two arrays for previous row and new row, and all is set! I hope it clears your doubt. :)
 » 22 months ago, # |   0 which data structure to use in c?
 » 16 months ago, # | ← Rev. 3 →   0 here is my code for 166E. Tetrahedron 105550054My code is giving a time limit exceeded for the test case with n = 10000000. But when I change the vector with an array, i.e. in 105550845 It is running much faster and got accepted! Why is this problem with vectors? Why is the vector so slow? I am new here :)
•  » » 16 months ago, # ^ | ← Rev. 3 →   0 this should pass UPD: sorry I miss understood your question :)I think it's because you're creating n unnecessary vectors while you can just creat 1see the code above it's faster and with vectors :)
•  » » » 16 months ago, # ^ |   0 Thanks Satoru for your answer! :) I got it accepted using your correction. But still it is taking more time than with the array one. So vectors are really slow?
•  » » » » 16 months ago, # ^ |   0 Yeah arrays are faster But like a lot of people I'm not using arrays (I just use vectors) because it have benifiets more than arrays (like push_back, pop_back ... etc) and you don't need to calculate the size, just use resize unlike arrays
•  » » » » » 16 months ago, # ^ |   0 Yeah! Thanks a lot for your answer! :)
 » 13 months ago, # | ← Rev. 2 →   0 For problem E :I created a 2D matrix A = { {0,1,1,1},{1,0,1,1},{1,1,0,1},{1,1,1,0} }and then A^n gives WA but A^(n-1) gives AC. Why is that ? please explain..
 » 13 months ago, # |   0 How did solutions based on Kuhn's algorithm passed in problem D? Shouldn't it get TLEd?
 » 8 months ago, # |   0 Hi. // My code give the corrects answers, but in some cases, i dont know why the result is negative. Am a beginner in Codeforces and C++. Please help me find what's wrong with my code.##########long long n; cin>>n; long long cst=(7LL+pow(10,9)),x=1,c2=0,c1=0; if(n>1){ for(unsigned int i=1;i
 » 5 months ago, # |   0 In case someone needs help with problem E, I am sharing my approach based on tracing the path of ant moving backwards from finishing point D. Approachstart with a single char D representing last position of ant which is D, string str = D, and append chars A, B, C to its left which are the possible choices for ant to reach D. After 1st step we will get 3 diff strings -- 1.AD 2.BD 3.CD now in each string and append chars A, B, C, D to strings left which are the possible char from where ant could have jumped to reach present leftmost char, but no 2 consecutive char should be equal in the string, as ant is constantly moving i.e. we have 3 chars available for each strings which are different from present leftmost char. 1.AD -> AAD (**not possible** as ant is moving constantly so 2 consecutive chars cannot be same) -> BAD -> CAD -> DAD 2.BD -> ABD -> CBD -> DBD 3.CD -> ACD -> BCD -> DCD so if we observe our answer will be those strings which has both first and last char D (as ant started from D and want to reach D at the end) and are of length n+1, length n+1 because we need to create n jumps to reach from last char from 0th char.  Code ll d = 1, a = 0, c = 0, b = 0, prev_a = 0, prev_b = 0, prev_c = 0, prev_d = 1; loop(i, 0, n){ prev_a = a, prev_b = b, prev_c = c, prev_d = d; a = ((prev_b %mod + prev_c %mod)%mod + prev_d)%mod; b = ((prev_a %mod + prev_c %mod)%mod + prev_d)%mod; c = ((prev_d %mod + prev_a %mod)%mod + prev_b)%mod; d = ((prev_a %mod + prev_b %mod)%mod + prev_c)%mod; } cout<
 » 4 months ago, # | ← Rev. 2 →   0 I keep getting wrong answer at test case 13 for E idk why