By awoo, history, 3 weeks ago, translation, In English

Hello Codeforces!

On Jul/14/2021 17:35 (Moscow time) Educational Codeforces Round 111 (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 or 7 problems and 2 hours to solve them.

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

Good luck to all the participants!

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

Hey, Codeforces!

From Barcelona to Bangkok, we are officially opening our new campus in August.

As some of you might know, Harbour.Space University has partnered with the University of the Thai Chamber of Commerce, Bangkok to offer exceptional tech specialists the opportunity to study in one of the most dynamic and vibrant cities in the world.

To celebrate our launch, we have scholarships available for our tech bachelor’s and master’s programmes including Data Science, Cyber Security, Front-end Development and Computer Science.

Codeforces and Harbour.Space

Scholarship Requirements:

  • Proficient level of English
  • CV
  • Maths and Computer Science Test
  • Diploma and transcript of the highest attained education level

For the Front-end Development Master’s programme, applicants will have to submit a challenge.

We are always happy to see Codeforces members join the Harbour.Space family. Get a chance to learn from the best in the field and kickstart your career and apply now to one of the following programmes:

Keep in touch and follow us on LinkedIn for more scholarship opportunities. And follow us on Instagram to evidence student life, events, and success stories from our apprenticeship program students.

Good luck on your round, and see you next time!

Harbour.Space University

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 jiangly 6 136
2 neal 6 177
3 zxcgod 6 186
4 Bench0310 6 211
5 Geothermal 6 212

289 successful hacks and 677 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Geothermal 0:00
B Geothermal 0:02
C TheScrasse 0:07
D jiangly 0:27
E Andreasyan 0:18
F TheOneYouWant 0:40

UPD: Editorial is out

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

»
3 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

Hope to be pupil after this round!

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

    solve A and B fast(miserable part is I saw 'how' in place of 'hope', then gave advice only to get downvotes lol)

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

    get high rank, easy-peasy answer

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why is this so true?

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

      Say hello from Hanoi :P

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

      LOL.... some people start off as pupil and later struggle at NewBie. I ain't one of them i started of as Newbie and struggling at newbie xD.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i came down from 1321 to pick u up lets go to pupil together , ps: u wont believe me but rating graph wont lie

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

    Why there is a huuuge phase of solution hacks for 12 hrs and after 3 hrs from its finish STILL no rating changes published? I'm not sure the whole process of calcing rating changes takes more than 3 hrs itself.

    edit: 7 HOURS already passed from solution hacks phase finish and still nothing... why do we have to wait soo long

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      exactly man, not sure what's going on

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

        and this long delay happens literally every time a div3 round occurs or a rated for div2 only, very dissapointing

»
3 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it

There is a long queue in problem submission rn. I hope this won't happen in tomorrow's contest.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

very nice number, I hope there will be a good round with nice problems.

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

After so long time educational round hope learn something new from it

»
3 weeks ago, # |
  Vote: I like it +176 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

I hope to finally be expert after this round :)

»
3 weeks ago, # |
Rev. 3   Vote: I like it +31 Vote: I do not like it

Educational Codeforces Round 7

Spoiler
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Hoping for a good contest :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

All the best to everyone :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope the best to everyone GLHF!!!

»
3 weeks ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

Love Educational rounds very much!! Hope to go ++.

UPD : wth guys, why these downvotes lmao? people dont like educational rounds?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yup,aiming for pupil rn but it might take a while.

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

      As a guy who became pupil one round before (and in this one I got 1800th place) I suppose you should check some books in parallel with practice. I was just like: "wow stop, it's is how it works???" when I understood how time complexity is being calculated.

»
3 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

I hope everyone can rate growth.

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

Hoping for a Good and Fair Contest. Hackers are all set to hack :(

»
3 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

I hope to become specialist after next round.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

ALL THE BEST GUYS.

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

I wish problem rating updated soon to judge my level, Educational round problem rating updated too late many times :), But Educational round is interesting.

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

    I think that's only because educational round is extend-ICPC rule, which means it will have a 12 hours open hack.

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

Hey guys, I received a report :"Rating changes for the last round are temporarily rolled back. They will be returned soon." . What does it mean???

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

    This is a very regular thing in Codeforces. Means Codeforces have a daily maintain on its datebase.

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Hope to be pupil after this round!

»
3 weeks ago, # |
  Vote: I like it -22 Vote: I do not like it
Spoiler
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to get as much positive delta as this round number(also very symbolic) is. Good luck every one!

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

There are more than 20K+ participants registered for this contest but why the upvote is only 222 at least everyone upvotes the contest.

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

    I personally think the post should be upvoted/downvoted after the contest has ended depending on the quality of problems and/or any issues faced...

»
3 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

how to be specialist after this round

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

all the best to all

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

HOPEFORCES it is.

»
3 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Tesla is exited!

»
3 weeks ago, # |
Rev. 2   Vote: I like it -71 Vote: I do not like it

Can I get some down votes please !!

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

111th Educational Round

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest of beautiful arrays and numbers!

»
3 weeks ago, # |
Rev. 2   Vote: I like it +156 Vote: I do not like it

terrible difficulty gap.

Update after the contest:E is easier than C imo

»
3 weeks ago, # |
  Vote: I like it +45 Vote: I do not like it

Pupils are unable to solve C.

Masters are unable to solve C.

Perfectly balanced as all things should be.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -70 Vote: I do not like it

    can u explain the problem to me...if all subarray is good for tst cs 1 then ans should 4C1+4C2+4C3+4C4 =15

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

      we should not discuss things when contest is running atleast wait for contest to end

»
3 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

I'm indeed educated

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

my hopes of being specialist have been shattered ;-;

»
3 weeks ago, # |
  Vote: I like it -53 Vote: I do not like it

can u someone the problem to me...if all subarray is good for tst cs 1 then ans should 4C1+4C2+4C3+4C4 =15

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

    that's not correct way of calculating total number of subarrays

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    total number of subarrays of a specific length let say k = n-k+1; for example subarrays of length 1 = n-1+1 = n; subarrays of length 2 = n-2+1=n-1; this way subarrays are calculated

»
3 weeks ago, # |
  Vote: I like it -74 Vote: I do not like it

Amazing contest! Enjoyed it!

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

The gap between B and C is so terrible that I spent an hour to do it :(

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

    at least you solved it

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

    How you solved C?

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 3   Vote: I like it +7 Vote: I do not like it

      Key observation you had to make is that for a subarray to be good, the size is very limited, I think the size can be up to 4.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      My thinking was as follows: In general an array is good if it has no monotonic subsequence of length 3 or more.

      Based on some case analysis I think you can just check all subarrays of length 3 or 4 and count the good ones.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Wow, very clever solution!! I just realised this observation.

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

        How do you notice such cases? Asking this because it's not that obvious.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The best advice I can give is, solve a lot of problems to develop your intuition.

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

        I have never felt more stupid. Really I feel ashamed.

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

        Yeah Same here!! I used the same concept!

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      in a subarray if u find 3 elements such that a[i]<=a[j]<=a[k] or a[i]>=a[j]>=a[k] if i<j<k then that subarray is not good so now solve the problem as the number of subarrays which doesnt have the above condition u can check my submission for code

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

      Every sub-array of size > 4 has atleast one bad triple.
      So only need to check subarrays upto size 4.

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

        can you please prove it!

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

          It was just an observation.
          In contest, I have tried several examples and came out at it.
          But I can try for the proof -
          For not having a bad triple, consecutive elements of sub-array should be in this pattern -
          1.) Increasing -> Decreasing -> Inc. -> Dec. -> ... & so on.
          OR
          2.) Decreasing -> Increasing -> Dec. -> Inc. -> ... & so on.
          Now if we consider that 1st case (Inc — Dec — Inc — ...) :-
          Suppose {a,b,c,d} is good subarray & follow 1st case, then -
          b>a , c<b , d>c
          Here if You observe 'd' can't be the greatest of these four because if it is greatest then a<b<d will not make this subarray good. It means there is atleast one element which is greater than 'd' before it.
          Now if we add 5th element in subarray, let's say 'e' , then by the pattern of case — 1, e should be less than d i.e., e<d.
          And we have proved that 'd' is not greatest so there is one element that is > d and d>e. So sub-array can't be good because (that element) > d > e. ​ Similarly it can be proved for pattern of case-2.

          Sorry for bad english !!

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

            Thank you very much can anyone please give an intuition why the sequence should be monotonic for being bad. why cant it be zigag. thanks in advance :)

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I'll just drop a hint. Think of a value-index pair as a point in an x-y plane, and try to plot some points and calculate the manhattan distances, I think you'll come up with the proof pretty easily!

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      I think the size of the subarray can't be up to more than 4. But during the contest I didn't prove it but just assume that it is right, then I solved it...

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

      Consider a good subarray... Take the leftmost point in it, call it $$$p$$$... Consider three possible positions:

      • $$$q$$$ such that $$$x_p=x_q$$$. If there is another point $$$r$$$ with the same propertie, $$$(p,q,r)$$$ is a bad triple

      • $$$q$$$ such that $$$x_q > x_p$$$. If there is another point $$$r$$$ with the same propertie, or $$$q$$$ it's inside the rectangle with opposite vertexs $$$p-r$$$, or $$$r$$$ it's inside the rectangle with opposite vertex $$$p-q$$$, in both case $$$(p,q,r)$$$ is a bad triple

      • $$$q$$$ such that $$$x_q < x_p$$$. If there is another point $$$r$$$ with the same propertie with an analogous procedure we can conclude that the triple $$$(p,q,r)$$$ is a bad triple.

      So we have at most one point of each kind, so the lenght of a good subarray is at most $$$4$$$

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

    I wish that happened to me. I took an hour on B because I forgot to add one to my solution at the end and did C in 12 minutes ;-;

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Gotta be one of the most unbalanced problemsets

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Really cool problem E!!! But my 122504290 takes 2s and 166MB so I wonder if it is the intended solution.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how to calculate if the length is valid using masks only? my solution tle as I use the index & the masks which will of course tle :) (mle before tle) :D https://codeforces.cc/contest/1550/submission/122504948

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Basically we maintain only those masks which can be updated at the present instant. That is, we only keep those un-updated masks which are 1 bit different than the already updated masks. Complexity of my sol is $$$O(2^{k}kLOG)$$$

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

    My idea for E, Firstly binary search the answer. Precalculate each mask having 1 bit,2 bit, 3 bit,4 bit set separately.

    For each index precalculate up to how much it can be extended to the left for each alphabet. Now suppose we want to check whether $$$len$$$ is possible. We will find the answer for each mask in increasing order of a number of bit set (which we have precalculated earlier). $$$dp[mask]$$$ will store the lowest index from the left where all the set bit of this mask has a length of $$$len$$$. Now if we have mask where $$$kth$$$ bit is set, we want the $$$kth$$$ alphabet to be the last alphabet to have a contagious length $$$len$$$. we already know dp[mask^k] ,

    if this is possible we can find the first index after dp[mask^k] where $$$len$$$ of alphabet $$$k$$$ is possible, this can be easily found using lower_bound with some precomputation of each alphabet, in this way $$$dp[mask]$$$ will be the minimum answer of all the bit set in mask. And finally if $$$dp[(1«k)-1]$$$ has a index then it is possible otherwise not. My complexity is $$$O(k*(2^{k})*log(n)*log(n))$$$ but passes in 1107 ms.

»
3 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

May be today C is the hardest C for some recent educational !

»
3 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

I didn`t want to write till end, but this is really speedforces. Pretty big difficulty gap between C and D. I think it is bigger than it should. But still, thanks for the round. Waiting for editorial.

»
3 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

When you realised C was just about one DAMN observation — that you need to check only subarrays of size 3 and 4.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why ??

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      in a subarray if u find 3 elements such that a[i]<=a[j]<=a[k] or a[i]>=a[j]>=a[k] if i<j<k then that subarray is not good so now all subarrays of size 1 and 2 are good so now we have to just check it for 3 and 4

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

      Three indexes is a bad triple if arr[i] <= arr[j] <= arr[k] or arr[i] >= arr[j] >= arr[k] and i < j < k.
      min(Longest Non-decreasing Subsequence, Longest Non-increasing Subsequence) of every array of length 5 is >= 3. So, every array of length 5 or more is automatically bad

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

    When you realised C was just about one DAMN observation — that you need to check only subarrays of size 3 and 4.

    What if someone didn't make this particular observation and just implemented checking subarrays of size 3, 4, 5, 6, 7, 8 and so on in the most straightforward fashion? Their solution would always bail out on subarray of size 5 anyway (so sizes of 6, 7, 8 won't be tested) and thus avoid TLE. Submission 122458692 is a very good example of this.

    When trying to hack various accepted solutions for problem C, I noticed that the opportunities to TLE them are very much limited. Moral of this story: don't give up even if you missed an important observation. Your "silly" bruteforce solution with multiple nested loops may actually have $$$O(N)$$$ time complexity, just because the observation that you failed to notice still benefits you nevertheless.

»
3 weeks ago, # |
Rev. 2   Vote: I like it +51 Vote: I do not like it

Solution of F -
Lets create a graph with edge from $$$i$$$ to $$$j$$$ with cost $$$|d - |a_i - a_j||$$$. Let's define the cost of a path as max edge weight along the path. Then minimum $$$k$$$ required to go from $$$s$$$ to $$$i$$$ is path with minimum possible cost from $$$s$$$ to $$$i$$$. This graph has $$$O(n^2)$$$ edges.

Let $$$i , j$$$ be the two stones and $$$a_j - a_i >= d$$$. Then instead of jumping from $$$a_{i-1}$$$ to $$$a_{j+1}$$$ its always better to go along $$$a_{i-1}$$$ to $$$a_{j}$$$ to $$$a_{i}$$$ to $$$a_{j+1}$$$. So lets not add $$$i-1$$$ to $$$j+1$$$ edge.

Let $$$i,j$$$ be the two stones and $$$a_j - a_i <= d$$$. Then instead of jumping from $$$a_{i+1}$$$ to $$$a_{j-1}$$$ its always better to go along $$$a_{i+1}$$$ to $$$a_{j}$$$ to $$$a_{i}$$$ to $$$a_{j-1}$$$. So lets not add $$$i+1$$$ to $$$j-1$$$ edge.

Now reduced graph has $$$O(n)$$$ edges.

To answer queries we can process offline in increasing order of k and maintaining connected components such that the cost to reach from one node to another in the same component is atmax k.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In your solution 122498108 can you explain why you only need R = 1 and not any larger value of R? I can see that for all examples of using those edges one can connect the whole graph but I can't find a proof or good explanation as to why. Thank you.

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

      My first submission had R=2. Later on, I submitted R=3,4 at last R=1 as well.
      I didn't prove rigorously for R=1 and was expecting WA and later on hack. But awoo did stress tests and this submission did pass them.
      Edges in my submissions may not be sufficient if it's a poor implementation but the idea remains the same.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i used dp for problem A.Does anyone have a better idea for problem A? And i want to ask more about the solution to problem C. thanks a lot !

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

    The solution for A can actually be calculated using arithmetic sequence and is simply

    ans = sqrt(s-1)+1
    
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yeah, this solution is much faster than dp and greedy, but i dont want to spend that much time to look for this formula during the round.

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

        Technically, that is basic maths, if observe enough, you can see that in a minute or so.

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

    I believe, that greedy works correctly, like dp. At least, my solution for A is greedy. You can check it 122453650

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought about odd numbers, but I was not able to code,

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

    Main fact that i used for promlem C is that good array cant be larger than 4. So you can calc good subarrays of length 1,2,3,4 in O(N)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      really? I thought of it as a 2 pointer problem and created 3 such cases: (let say i < j < k) - Case1: ai <= aj <= ak or ak <= aj <= ai - Case2: 2(i — j) = |aj — ai| + |ak — ai| — |ak — aj| - Case3: 2(j — k) =-|aj — ai| + |ak — ai| + |ak — aj|

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

How to solve D ? I thoutht like this.

First fix a vertex. For convenience lets fix 1. and lets assume we are going to give the value 'x' to it. l <= x <= r.

Then for each vertex either give 0 or 1. If it is one, the value of the that node is i — x + 1, else it is i + x — 1.

Then how to find the number of values satisfying the above condition that the value of the node is l <= x <= r.

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

    Well there are multiple steps, but the first crucial observation you have to make is that the final array will be in a form of a_i = i+k or i-k (k is a constant positive integer). So you have to figure out a way to loop through the possible k values. The next step is that you realize for most k, the number of ways of arranging an excellent array will be simply nC(n/2) for even numbers and for odd numbers, if we let x = (n+1)/2, and y = n — (n+1)/2, then it will nCx+nCy. So if you somehow reduce the range of k you have to calculate, then you can simply naively loop through the rest of the range, which will result in O(n) solution.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How is the number of ways of arranging will be nCn/2 why exactly only n/2 elements can have i+k / i-k? And could you elaborate the part why we need to do separately for even and odd part ?

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

        Let x be the number of a_i = i+k, and y be the number of a_i = i-k, then it is quite obvious that x+y = n. Also from this simple setup, we can actually calculate the value of F(a). When we choose one of x numbers and one of y numbers, it contributes 1 to F(a) (because a_i+a_j = (i+k)+(j-k)=i+j), so it is basically going to be F(a) = x*y = x*(n-x), and we want to maximize this value. Simple calculus tells us that this function is at maximum when x is closest to the value n/2, so for even it is just x=y=n/2, whereas for odd numbers, n/2 is not an integer, so we have to resort to (n-1)/2 and (n+1)/2. From this basic analysis using calculus, it is clear that we have to choose n/2 numbers out of the array to have i+k, and the rest to be i-k. Thus, nC(n/2) (n:even) or nC((n-1)/2) + nC((n+1)/2) (n:odd)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But there can be cases when for some k's you can't choose nC(n/2). For example when l=4 and k=3 for i's up to i = 7 there couldn't be a[i]-3 in array, so it will be at list (n-6)C(n/2) and there could be the same issue with r value and last elements. So you need to find k's not effected by this — they are -lim <= k <= lim, where lim = min(max(0, r-n), max(0, 1-l)) and for every other you should count number of elements excluded from change and find (n-ex_l-ex_r)C(n/2-ex_r) and (n-ex_l-ex_r)C(n/2+1-ex_r). Is it right? If so, how to do it quick?

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

        The key is that there are only O(n) possible situations where you have to manually calculate the value, so you don't really have to calculate them quick. And as you have mentioned, for the values 1<=k<=lim (k being negative would lead to counting the same cases twice since a_i = i- k is essentially a_i = i+ (-k)), you can simply multiply lim to the formula nC(n/2) for even and vice versa. Also, there is an intuitive way to think about why there would be only O(n) brute force cases: When k increases, the number of values in the array that have to be a_i = i+k or a_i = i-k will strictly increase because more values will be out of bounds (a_i = i+k or i-k) and since the size of the array is O(n), the number of brute force cases will also be O(n)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why such and only such arrays ($$$a_i = i \pm k$$$) are excellent?

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

        Let's say there are offsets, a and b such that for some indices i,j of the array, a_i = i+a, a_j = i+b. Then, in order for a_i and a_j to contribute to F(a) (since we want to maximize F(a)), a_i +a_j = i+j + (a+b) = i+j, so this would only occur when a+b = 0, so a = -b. We can think that a and b are "compatible" in this case and it is obvious that only compatible pairs would contribute to the function F(a). Having values that have different absolute values would decrease the number of "compatible" pairs, since they can be only compatible if and only if the other offset has the same absolute value and is negative. Hence, only when we have two offsets (k, -k) that are compatible the F(a) can be maximized. Formally, I think you could use some sort of exchange argument, but intuitively this is what I came up with during contest

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 3   Vote: I like it +5 Vote: I do not like it

      @Bungmint Congrats on solving D during the contest. Had the right idea at the contest but it took me 2 days (after work but still) to complete it :-) Amazing how the top performers do it in 15-20 minutes.

»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Missed E by just 3 min :(

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please I need hints for problem B

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the hint of problem b is an observation about how the values a and b affect the final answer. Can we say that no matter how we slice the contribution of a in the answer will be same. Now try to think how the value of b affects the answer and what happens when it goes negative.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If b is negative/zero then we need to count min number of 0 or 1 segment and then min(1,0) will be counted as sum of segments and the max(1,0) as one segment will be added to the sum.Then sum will be the ans.

      For positive just count one by one. Am i right?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Think of the case where b<0, you would want to minimize the number of moves you take. Id b>0, then you would want to maximize the moves.

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

I hate green color I love gray color thanks codeforces.

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

This contest is an example of perfect Cf contest. Problems were not direct and required some amount of thinking and there was no sudden increase in difficulty(in case of B and C). Simply loved the contest.

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

Lets LIS be Longest Non-decreasing Subsequence and LDS be Longest Non-increasing Subsequence. Lets F(arr) = max(LIS(arr), LDS(arr)). Whats the minimum F(arr) we can get for array of length N?

Its question from selection round in Summer Computer School (Round is already over), but because its related for todays C, I think I can ask here

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

    I think it's $$$\lceil \sqrt{N} \rceil$$$ as Dilworth's theorem gives a lower bound, and it can be easily constructed by grouping elements in an interval of $$$[i\sqrt{N},(i+1)\sqrt{N})$$$ in increasing order and then sort the groups in decreasing order.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do B? Any short way?

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

    If b>=0 , then just pick every element one at a time to maximize points.
    Else if b<0 , then one-by-one pick continous substrings with ( value != starting value(str[0]) ) and then pick remaining substring in one move.
    Reason for picking 2nd group for b<0 :- Because group of elements which is not equal to first element will always 1 less than or equal to other group. It can't be more than other group. So value of b which is (-)ive will be added less no. of times.
    You can check this — 122468733

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What I tried to do instead was count if we had more zeros or ones for the case when b<0. If we had more ones I removed all zeros according to there length and added it to result and at last concatenated all ones and added to result and vice versa if more zeros were there.

      This didn't work any idea why ? My submission — https://codeforces.cc/contest/1550/submission/122498847

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It won't work for 10001 case i got it, from your solution. Thanks.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Instead of counting no. of zeros and ones, count no. of max. length contiguous sub-strings of 0's and 1's because You can remove whole sub-string with same elements in one move.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

my first contest .. so can anyone tell when rating comes ??

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve D?

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

    I have a solution for even numbers, so I didn't pass the tests, but I'm sure it's almost complete solution. Firstly notice that in order for the given formula to be correct, meaning $$$a_i + a_j = i + j$$$, integers $$$a_i$$$ and $$$a_j$$$ should be of form $$$i + k$$$ and $$$j - k$$$. So for example $$$a_5 + a_3 = 5 + 3$$$ holds for $$$a = 7$$$ and $$$b = 1$$$, which is the same as saying $$$a = 5 + 2$$$ and $$$b = 3 - 2$$$.

    So we can notice that we can traverse every $$$i$$$ from 1 to infinity, but the constraints are a bit too large for this. However, we can also notice that we can add or subtract any number between 1 and $$$min(1 - l, r - n)$$$ to each of the numbers without leaving the bounds. We can clearly see that subtracting any of the value in these bounds won't exceed $$$l$$$ nor $$$r$$$.

    So this means that there are exactly $$${{min(1 - l, r - n)}\choose{n/2}} + x$$$ ways where x represents the number of ways when we can't choose two options for every single integer. This however is easily solvable, because you can notice that if for some $$$p$$$, $$$a_k + p > r$$$, then we can guarantee that $$$a_k + (p + 1) > r$$$ and $$$a_k - 1 + (p + 1) > r$$$, meaning $$$a_{k-1} + (p + 1) > r$$$. Similar statement holds for $$$q$$$ for which $$$a_k - q < l$$$. So just find the border value between these two cases (select all and select only some). Once you find the edge value it's easy to notice that you can bruteforce every value $$$\geq p$$$ as there are at most $$$n$$$ such values. Hope this helps.

    The problem I encountered is bruteforcing for odd $$$n$$$, so this solution fails on the last and first number of first test, but solves the second and third. I'd appreciate if somebody provides a workaround for this. Thanks.

    EDIT: I see I made a mistake which made the explanation sound poor.

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

      For odd n you have to consider cases: you add to $$$(n-1)/2$$$ numbers and subtract from $$$(n+1)/2$$$ numbers or you add to $$$(n+1)/2$$$ numbers and subtract from $$$(n-1)/2$$$ numbers.

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

        I'm fully aware of that, but I fail to implement it :P I don't know why, but I still keep getting 5, 6, or 3 as the answer to the first case. IDK, my implementation skill is probably bad or I'm crazy. Thanks for the confirmation though. :)

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +7 Vote: I do not like it
»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hello, I wasn't able to solve C, but while thinking on it's solution , I stumbled on a different problem.

How to find the next kth larger number in an array for an index i?

Can someone tell me how to solve this in $$$O(n)$$$?

I think a monotonic stack can be used, but I am not sure about the implementation.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is the k static or can be changed for every query?

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

    That is really not required for the problem. If you notice no subarray of size greater than equal to 5 can be good, as there will always be at least 3 non-decreasing or 3 non-increasing elements. Sadly I realized it so late that I couldn't implement it during the contest.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      omg thank you, I spent 1 hour and a half thinking about C and I didn't realize it, LOL

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For an index $$$i$$$,

      Let $$$j>i$$$

      So, for all $$$j$$$ such that $$$a[j]>a[i]$$$, find the $$$k$$$th leftmost $$$j$$$.

      This is the problem I want to solve.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I applied this approach for solving B still my test case 2 fails. What's wrong with the approach?

https://codeforces.cc/contest/1550/submission/122490178

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    test 1 5 1 -1 10101

    Correct answer is 2, your code gives 3. It's better to remove the zeroes and then you are left with 111, so you only need to apply the operation 3 times.

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Is there a formula/dp for finding the number of trees in which the distance between 2 fixed labels is even/odd?

Reduced D to this but got stuck, thanks

»
3 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

Problem E is both fun and educational, I really like it. Thanks for this brilliant round!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody tell what is the third not good subarray in 2nd test case of problem C?

6 9 1 9 6

I only discovered [6 9 1 9], [6, 9, 1, 9, 6]

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    9 1 9 6

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We should find three elements, such that:

      i <= j <= k and a_i <= a_j <= a_k

      Or my logic was wrong?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally going to become a specialist after this round :)

»
3 weeks ago, # |
Rev. 2   Vote: I like it +36 Vote: I do not like it

there're two types of people: those who have found the observation in C and those who haven't...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think problem F would be more interesting if s were different for queries

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

    We were expecting a solution without MST, but it seems that it's too obscure.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem C?

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

    You can put 5 points on paper and become sure that there is 1 bad triple (at least).

    First put 2 points and indicate the area where you can't put the third one. Then add third and then forth. And you can see that you have not enough area for fifth.

»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Is CodeForces making me stronger or bullying me?

»
3 weeks ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

can someone help me with a counter case for C My idea ->
using 2 pointer triplet will be bad if any number between start and end is bound by minimum and maximum among starting pointer and ending pointer.

https://codeforces.cc/contest/1550/submission/122495304

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    Hey, think about it:|

    (n = 4)

    (a = {3 1 2 4})

    The answer is 8 but your code output 10 because of the bad triple with index (2,3,4)

    obs: My ideia is lile yours and I spent about 30 minutes to find this case

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

      How is (1,2) , (2,3) , (4,4) a bad triplet? (1,2) — (2,3) -> 2 (2,3) — (4,4) -> 3 (1,2) — (4,4) -> 5

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But this is a bad triple, because:

        d(2,3) = 2, d(3,4) = 3 and d(2,4) = 5

        So, d(2,4) = d(2,3) + d(3,4)

        d(p,r) = d(p,q) + d(q,r), with p = 2, q = 3 ans r = 4, just like in the problem.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

any idea on how to solve problem C?? my idea was any increasing or decreasing subsequence of length 3 is a bad triple. Got the idea to implement dp using a start and end as the state but it would give time complexity.

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

    any sequence of length >=5 will always have a bad triple

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

      why is that?? i mean can you explain the prove please??

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

        You can put 5 points on paper and become sure that there is 1 bad triple (at least).

        First put 2 points and indicate the area where you can't put the third one. Then add third and then forth. And you can see that you have not enough area for fifth.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When the editorial will be post?

»
3 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Video Editorials of this Round A. Find The Array B. Maximum Cost Deletion

»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

General question, what makes a contest "educational" compared to a regular div 2 contest?

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

    I dont think there is any difference apart from the fact that they are organised by the same people every time.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

man educational rounds are always tricky .

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why a does not effect the answer in problem B ?

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

    Because a always *n

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Summation of l over all k will be equal to n as the final string is empty., so this part will be equal to a*n. The final answer will be a*n + k*b . where k = no. of operations.

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

If some people wish to write the things/topics they found educational in A,B and C, it'll be very helpful for me (and I think for others also). So, please do write if you have some time. TIA.

»
3 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

Sorry for the bad stream :(
We should have considered making the stream hidden from the sidebar.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one explain problem a

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    since for all 1 to n for every a[i] there must be a[i]-2 or a[i]-1 ...or a[i]=1 .. then for the least element in the array must be 1 ....then since you need to maximize you add a[i-1]+2 every time and increase the count until ans>=s ...and print the count as if ans =s then it is true and nothing change ...if ans>s then there is a 1 in the end of the array but the count wont change ....

»
3 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

I found this person:

Spoiler

Still continuing to send and hack!!

»
3 weeks ago, # |
Rev. 5   Vote: I like it +59 Vote: I do not like it

For everyone wondering why a good subarray cannot have length greater than $$$4$$$ in $$$C$$$. There is a theorem Erdos Szekeres which basically states that any sequence with length greater than $$$xy$$$ must have either a non-increasing subsequence of length $$$x+1$$$ or a non-decreasing subsequence of length $$$y+1$$$ or both.

Put $$$x = y = 2$$$ for this problem.

Hint for proving this theorem:

Hint
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't register and participate in the contest.If I try to hack solutions now, will my rating get affected because of unsuccessful hacking attempt?

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Hi guys, I haven't tried out hacking feature yet on codeforces so was trying out this time and had some doubts:

  1. Is there any penalty on unsuccessful hack attempt?
  2. I can see that I can hack my solution as well. I don't think this makes sense as then the user can hardcode some condition where it will fail and then hack it to get points.
  3. Is it possible to hack one solution multiple times. For eg. if user A hacks user B, can user C also hack user B ?

For the second point, someone is using the same flaw which i mentioned :

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

    An individual doesn't get points on hacking another user's submissions in Educational rounds or Div 3 rounds.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    1. No penalty for unsuccessful hack in Educational Rounds.
    2. No points for successful hack in case of Educational Rounds, so user will not be benefited.
    3. I am not sure but you can't hack whose solution is already hacked by someone.
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    3.When you hacked a solution, it status will become "hacked" and there won't be a 'hack it' button.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello everyone, it would be really helpful if someone explains the detailed proof of problem C in an easy way so that all the newbies like me get the things clear and able to learn some new concepts. why a good subarray cannot have a length greater than 4 ?????

please help!!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The first thing is that if points A, B, C (and A.x < B.x < C.x) are in a bad triple then point B lies in a rectangle formed by points A and C. It can be proven just by considering several cases.

    Then it's clear that for any point from a good array (let its coordinates be X and Y), there are no points before that have less/bigger Y coordinate and after that have bigger/less coordinates is the same time. Otherwise, we could choose them to form a rectangle, in which our point lies.

    From here, in any good subarray with 4 elements, the second element is the biggest/smallest and the third element is the smallest/biggest (it can be proven by contradiction). If we add the fifth element, then the fourth point will lie in a rectangle formed by either points 2 and 5 or point 3 and 5. As soon as, every subarray of a good array is also good, there would be no good arrays with length greater than 4.

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

"Educational"

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

After how much time the cumulative rating gets updated?

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

How to know in educational rounds whether sys test has been completed after open hacking phase finished ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, codeforces should write final system test pending or something like that.

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

    Educational rounds are typically getting separate Div1 and Div2 leaderboards after system tests are done. We are not there yet, so system tests are still pending. I agree that this isn't very intuitive, but I don't know any better way to guess the system tests completion status.

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

Does anyone know what does the meaning of 00:30 or 01:26 means below the + sign.

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

    It's the time after you solved the problem since the contest started

»
3 weeks ago, # |
  Vote: I like it -29 Vote: I do not like it

Educational round rating pending ... 2 hr later ... rating pending ... hacking phase ends ... rating still pending ... 200 hr later ... rating still pending ... 2000 yrs later ... rating still pending .... 2 million yrs later ... Finally updated.

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

when's the editorial coming out?

»
3 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it

When will rating change!!!!!!!!!

»
3 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

Guys, When will my rating update ???

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any editorial in this round? Keep waiting...

»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

is the system testing over?

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

isn't it rated? then why my rating didn't change?

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

    Just wait until there is a rating change tab in the contest standing page.

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

    Finally ratings are updated!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My Code for C is running in 592ms, will it FST?

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

    The final system test is over already lol.

»
2 weeks ago, # |
  Vote: I like it +44 Vote: I do not like it

To not keep you waiting, the ratings updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!

»
2 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

During the 12 hours hacking stage, I received a very strange DM from someone, who claimed to be an alt account of myACEY. This person asked me about how I managed to hack 122468435 and what was their mistake. But I noticed that myACEY's account is primarily using Python and another account is using C++, sometimes they participated in the same contests and solved different number of problems using very different solutions (so nothing suggests that both accounts could be owned by the same person). I responded "How can I be sure that it was really your account?" and never heard anything back. Now this is eating me a bit. Am I a bad person because of being too paranoid and refusing to share information with a fellow competitive programmer?

As for the hack, that solution was already a bit slow (717 ms on pretests). The amount of calculations it performs depends on $$$s$$$. Processing some $$$s$$$ values is much slower than the others, and $$$s=4902$$$ was one of the worst. So constructing a testcase with 4902 repeated 5000 times pushed myACEY's solution over the 1000 ms time limit. Now this hack is a standard testcase #4 of the A. Find The Array problem and it was included in system tests too (even though I doubt that it managed to catch anyone else).

»
2 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

289 successful hacks and 677 unsuccessful hacks were made in total!

The numbers should be 110 out of 498 if we subtract my 179 pointless self-hacks.

It was a game, and it was fun XD

and don't ever think of doing this, solve problems instead!

»
2 weeks ago, # |
Rev. 3   Vote: I like it -18 Vote: I do not like it

ok