By PikMike, history, 5 weeks ago, translation, ,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir Vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all participants!

Our friends at Harbour.Space also have a message for you:

Hi Codeforces!

This summer, we want to invite you to Tech Scouts, the two-week summer camp we run from the 8th-19th of July in one of Barcelona's leading international schools, St.Paul’s.

This camp, divided into Creative and Technical tracks, is designed to lay out the foundation of knowledge for high-school students in the fields of technology, mathematics, business and design. Both tracks are taught in English.

We would love to see you guys at our camp this year — if you’re interested in joining, or if you just want to know more, just head over to the Tech Scouts website.

This camp is for anyone passionate about tech or design, so if you know someone who might be interested, be sure to let them know too!

Ps. Don’t wait too long — you still have an early bird discount, but only until May 20th

UPD: The round will contain 6 problems.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Um_nik 6 111
2 Cinro_9baka 6 207
3 Ilovebxy 6 247
4 ivan100sic 6 249
5 ainta 6 411

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 292:-18
2 Haunted_Cpp 31
3 WileE.Coyote 30:-4
4 Disappointment 27:-1
5 czasem_tak_trzeba 23
790 successful hacks and 697 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A iaeyoayao 0:01
B MesyuraTheOldDumbGoblin 0:03
C NeKrasnyj 0:07
D FlyToTheSky 0:07
E Rezwan.Arefin01 0:17
F Um_nik 0:59

•
• +124
•

 » 5 weeks ago, # | ← Rev. 2 →   0 Good luck to everyone tomorrow! Nice time by the way!
 » 5 weeks ago, # |   +11 Why does PikMike sets problem mostly for educational rounds only ???
 » 5 weeks ago, # |   -17 Hope to we all have a good luck , with no hacked submissions!
 » 5 weeks ago, # |   -19 It'll be held at 22:35. I've never stayed up late for a contest XD.
 » 5 weeks ago, # |   +1 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 5 weeks ago, # |   +1 Good Luck Everyone :)
 » 5 weeks ago, # |   -9 what do u mean by "great systems Polygon" ? " thanks to Mike MikeMirzayanov Mirzayanov for <> and Codeforces."
 » 5 weeks ago, # |   +42 Give me that +12 rate change:)
•  » » 5 weeks ago, # ^ |   0 How about +12 up votes?
•  » » 5 weeks ago, # ^ |   +4 Granted.... Oops -83
•  » » » 5 weeks ago, # ^ |   -9 Get to expert then we will talk about it/ until then shut up and keep my rate change out it Eminem after learning c++
•  » » » » 5 weeks ago, # ^ |   0 As you wish My Lord
 » 5 weeks ago, # | ← Rev. 2 →   +5 m2.codeforces shows 500:Internal Server Error. m1,m3 also not working. Please fix.
 » 5 weeks ago, # |   +23 halyavin is here.
 » 5 weeks ago, # | ← Rev. 2 →   -48 .
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +22 Hmm, I will just leave the link to one of my comments here.UPD: posting such articles or links during the contest is unacceptable behavior anyway.
•  » » 5 weeks ago, # ^ |   +37 It is bad to post it during the round. But also it is not the same problem :)
 » 5 weeks ago, # |   +19 How to solve E, are there some observations or it's an application of some algorithm?
•  » » 5 weeks ago, # ^ |   0 I was thinking it could be solved by solving System Linear Equation with Gauss Jordan with modules. But I failed in the implementation...
•  » » 5 weeks ago, # ^ |   +40 I checked x=0,1,2,3,4,5,6,7,8,9,10. And then calculated all values using Lagrange interpolation.
•  » » » 5 weeks ago, # ^ |   +3 It could be simpler. Its just check x = 0,1,2,3,4,... 10 and find the coeficients (like you did) and then eval the function over [0, Mod — 1]. AC = http://codeforces.com/contest/1155/submission/53163325
•  » » » » 5 weeks ago, # ^ |   +13 Lagrange interpolation is actually the method to calculate coefficients.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +27 A $N$ degree polynomial is uniquely determined by $N+1$ distinct evaluations. You can ask $P(0), P(1), \cdots, P(10)$ and then interpolate. Then you can find the root in $O(mod)$ by checking all numbers in $[0, mod - 1]$.
•  » » » 5 weeks ago, # ^ |   +3 So, the interpolation would return the coefficients and then we bruteforce over all the values for the function we've found?
•  » » » 5 weeks ago, # ^ |   0 Technically $O(mod \log mod)$ for me bcz my interpolation involved finding the inverse of each $n$ with $0 •  » » » » 5 weeks ago, # ^ | +6 My interpolation required inverse of numbers in$[0, 11]$, which you can precalculate in$O(1)$using$inv(i) \equiv -(M / i)\cdot inv(M \mod i) \pmod M$: Codeint c[N+1]; // initially c[i] = P(i) void init() { for(int i = 0; i < n; ++i) for(int j = n; j > i; --j) c[j] -= c[j - 1]; } int eval(int x) { int m = 1, y = 0; for(int i = 0; i <= n; ++i) { y += c[i] * m; m *= (x - i) / (i + 1); } return y; } // add mods^  •  » » » » 5 weeks ago, # ^ | +6 Calculating inverses of all elements in modular ring can be done in$O(mod)$. Refer last section of https://cp-algorithms.com/algebra/module-inverse.html . •  » » 5 weeks ago, # ^ | ← Rev. 2 → +15 Just ask for$f(0), f(1), ..., f(49)$, pray there is some recurrence like$f(i) = \sum_{j} a_j \times f(i - j)$. and find it using Berlekamp-Massey. Then you can calculate all$f(i)$for$0 \le i < MOD$. The existance is proved here. •  » » 5 weeks ago, # ^ | +19 I used little Bézout's theorem. For any$a$we have$f(x) = g_1(x) \cdot (x - a) + f(a)$, where$g_1(x)$is a polynomial with less degree. So if we know$f(x)$and we have asked for$f(a)$before we can calculate$g_1(x)$.You can continue, say$g_1(x) = g_2(x) \cdot (x - b) + g_1(b)$, and so on, remembering the remainder on each step. After a few iterations (about$10$)$g_i$will become a constant function. If we know$g_{i + 1}(x)$we can easily find$g_i(x)$. So, since we know that for big enough$i$:$g_i$is constant, for any$x$we can caluclate$f(x)$by going backwards through these functions.Now just iterate through all$0 \le x < 10^6 + 3$and check if$f(x)$is zero.  » 5 weeks ago, # | +16 What is the solution to F? •  » » 5 weeks ago, # ^ | -32 •  » » » 5 weeks ago, # ^ | +16 It's "minimal", not "minimum". "minimum" is NP-hard, hence the limit. •  » » » » 5 weeks ago, # ^ | +1 Sorry for my english, but what is the difference between "minimal" and "minimum" in this case?Thank you! •  » » » » » 5 weeks ago, # ^ | ← Rev. 3 → +13 It is a mathematical notation. For set$S$, a subset$X \subset S$is "minimal" set satisfying certain property if there exists no other subset$Y \subset S$such that$|Y| < |X|$,$Y \subset X$, and satisfies such property.For set$S$, a subset$X \subset S$is "minimum" set satisfying certain property if there exists no other subset$Y \subset S$such that$|Y| < |X|$and satisfies such property. •  » » 5 weeks ago, # ^ | ← Rev. 2 → +23 DP on subset of vertices. Note that 2-edge-connected graph admits an ear decomposition. Thus, the base case is where the graph admits a Hamiltonian cycle. For the inductive case, you split the set into two parts: One for the new ear, other for the minimum biconnected subgraph of remaining sets. The time complexity is$O(3^N \times N^2)$because you enumerate subsets for each subset. My code is pretty slow, and I think it could be done faster, something like$O(3^N \times N)$. •  » » » 5 weeks ago, # ^ | ← Rev. 2 → +26 I think you can precalc bunch of stuff in$O(2^{n} poly(n))$and then get$O(3^{n} \cdot \frac{n^{2}}{64})$. My solution from the contest also works in$O(3^{n} n^{2} + 2^{n} n^{3})$, but the constant factor in first part is very small ($1/54$easily), I even think that precalc is the slowest part of my solution (I store all the paths for some reason, so it is$2^{n} n^{3}$pushbacks, you don't need it actually). •  » » 5 weeks ago, # ^ | +29 Randomized solution also works. If we fix the DFS tree of the graph, it is easy to choose minimum number of back-edges to make the graph bi-connected. (It can be done by simple dfs+greedy, in O(N+M)) So, we run the following iteration as many as can: 1. make a random DFS tree of the graph. 2. run greedy on that DFS tree to find minimum edge set. then print the best solution. •  » » 5 weeks ago, # ^ | 0 Here's my solution:For each subset of the set of vertices, try finding a simple cycle which contains only those vertices, this can be done in$O(n^3 2^n)$. If there is a Hamiltonian cycle, then it is the solution. Otherwise, pray that there aren't many subsets of the set of vertices such that they form a cycle, and then do DP on them: I assumed that the solution will always be a union of such cycles. (I didn't prove it but it makes sense). The complexity of this part is$O(\frac{n^2 2^n C}{32})$where$C$is the number of cycles.Code: 53156325  » 5 weeks ago, # | +12 Problem D case 5?  » 5 weeks ago, # | 0 Any hints for E? •  » » 5 weeks ago, # ^ | +2 Finding the constants of the polynomial by solving linear equations (notice or google that 10^6+3 is a prime so it forms a field Zp) and then brute forcing on the polynomial as the degree is <=10 .  » 5 weeks ago, # | 0 How to solve D ? •  » » 5 weeks ago, # ^ | ← Rev. 2 → +9 dp[i][0..2] mean haven't multiplied by x, have been multiplied by x, have multiplied x. So we have follow:dp[i][0]=max(dp[i-1][0]+a[i],a[i])dp[i][1]=max({dp[i-1][0]+a[i]*x,dp[i-1][1]+a[i]*x,a[i]*x})dp[i][2]=max({dp[i-1][1]+a[i],dp[i-1][2]+a[i],a[i]})the answer will equal to one of the dp array •  » » » 5 weeks ago, # ^ | ← Rev. 2 → 0 I think the last transition is wrong. In dp[i][2] you can't start a new segment. EDIT: Well, it is correct I guess, as the problem allows not multiplying x at all. But it is wrong for the dp definition. •  » » » » 5 weeks ago, # ^ | ← Rev. 3 → 0 You are right, but the value won't be wrong because the dp[i][2] value was equal to dp[i][0] at that time •  » » » » » 4 weeks ago, # ^ | 0 I am looking for advice, how do you come up with states for harder dp problems •  » » » 5 weeks ago, # ^ | 0 Brilliant approach, thanks! It helps me a lot. •  » » » 5 weeks ago, # ^ | 0 I let dp[i][j][k] mean now consider the i-th number if j=1 that the i-th number doesn't * x if j=0 that the i-th number *x if k=1 that there is an area *x before if k=0 that there isn't an area*x before so we can find that dp[i][0][0]=max(dp[i-1][0][0]+a[i]*x,max(dp[i-1][1][0]+a[i]*x,a[i]*x)); dp[i][1][0]=max(dp[i-1][1][0]+a[i],a[i]); dp[i][1][1]=max(dp[i-1][0][0]+a[i],dp[i-1][1][1]+a[i]);  •  » » 5 weeks ago, # ^ | ← Rev. 2 → +8 My Segment Tree solution was overkill, as it was a DP problem. Because I'm jobless and narcissistic, I'm explaining my solution anyway. Given numbers$a[0] .... a[n-1]$, let us calculate$upto[i]$and$from[i]$which would give you the maximum sum of the subarray the ends at position$i$, and starts from position$i$respectively.$upto[i] = max(0, a[i], upto[i-1] + a[i])from[i] = max(0, a[i], from[i+1] + a[i])$The first observation is that if we decide to apply the operation from$a[L] ... a[R]$, and it was optimal then$answer = upto[L-1] + (a[L] + ... a[R]) * x + from[R+1]$Let us define a function$ f(l, r) = upto[l] + (a[l+1] + a[l+2] + ... + a[r-1]) * x + from[r]$. The required answer is the maximum of$f(l, r)$for$l < r$. If we attempt to solve this naively by precomputing$upto[]$and$from[]$and prefix sums, then this can be done in$O(n^2)$, which is too slow. Let us define$g_r(l) = upto[l] + (a[l+1] + .... a[r-1]) * x$. Here$f(l, r) = g_r(l) + from[r]$. Obviously$g_{r+1}(l) = g_r(l) + a[r] * x$for$l != r-1.$If we keep a segment tree that supports range-max queries and range-sum updates to represent$g_r$for different values of$r$. Initally all the values are 0. This represents$g_0$. For each r = 0 to$n-1$, do the following: calculate the maximum in the subarray right now. One possible$answer = max(g_r[0...r-1]) + upto[r]$. update the values from$0 ... r-1$by$a[r] * x$. set$g_r[r] = upto[r]$. If you get the boundary conditions right, then you have found an overkill$O(n log n)$solution. See my submission 53151609 to know more. •  » » » 5 weeks ago, # ^ | +2 My solution is exactly similar to yours.Infact i missed by C because of this tedius implementation of D •  » » » » 5 weeks ago, # ^ | 0 You have my commiserations.  » 5 weeks ago, # | 0 How to solve 4th one?My approach : Let ans = kadane(original array) If x >= 0 && all A[i]<=0 then answer is 0 If x >= 0 and all A[i] are not negative, then find subarray with max sum, multiply with x. Now ans = max(ans, kadane(modified array)) If x<0 then find subarray with most negative sum, multiply with x, Now ans = max(ans, kadane(modified array)) •  » » 5 weeks ago, # ^ | +6 I have applied the same logic ,but its failing in test case number 10. Code Link Can you please find the error. •  » » » 5 weeks ago, # ^ | ← Rev. 2 → +5 Run for this case 5 -1 -5 -2 6 -3 -5 Correct answer : 14 •  » » 5 weeks ago, # ^ | 0 DP! I passed it! But I TLE at the 3th problem •  » » 5 weeks ago, # ^ | ← Rev. 2 → +1 Try this:5 0-1 2 -6 4 -5 •  » » 5 weeks ago, # ^ | 0 When x is 0 your solution fails as you can "erase" a negative subarray by multiplying it by 0 and combine its adjacent maximum subarrays, but that negative subarray is not necessarily minimal.  » 5 weeks ago, # | ← Rev. 2 → 0 I thought$O(k! + 10^{6} + 3)$solution for problem E. Use gaussian elimination for polynomials$f(x) = \sum_{i=0}^{k} a_{i} x^{i}$for all$x$in$[0, 11]$. I was stuck at D so I couldn't implement this solution in a rest of time. Any better ideas or approaches for E? •  » » 5 weeks ago, # ^ | +8 I solved E using Lagrange Interpolation. Also I have just seen a solution with Berlekamp Massey. •  » » 5 weeks ago, # ^ | +8 I think you meant$O(K^3 + MOD)$since gauss takes$O(K^3)\$.
•  » » » 5 weeks ago, # ^ |   0 I thought unoptimized approach only during contest :(
 » 5 weeks ago, # |   +1 I'm seeking someone who debugged their problem D code after getting WA on test 10. What kind of input could be there on test 10?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 4 -1100 -100 90 -101
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +2 Try this: 5 -1 -5 -2 6 -3 -5 You are printing 9, but the answer is 14. This case lead me to DP.
•  » » » 5 weeks ago, # ^ |   0 Why did it lead to DP? What are the overlapping subproblems?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Consider longest prefix and suffix for every index by using segment tree or stuff like that. Now start a loop from i=1 to n and consider this as the ending of subarray*x that will give you optimal result . We can do the above part with segment tree as well all we need to store is: prefix excluding the current element (largest answer considering current element as last) suffix excluding the current number(largest answer considering current element as first) some number multiplied by x .So just keep on doing range update in [1,i] and keep adding x*current_number and also do point update on position i with prefix[i] Now take maximum of suffix[i] + range_query(1,i) values that will be ans
 » 5 weeks ago, # | ← Rev. 3 →   +1 Problem B.Please, can anybody show me where is the mistake in my code?And counter test if possible. https://codeforces.com/contest/1155/submission/53136294
•  » » 5 weeks ago, # ^ |   0 Can you explain to me your idea?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Let x = (n — 11) / 2 Going from the start and marking first x eights (if possible) and first x non-eights (if possible) Then one more time going from the start and the first not marked element is the answer (if 8 then YES, otherwise NO).
•  » » » » 5 weeks ago, # ^ |   0 you have a mistake because if cnt8 == 0 and s[i] == 8 then you will try to remove it with a cnt1 value. But this is a waste since obviously player 1 does not want to remove 8 values.
•  » » » » » 5 weeks ago, # ^ |   +5 Thanks. I have absolutely no idea how I could forget about this. It costs me 1.5 hours of smashing the table and rating of course. Maybe today I was tired. I do not know. Thanks...
•  » » 5 weeks ago, # ^ |   0 for (int i = 0; i < n; i++) { if (s[i] == '8' && cnt8 > 0) { s[i] = '?'; cnt8--; } else if (cnt1 > 0) { s[i] = '?'; cnt1--; } } What if s[i] == '8' but cnt8==0? If cnt1 is still positive, you will erase an 8
•  » » » 5 weeks ago, # ^ |   0 Thanks. I got it.
 » 5 weeks ago, # |   +1 Logic for Problem C: I found the difference between first two elements. Then found the least factor which is divisible by the difference. Then decided the answer on the basis of this factor. Code LinkCan u give a test case where it is failing.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 You have to have the GCD of every two consecutive differences. Test: 5 2 1 3 5 6 7 2 3 Your anwser is: Yes 1 1 Correct: No
•  » » » 5 weeks ago, # ^ |   0 Output is, YES 1 2. I don't think its failing in this case.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Thats a wrong test case, but your code is wrong.
•  » » » » 5 weeks ago, # ^ |   0 for(i=2;i
•  » » » » 5 weeks ago, # ^ |   0 your code will never check the last difference, thats your mistake
•  » » » 5 weeks ago, # ^ |   0 consecutive difference is not necessary you can have difference of first with every element and just calculate gcd of all element.rest of the logic is same...
•  » » » » 5 weeks ago, # ^ |   0 this is pretty much the same ...
•  » » 5 weeks ago, # ^ |   +1 3 2 2 8 11 2 3Correct output:YES 2 2Your code output: No
•  » » » 5 weeks ago, # ^ |   0 Thanks for the test case.
 » 5 weeks ago, # | ← Rev. 2 →   0 53163062 could any one help me with my solution on C? i don't know why i got wrong answer in 11; i think logic is fine.... help me please.. i'm stupid...
•  » » 5 weeks ago, # ^ |   0 You have declared temp as int.
•  » » » 5 weeks ago, # ^ |   0 wow you're genius thank you !!!!
 » 5 weeks ago, # |   +2
•  » » 5 weeks ago, # ^ |   0 Ну ты и петушара (translate from Russian)
 » 5 weeks ago, # |   -10 Anyone can tell me , is problem D kadane's algo problem ?
 » 5 weeks ago, # | ← Rev. 4 →   +25 I found this interesting solution, is this allowed Vovuh? The code is not visible, so how does someone hack?
•  » » 5 weeks ago, # ^ |   0 it means they will be disqualified, this has happened before
•  » » 5 weeks ago, # ^ |   +7 This is not allowed.See point no 16 of https://codeforces.com/blog/entry/456
•  » » 5 weeks ago, # ^ |   0 Can you please explain your solution of D?
•  » » » 5 weeks ago, # ^ |   0 1) don't take any 2) started subarray multiplication with x 3) multiplied some subarray already with x
•  » » 5 weeks ago, # ^ |   +1 how did it even get AC.
•  » » » 5 weeks ago, # ^ |   0 Power of #define
•  » » 5 weeks ago, # ^ |   +42 It is not allowed. The user will be disqualified from the contest.
 » 5 weeks ago, # |   0 https://codeforces.com/contest/1155/submission/53152525 Problem B Why does this give runtime error ?If I simply change the values to some letter, let's say 'a' instead of erasing a number, I stop getting runtime errors but I get TLE.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 you should will never stop with undefined behavior while(*****s[j]=='8'*******){ j++; } s.erase(s.begin()+j); ////////////////////////////////// while(******j < s.size()******* and s[j] == '8')++j;
 » 5 weeks ago, # |   0 Does anyone have test hack for D ?
•  » » 5 weeks ago, # ^ |   -7 5 -1 -5 -2 6 -3 -5Ans : 14
 » 5 weeks ago, # | ← Rev. 5 →   +9 My overkill solution 53155985 for D is using sqrt decompopsition. I divided the array into blocks and then handle two cases:1: The endpoints of the multiplied subarray lie in different blocks2: The endpoints of the multiplied subarray lie in the same blockDid anyone also solve it using this method?
 » 5 weeks ago, # |   +7 I found what looks like cheating to me.Submissions 53159161 and 53158255 which are made by different accounts are exactly the same, and submissions 53139289 and 53139670 made by the same two accounts are exactly the same except for an extra return 0; line which is commented out in one of the submissions but not the other.
•  » » 5 weeks ago, # ^ |   +3 How do you find these submissions? Are you running a script for this?
•  » » » 5 weeks ago, # ^ |   +5 I was manually looking through submissions one by one trying to find hackable ones.
•  » » 5 weeks ago, # ^ |   -11 what the moo Bessie why are you asking poor high schoolers to solve your relationship problems with my boy Farmer John when you can code the solutions yourself
 » 5 weeks ago, # |   0 I tried to solve C(alarm one). My code is as follows https://codeforces.com/contest/1155/submission/53159102 . I solved it in O(n) but still got some runtime error! PLease help
•  » » 5 weeks ago, # ^ |   0 Runtime Error is because you didnt use long long.
•  » » » 5 weeks ago, # ^ |   0 You wouldn't get a runtime error for not using long long. You would get a wrong answer when int overflows. In this case the runtime error is because he is using 2 arrays of size 300001 inside main. You should declare those outside of main.
•  » » » » 5 weeks ago, # ^ |   0 aisa kyu
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 The stack space isn't sufficient to allocate so much memory. Global space is much more so you should always declare your arrays outside of main.
•  » » » 5 weeks ago, # ^ |   0 did not help!
•  » » » » 5 weeks ago, # ^ |   0 Can you allocate that large memory in stack? I am not sure but this could be a problem.
 » 5 weeks ago, # |   0 Have a look at this and this submission .. ment intentionally hackable and there are many more of this kind
•  » » 5 weeks ago, # ^ |   0 imaginative
 » 5 weeks ago, # |   0 I'm new to codeforces, does open hacking means there will be no points for hacking?
•  » » 5 weeks ago, # ^ |   0 Yes.
•  » » » 5 weeks ago, # ^ |   0 Oh, there were quite easy hacks for D. Anyways it was still fun hacking it :)
 » 5 weeks ago, # |   +3 How to solve E?
 » 5 weeks ago, # |   +1 Can anyone offer some help as to how Gaussian elimination (and/or Lagrange interpolation) generalise to when the system of equations (and/or set of points on a polynomial curve) is taken modulo a prime, as in today's problem E?I've been trying to get my head around it but there doesn't seem to be anywhere on the internet addressing it — https://cp-algorithms.com/linear_algebra/linear-system-gauss.html for example asserts 'we can still use the described [Gaussian] algorithm' but I don't see how this follows.
•  » » 5 weeks ago, # ^ |   +8 All we use when defining Gausssian elimination and Lagrange interpolation and when proving their correctness is that we can add/subtract/multiply numbers and divide by numbers that are not zero and that these numbers follow the standard rules (e.g. distributivity). As such, these algorithms work over any [field](https://en.wikipedia.org/wiki/Field_(mathematics)), not just over the real or rational numbers. It is a well-known fact that Z/pZ with p prime is a field.
•  » » » 5 weeks ago, # ^ |   0 Ah okay — so when changing the cp-algorithms Gaussian elimination implementation for the modular system case, we can just adjust the division of a number with multiplication with that number's inverse (mod p)?
•  » » » » 5 weeks ago, # ^ |   +3 Yes, that is correct. In fact, your code may become a bit simpler because any non-zero diagonal element will do, whereas you want to choose the largest diagonal element in the floating-point case for stability.
•  » » » » » 5 weeks ago, # ^ |   0 Thanks very much — I think it's clear I need to get my head around the correctness proofs etc. better before implementing something, but once I do I'll keep that in mind :)
 » 5 weeks ago, # |   0 [PROBLEM E] I don't sure what am writing but I think 11 queries are enough for this problem. Is this right?
 » 5 weeks ago, # |   0 Spoilers:first guy:why my rate hasn't change second guy replies:the system didn't start testing first guy: but it's written final standing.third guy: why the system didn't start testing yet !.
 » 5 weeks ago, # |   -15 Problem D felt
 » 5 weeks ago, # |   +5 Please update ratings and add tutorials, can't wait.
 » 5 weeks ago, # |   +24 During the contest, my solution for problem B passed the pretests. But, during the system testing, the judge is giving "Compilation Error" as verdict. How is that even possible? Kindly look forward in the situation.
 » 5 weeks ago, # | ← Rev. 2 →   0 My solution for problem D is taking wrong answer on test 5.But i can't understand why.Can anyone help me pls?(Sorry for my bad english)53179364
•  » » 5 weeks ago, # ^ |   +1 4 -1 100 -100 90 -101 answer is 290
•  » » » 5 weeks ago, # ^ |   0 thanks for that.still i don't know how can i fix it but i understood my fault
 » 5 weeks ago, # |   +11 Thanks for the contest. I'm finally Purple Now :D
 » 5 weeks ago, # | ← Rev. 2 →   +17 I'm so confused that I was told I have to be skiped due to my solution for E 53159928 is coincides with solutions 53156214I'm sure that I just use a third party code Gaussian elimination ,the opensource code is posted in 2018/08/26.According to Rule about third-party code is changingSolutions and test generators can only use source code completely written by you, with the following two exceptions:the code was written and published/distributed before the start of the round,the code is generated using tools that were written and published/distributed before the start of the round.Except the opensource part of my solution,the left part is just two loop and the use of function,I think most of the people who pass the problem E has the familiar writing style in this part.So MikeMirzayanov and PikMike is it my fault or careless about the use of third party code?
•  » » 5 weeks ago, # ^ |   +21 Sorry.
•  » » » 5 weeks ago, # ^ |   -13 That's not your fault,you don't need to say sorry
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +27 Hesitating will be defeated!
•  » » » 5 weeks ago, # ^ |   +13 You mean resolute lead to AC ? : (
•  » » » 5 weeks ago, # ^ |   +21 Decisive will be useless
•  » » 5 weeks ago, # ^ |   +27 Such a notorious coincidence that your submissions were the same on D as well. 53150449 vs 53147765
•  » » » 5 weeks ago, # ^ |   -23 Isn't it you don't noticed that my solution of D is similar to lots of people you clever boy?If you want to say something,just do it,don't beat around the bush : )
•  » » » » 5 weeks ago, # ^ |   +37 Okay look here. You are currently complaining about getting caught while literally sharing the same code for every problem this entire contest. Just stop. a: 53128023 vs 53127195b: 53131283 vs 53129702c: 53137382 vs 53134674d and e: see above
•  » » » » » 5 weeks ago, # ^ |   -36 Oh Man,have you ever look for some other ABCD's solution is similar with mine which is wrote in c/c++,that's plenty of the similar code about the ABCD So that's your evidence that I'm a cheater? And how can I cheat other people 's solution? Why not @buxing201606 to join the judge? What you said above is just personal affront to me
•  » » » » » » 5 weeks ago, # ^ |   +33 "have you ever look for some other ABCD's solution is similar with mine which is wrote in c/c++". In fact, I have. I took the first 10 or so accepted solutions for problem C written in C++11. Even if they all implement the same idea, let's take a look at how they differ from your code. 53191694 didn't memorize the numbers (no arrays), wrote his own gcd function and also used abs for differences 53191661 wrote his own gcd function, alternated input with gcd computation (so different flow); also, arrays are 0-indexed 53191201 used stl vectors instead of arrays, treated n==1 case separately, also own custom gcd function (though here it's part of the template) 53190037 wrote their own gcd function, didn't memorize arrays, also did some weird thing to consume input once the execution was finalized (though they didn't have to) 53189796 alternates input with gcd computation, doesn't use 0 as neutral element for gcd (instead starts with the difference of first two elements); also, the output is all handled at the end of the program 53189373 alternates input with gcd computation, uses stream IO, handles all output (and some other operations I don't get) at the end of the program 53188909 custom gcd function, stream IO, stl vectors instead of arrays 53188661 custom IO, alternates input with gcd computation, doesn't use 0 as neutral element for gcd 53188393 stream IO, uses a separate array for memorizing adjacent differences, handles all output at the end of the program 53187814 custom gcd function, stream IO, separate array for memorizing adjacent differences (sort of similar to previous submission, but different flow: alternates gcd computation with computation of differences array) 53187738 custom gcd function, stream IO, alternates input with gcd computation, doesn't use 0 as neutral element of gcd 53187071 custom gcd function, stream IO, uses array for memorizing differences (sorts it too for some reason), uses an unnecessary min when computing gcd, all output is handled at the end of the program As you can see, all of these implementations differ form yours (in more than 1 aspect), even though they implement the same idea. Subtle differences WILL naturally appear in codes written by different people, even if they express the same thing.In fact, the probability that two codes are EXACTLY the same (modulo headers, indentation and variable names) is extremely low, even for a simple problem. The probability that all codes are the same for ALL problems during the contest is so small it's not even worth considering.If you want to "steal your own hat" and cheat, that's fine by me. But the fact that you then come to the blog and complain about being caught, acting innocent, is quite frankly an insult to the CF community.
•  » » » » » » » 5 weeks ago, # ^ |   -10 You can read what I said just before,I just learn some skill from the blog I said below,I don't think the header can be seemed as evidence,maybe,I say maybe,buxing201606 is also a learner from the blog I said below. That's all that I know
•  » » » » » 5 weeks ago, # ^ | ← Rev. 5 →   0 What you give us seems the true,but even if everyone don't trust me,I know I'm innocent.What you said about ABC I think it's not strong enough to prove your opinion.But,actually myself also think the solution and the writing style about the problem D is so similar. I don't know why buxing201606 has the same simplify operation about getmax function,what can I say is just where I learn this function.Once I search some solution in the web,I found this blog blog of notnight,and the simplify operatin is just modify from it.I'm a retired ACMer(retired just last year),I bet my honor as a programing competition participant to say,what I said above is all that what I know about the whole case.That's my last reply to you,no offend,best wishes in your programing competition days.
•  » » » 5 weeks ago, # ^ |   -7 I really didn't know him before, and I didn't share my code with others during the contest. The template for Gaussian elimination is copied and pasted from someone else's blog. I searched for Gaussian elimination on the search engine. The first blog is this.
•  » » » » 5 weeks ago, # ^ |   +12 Did you also copy-paste from a blog the solutions to the other 4 problems which you guys solved with the exact same code?Seriously, I don't know what you two are debating here. It's obvious that (at least) one of you cheated. It's like a kid telling you they didn't eat the cookies, with crumbles around their lips.I don't even know who you're tying to sell the story to. Mike won't take any action (as it's been shown before), I myself couldn't care less, and neither does anybody else: you are the ones who started the topic in the first place. Just let it go and save yourselves the hassle.
•  » » 4 weeks ago, # ^ |   +8 It is not a question of using third-party code. I do not have time to debate on this issue, I once again carefully looked at and studied all the arguments. My decision remains unchanged. A large number of suspicious coincidences do not leave it to be considered an accident: incredible coincidences in solutions on other problems, similar code in these programs that is not part of the third-party code. Probably, there was an unintentional leak, which is also violation. I suggest you both to change passwords and use only https in the future. Good luck.
•  » » » 4 weeks ago, # ^ |   0 Thanks，got it.
 » 5 weeks ago, # |   +28 Editorial link????
 » 5 weeks ago, # |   0 I wonder why I got AC from this random solution that I made for problem B. Can anyone explain it to me?I define F8[i] as the number of digits 8 from the 1st to the ith character.https://codeforces.com/contest/1155/submission/53148643
 » 5 weeks ago, # |   0 Can anyone tell me how to use dp in D question....? i am new to competative.. and how i recgonise that dp is use or not... is there any trick or it comes with practice... any related question to that so that i can practice.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +2
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 oh my, halyavin 292 successful hacking attempts? What?