By PikMike, history, 6 months ago, translation, In English,

Hello Codeforces!

On Apr/22/2019 17:35 (Moscow time) Educational Codeforces Round 63 (Rated for Div. 2) will start.

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

UPD: The editorial is out

 
 
 
 
  • Vote: I like it
  • +124
  • Vote: I do not like it

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Good luck to everyone tomorrow! Nice time by the way!

»
6 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Why does PikMike sets problem mostly for educational rounds only ???

»
6 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Hope to we all have a good luck , with no hacked submissions!

»
6 months ago, # |
  Vote: I like it -19 Vote: I do not like it

It'll be held at 22:35. I've never stayed up late for a contest XD.

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Good Luck Everyone :)

»
6 months ago, # |
  Vote: I like it -9 Vote: I do not like it

what do u mean by "great systems Polygon" ? " thanks to Mike MikeMirzayanov Mirzayanov for <> and Codeforces."

»
6 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Give me that +12 rate change:)

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How about +12 up votes?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Granted.... Oops -83

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      Get to expert then we will talk about it/ until then shut up and keep my rate change out it Eminem after learning c++

»
6 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

m2.codeforces shows 500:Internal Server Error. m1,m3 also not working. Please fix.

»
6 months ago, # |
  Vote: I like it +23 Vote: I do not like it

halyavin is here.

»
6 months ago, # |
Rev. 2   Vote: I like it -48 Vote: I do not like it

.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +22 Vote: I do not like it

    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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    It is bad to post it during the round. But also it is not the same problem :)

»
6 months ago, # |
  Vote: I like it +19 Vote: I do not like it

How to solve E, are there some observations or it's an application of some algorithm?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was thinking it could be solved by solving System Linear Equation with Gauss Jordan with modules. But I failed in the implementation...

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    I checked x=0,1,2,3,4,5,6,7,8,9,10. And then calculated all values using Lagrange interpolation.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +27 Vote: I do not like it

    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]$$$.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      So, the interpolation would return the coefficients and then we bruteforce over all the values for the function we've found?

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Technically $$$O(mod \log mod)$$$ for me bcz my interpolation involved finding the inverse of each $$$n$$$ with $$$0<n<mod$$$.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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$$$:

        Code
      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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 .

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it

    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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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.

»
6 months ago, # |
  Vote: I like it +16 Vote: I do not like it

What is the solution to F?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -32 Vote: I do not like it
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      It's "minimal", not "minimum". "minimum" is NP-hard, hence the limit.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Sorry for my english, but what is the difference between "minimal" and "minimum" in this case?

        Thank you!

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
          Rev. 3   Vote: I like it +13 Vote: I do not like it

          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.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +23 Vote: I do not like it

    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)$$$.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +26 Vote: I do not like it

      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).

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
6 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Problem D case 5?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for E?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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 .

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D ?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    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

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I am looking for advice, how do you come up with states for harder dp problems

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Brilliant approach, thanks! It helps me a lot.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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]);
      
  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    My Segment Tree solution was overkill, as it was a DP problem. Because I'm jobless and narcissistic, I'm explaining my solution anyway.

    1. 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.

    2. $$$upto[i] = max(0, a[i], upto[i-1] + a[i])$$$

    3. $$$from[i] = max(0, a[i], from[i+1] + a[i])$$$

    4. 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]$$$

    5. 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.

    6. Let us define $$$g_r(l) = upto[l] + (a[l+1] + .... a[r-1]) * x$$$. Here $$$f(l, r) = g_r(l) + from[r]$$$.

    7. Obviously $$$g_{r+1}(l) = g_r(l) + a[r] * x$$$ for $$$l != r-1.$$$

    8. 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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      My solution is exactly similar to yours.Infact i missed by C because of this tedius implementation of D

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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))

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I have applied the same logic ,but its failing in test case number 10. Code Link Can you please find the error.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DP! I passed it! But I TLE at the 3th problem

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Try this:

    5 0

    -1 2 -6 4 -5

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I solved E using Lagrange Interpolation. Also I have just seen a solution with Berlekamp Massey.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I think you meant $$$O(K^3 + MOD)$$$ since gauss takes $$$O(K^3)$$$.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought unoptimized approach only during contest :(

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    4 -1
    100 -100 90 -101

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    Try this:
    5 -1
    -5 -2 6 -3 -5

    You are printing 9, but the answer is 14. This case lead me to DP.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why did it lead to DP? What are the overlapping subproblems?

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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:

        1. prefix excluding the current element (largest answer considering current element as last)
        1. 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

»
6 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain to me your idea?

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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).

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          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...

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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 Link

Can u give a test case where it is failing.

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Output is, YES 1 2. I don't think its failing in this case.

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thats a wrong test case, but your code is wrong.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        for(i=2;i<n;i++) { ll diff=x[i]-x[i-1]; if(diff%factor!=0) break; } if(i==n) { cout<<"YES\n"; cout<<x[0]<<" "<<pos+1<<endl; return 0; } i will never be == to n bro...

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        your code will never check the last difference, thats your mistake

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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...

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    3 2 2 8 11 2 3

    Correct output:
    YES 2 2

    Your code output: No

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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...

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have declared temp as int.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      wow you're genius thank you !!!!

»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ну ты и петушара (translate from Russian)

»
6 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Anyone can tell me , is problem D kadane's algo problem ?

»
6 months ago, # |
Rev. 4   Vote: I like it +25 Vote: I do not like it

I found this interesting solution, is this allowed Vovuh? The code is not visible, so how does someone hack?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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;

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have test hack for D ?

»
6 months ago, # |
Rev. 5   Vote: I like it +9 Vote: I do not like it

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 blocks

2: The endpoints of the multiplied subarray lie in the same block

Did anyone also solve it using this method?

»
6 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    How do you find these submissions? Are you running a script for this?

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I was manually looking through submissions one by one trying to find hackable ones.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Runtime Error is because you didnt use long long.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        aisa kyu

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      did not help!

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you allocate that large memory in stack? I am not sure but this could be a problem.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Have a look at this and this submission .. ment intentionally hackable and there are many more of this kind

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm new to codeforces, does open hacking means there will be no points for hacking?

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve E?

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)?

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 :)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

[PROBLEM E] I don't sure what am writing but I think 11 queries are enough for this problem. Is this right?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 !.

»
6 months ago, # |
  Vote: I like it -15 Vote: I do not like it

 Problem D felt

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Please update ratings and add tutorials, can't wait.

»
6 months ago, # |
  Vote: I like it +24 Vote: I do not like it

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.

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    4 -1 100 -100 90 -101

    answer is 290

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks for that.still i don't know how can i fix it but i understood my fault

»
6 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Thanks for the contest. I'm finally Purple Now :D

»
6 months ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

I'm so confused that I was told I have to be skiped due to my solution for E 53159928 is coincides with solutions 53156214

I'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 changing

Solutions 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?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Sorry.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      That's not your fault,you don't need to say sorry

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +27 Vote: I do not like it

    Hesitating will be defeated!

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    Such a notorious coincidence that your submissions were the same on D as well. 53150449 vs 53147765

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

      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 : )

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +37 Vote: I do not like it

        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 53127195

        b: 53131283 vs 53129702

        c: 53137382 vs 53134674

        d and e: see above

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it -36 Vote: I do not like it

          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

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it +33 Vote: I do not like it

            "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.

            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
                Vote: I like it -10 Vote: I do not like it

              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

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
          Rev. 5   Vote: I like it 0 Vote: I do not like it

          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.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

»
6 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Editorial link????

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

oh my, halyavin 292 successful hacking attempts? What?