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

Hello Codeforces!

On Jul/14/2019 17:45 (Moscow time) Educational Codeforces Round 68 (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 7 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!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Benq 7 347
2 Geothermal 6 120
3 tmwilliamlin168 6 168
4 neal 6 174
5 square1001 6 174

Congratulations to the best hackers:

Rank Competitor Hack Count
1 algmyr 8:-4
2 Half-Blood_Prince 3:-1
3 A_Egon_ 2
4 plusplus6408 2
5 Benq 2:-1
47 successful hacks and 344 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A dorijanlendvaj 0:01
B MesyuraTheOldDumbGoblin 0:04
C aneesh2312 0:04
D Benq 0:09
E Denisov 0:21
F Benq 0:15
G ecnerwala 1:07

UPD: Editorial is out

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

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

Typically for educational rounds (and for this one in particular), is the intention to have strong pretests to try to prevent failing systests, or to have weak pretests to encourage hacking?

Just trying to get a sense for how much I should trust the pretests tomorrow. :)

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

Hoping for good problems and strong pretests! cough subarray sorting cough

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

PikMike is a boy or a girl?

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

    PikMike = Mikhail Pikliaev (so it's man).

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

The pretests of D last time were VERY weak.

»
3 months ago, # |
  Vote: I like it -41 Vote: I do not like it

India is not in World Cup Finals and you can totally participate without any hesitation

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

Please no Hackforces like last time (C and D).

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

is there any interactive problem in the contest ??

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

I love contest!!!

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

Hopefully I can make blue this contest! I've been going after it ever since I reached my max rating, so hopefully this will be it.

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

Hope for no accident. Haha~

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

Hope that I'll become blue after this contest! :D

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

Wish I can become a candidate master.

What I need is only +26 rating. I think I can achieve that:D

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

I love educational constests!

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

I hope that everyone get the rank which they want. I want get closer to be a blue.

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

agc035 was just moved by 30 minutes, and due to this will propably overlap with this one.

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

There's an Atcoder round today that was delayed to conflict with the first 5 minutes of this round. Would it be possible to postpone this round by 10 minutes?

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

    On the other hand, it is also possible to hurry up on Atcoder, and finish some minutes before the constest ends :)

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

    U are so plodding.I think its hard to solve 2 contests in a row

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

Hopefully I can become purple in this round.

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

Due to the delay in the contest on AtCoder, we moved our round for 10 minutes.

===

По причине переноса контеста на AtСoder, мы подвинули наш раунд на 10 минут.

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

    why not delaying it for 30 mins like Atcoder? Many people would have more time to have a rest after agc.

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

      But someone who must stay up late for this contest may not think so :<( (such as Chinese)

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

Score distribution please.

»
3 months ago, # |
  Vote: I like it -12 Vote: I do not like it

I used to be a cyan coder once. But I've seen a downfall. Wish me luck CFians!!

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

I love educational rounds (^.^)

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

Good Luck && Have Fun !

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

QueryForces is back!

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

(F)educ/k one love

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

GO Federer !!

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

Are Div.1 Participants counted in calculating rating changes of Div.2 participants?

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

    No

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

    No.

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

    When I checked and unchecked the "show unofficial" then nothing really changed. So I also wonder like you.

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

      They are official participants for educational rounds. It is just that, the educational contests are unrated for them.

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

    No. They only show up in the "unofficial ranklist"

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

How to solve D??

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

    You can make an array "win[i]" which means that: win[i]=1: if n=i, Alice wins win[i]=0: if n=i, Bob wins

    Make a program that generates the values of the array, and then find the pattern. You will easily find it.

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

      You wont find it easily as I did not even after searching for it more than half the contest, submitting aprox ten times.

      How is a strategy to solve such one?

      I did write, paint... several pages on paper, but was not able to get the pattern right.

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

        I just found all the patterns when k=3, 4, 5, 6, ...

        When k%3==0, the pattern was a little different than when k%3!=0.

        So I divided the cases into two, that is:

        1) k%3==0

        2) k%3!=0

        Then you will be able to find the pattern. If you can't on case 1, write (k+1) numbers on one row like

        able[0] able[1] ... able[k]

        able[k+1] able[k+2] ... able[2k+1]

        ...

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

          I did. For k=3, 4, 5, 6 I drew the array for index up to 15-20 by hand...

          In fact, just now after inspecting several working solutions, I think I would not be able to write it down as code correctly.

          Seems that is not my kind of buisness.

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

How to optimize N^2 solution for F?

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

    Denote $$$f(l,r)=\sum\limits_{i=0}^{l}\binom{r}{i}$$$, Try to move from $$$(l,r)$$$ to $$$(l,r+1)$$$ and three other intervals in $$$O(1)$$$. Then apply Mo's algorithm to solve the problem in $$$O(n\sqrt{n})$$$.

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

      Wait? Don't we have to calculate $$$f(l,r)=\sum\limits_{i=0}^l(\frac{1}{2})^i\binom{r}{i}$$$? Or my expression is wrong(or needs more optimization)?

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

        We compute the overall answer as the sum of the probabilities that we solve each puzzle. We solve puzzle $$$i$$$ with probability

        $$$\frac{f(l, i)}{2^i}$$$

        for an appropriate value of $$$l$$$.

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

        No. It should be $$$\sum\limits_{i=0}^{l}(\frac{1}{2})^{r}\binom{r}{i}$$$.

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

          Oh thank you. I found my mistake.

          (If I didn't make this mistake I would solve it...)

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

      how do you do that?

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

    There's a solution that runs in $$$O(N \log MOD)$$$, where the second factor comes from computing modular inverses in the process of building the choose function. I can't explain it particularly well, but the gist is that we define the same sum as Roundgod did and note that the required $$$l$$$ will generally decrease over time. Then, we can transition from $$$r$$$ to $$$r+1$$$ quickly (think about Pascal's triangle to see how this works) and can simply add combinations necessary to change $$$l$$$ in order to get the final answer for a certain $$$(l, r)$$$.

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

      We can even solve it in $$$O(n)$$$ — linear time. That's because we can calculate $$$I_x = $$$ modular inverse of $$$x$$$ mod $$$p$$$ by inductively calculating by $$$I_x = I_{p \ mod \ x} \cdot \left (- \left \lfloor \frac{p}{x} \right \rfloor \right )$$$, and so we can calculate $$$J_x = $$$ modular inverse of $$$x!$$$ mod $$$p$$$ with $$$J_x = J_{x - 1} \cdot I_x$$$. That's the all inverses we need to calculate all $$$C(n, k)$$$ and finally the answer.

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

        Shouldn't we use $$$J_{x}=J_{x+1}\cdot x$$$? :)

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

          Really nice idea! In this way we don't need to calculate all $$$I_x$$$. So, this would be better in performance in constant time factor side.

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

          *$$$J_x = J_{x+1}\cdot(x+1)$$$

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

    Let $$$s_i = T - \sum_{j \leq i} t_j$$$. If $$$\ell$$$ is the last crossword completed, at most $$$s_\ell$$$ of the crosswords up to $$$\ell$$$ can take an extra second, and at least $$$s_{\ell+1} + 1$$$ of the crosswords up to $$$\ell + 1$$$ must take an extra second.

    The number of possibilities to check for any fixed $$$i$$$ is linear (the extra seconds up to $$$\ell$$$ and the extra seconds up to $$$\ell + 1$$$ differ by 0 or 1). Also, since $$$s_i$$$ is decreasing, the number of possibilities for all $$$i$$$ put together is still linear.

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

I don't like game theory because I ALWAYS lose when playing game with others.

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

RIP for those who thought that the player can move up to K cells in each turn
Not 1, 2 or exactly K.

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

    Well. I would have read question twice. If I read this.
    Because this problem is standard nim game and expecting it as D would have been surprise for me.

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

      How is "up to $$$K$$$" standard Nim? I think "up to $$$K$$$" can be done by simply checking value modulo $$$K + 1$$$?

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

        A bad selection of words.
        What I meant was that this is rather known. And would have got faster submissions that B/C.
        I read about it (simply checking value of modulo K+1). When I read some introductory level game theory blogs. Thats the reason I used "standard Nim".

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

I'm sure I saw problem B the same but don't remember in which round !

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

Solution for problem D:

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

Good contest, thanks)

How to solve E?

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

    Use lazy propagation and segment tree. That's the hint.

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

      can be solved just with a fenwick tree with line sweeping technique

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

        Even just with ordered_set 57040076.

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

          Can you please explain your approach?

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

            Fix a vertical line as the left side, add horizontal lines that start before it and finish after it. Now, sweep to right to see other vertical lines (as the right side of rectangle). Just keep track of horizontal lines (erase a horizontal line when you reached the endpoint of that). My code is easy to understand.

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

              I have a similar solution but it is giving TLE on test case 3. Can you help me out? code

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

          your code gives wrong answer for 5 0 0 0 10 10 0 10 10 -1 3 20 3 1 3 5 3 0 2 30 2 /* ans=1; your code ans=0; */

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

            no pair of horizontal segments shares any common points, and no pair of vertical segments shares any common points.

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

      I had been thinking on using segment tree for about hour when found O(n^3) algorithm with bitset. I still do not know/understand how to solve it using segment/fenwick tree. Looks like i blundering something about it...

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

    Make bipartite graph with vertices on the left corresponding to horizontal segments, and vertices to the right — to vertical ones. If two segments intersects, there is edge between corresponding vertices. Now lets iterate over all pairs of vertices on the left. Lets there are K common vertices on the right, then we need to add K * (K — 1) / 2 to the answer. Complexity is $$$O(N^3)$$$, but it is easy to see, that we can optimize this with bitsets, and overall complexity would be something like (N / 2) * (N / 4) * (N / 32), which seems to be fast enough (it is around 0.5 billion simple operarions)

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

      You can find a number of common vertices K by taking a square of an adjacency matrix. And taking square of a matrix can be done in O(n^2.8)

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

      Could you explain what do you mean by this "__Lets there are K common vertices on the right_," Thanks in advance.

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

        Let's fix two vertices on the left side (A and B). Let's call vertex C on the right side common if C is connected to both A and B.

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

      My bitset solution gave TLE-5 but using pragmas it passes in 1965ms. To optimize it should we make bitset matrix based on smaller count of horizontal or vertical segments?

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

      Could you explain how you got the complexity as N/2*N/4*N/32. Thanks in advance.

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

        Without loss of generality, assume that there are more vertical segments, than horizontal one. Now number of horizontal segments is no more than N / 2. Let's iterate over all unordered pairs of horizontal segments (there is no more than (N / 2) * (N / 4) such pairs) and AND their bitsets, which is N / 32.

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

          Was a very convincing explaination. Thanks

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

I'm pretty sure I had the right idea for D by printing Alice or Bob for values of n and k mod 3, along with a special case for k = 3. However, I got WA on case 3; could anyone tell me what I was missing?

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

    if k%3==0: Bob wins if and only if (n%k)%3==0 && (n%(k+1))!=k.

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

      Isn't it iff (n%(k+1))%3 == 0 && (n%(k+1))!= k

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

      k % 3 == 0 : Bob wins iff (n%(k+1)%3)==0 && (n%(k+1))!=k

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

      Would you please care to elaborate on why this would work?

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

    k = 3 is not the only special case. Any k which satisfies k % 3 == 0 is a special case.

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

    Thank you all for your input! It seems as though I was simplifying the problem too much.

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

Unusual start time is sometimes soo annoying; i didn't even have an hour in my hand.

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

can someone tell me what could be pretest 2 in question B, i tried every damn possibility, my code worked but it wasnt getting accepted.

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

    What problem are you meaning?

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

    will fail on 4 3 * . . * . . . . * . * * Your submission gives output as 3 but the answer should be 2 if u select 4th row and 1st column

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

I hope that this round won't be a HACKducational round.

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

LOL, First time A,B and C solved. problem C was quite easy i guess.

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

Some one please give a proper explanation how to solve D?

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

    The best way to solve D has already be given. Generate a few cases and observe the pattern. You can generate cases like this: A position i is marked 'W' if there is a winning strategy if it starts at i, otherwise it is marked 'L'. You can calculate all 'marks' as: if all positions that you can reach from here are marked 'W', then that means no matter what move you do, your opponent has a winning strategy so mark the current position 'L'. Otherwise, mark it 'W'.

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

Its sad that, i misunderstood Problem D. I thought Alice and Bob can only move i->i-k, if i>=k, and can take a step i->i-1 or i->i-2, only when i=1 and 2 respectively.

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

In my profile it says i have registered 50 years ago ( which is not really possible ).

Can anyone help me with fixing this .

EDIT: it is fixed now

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

https://codeforces.com/contest/1194/submission/57052535 can someone tell me why isn't it working ? I am 2*x , but random no. are being printed In the same way, https://codeforces.com/contest/1194/submission/57055104 if u copy code of this question and run on DevC++ , the answer is coming right , but on codeforces its coming wrong

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

    Maybe you should place sync_with_stdio just before you start input/output else it will mess up because of synchronization?

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

    you have written IOS after (cin >> t ) . This is happens because of that. You should write IOS before taking all input.

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

Can someone please help me in problem B . What i was doing is to find min_row first and find its respective min_col both having minimum number of white paint . Also again finding min_col first and find it's respective min_row with least white tiles. Answer would be minimum of both 2 possibility . But i m still getting wrong . Any counter case ? My submission

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

    The thing is, you need to consider all rows that have least tiles, because your program chooses the first one and that might not be optimal since there could be another row that could have the same amount of white paint, but that other row might intersect with another column,with minimum white tiles, on a white cell which means that by painting that white cell on which they intersect, you reduce the amount of white paint on both the column and the row with the least amount of white paint. Hope I helped.

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

      i have the same idea of yours but i can't come up with a test case that satisfy that.

      actually, every time he choose just the first minimum row and this is not always correct, the second answer of the first minimum column got the optimal solution and vice versa.

      anyone managed to get that test case guys ?!

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

        3 4 . . * * . . . * * * . .

        1st and 3rd row have 2 white tiles each which is minimum. If we select first row we'll get 3 as an answer but if we select 3rd row and 4th column we will get 2 as an answer.

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

          No you're wrong, check his submission above !

          ans1 will select first row yes, BUT ans2 will select the 3rd column and 3rd row which = 2. then, he output the min(ans1,ans2). so, according to your test case he still correct.

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

      Yes , that's why i am considering both ways . What i mean to say that

      1 . Find minimum row and it's respective minimum column and save it's ans . Let's say ans1

      2 . Find minimum column and find it's respective minimum row and save it's ans in ans2.

      Output minimum of 2.

      For eg let's consider this case (s means '*' )

      5 5

      s.s..

      ....s

      s..s.

      .s..o

      s..s.

      1 . selecting minimum row with least white tile . In this case there are four rows with 3 white tiles. (1,3,4,5) . Select any of them . Let's select 1'st row . Then for this row select minimum column keeping in mind of double counting of same white tile . we get (2,3,4,2,2) for respective columns (1,2,3,4.5) . Select minimum of them . We get ans1 = 3+2 = 5 .

      1. Now this time select minimum column first and find it's respective minimum row . Let select column 1 with 2 white tile and row 4 with 2 white tiles ans is 4.

      Optimal answer is min(ans1,ans2) =(5,4) = 4.

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

This is tastcase 2 on Problem B. Is it Strange?

15 158 169 ..**....**...*..*..****.....**.**.**..*****....*..*...*...*.*...*.**....*..*.*****.******...******.*..*...*..*...**.***..*..*.*.***.*..*.**.***.*..*.........*..**...**.. ..**...*.*.*.****.*..***...**.**.*..*****.******....*.*.........***.****.*..**....***.*.*.****..*****.*.....**..*...*****.***.*..***.*****.*.*****.***.*...**...*..**** ...*..*..***.**...**....**...***.*****.*..*.*.**..*.**..****...***.....**.**.*...****.*......*..*..***..****.**....***..*...***...***...*..********.*.**...

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

    That's only a part of it. The rest is snipped off and replaced with ... at the end which happens to look like part of the grid.

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

What happens if our hack is incorrect? I am new to hacking. Are there any points for successful hack?

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

    No; hacking will not affect your official ranking in an educational round.

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

      We can move up in standings if we hack someone above us, right?

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

    No points, just satisfaction xD. (In educational rounds)

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

Why official standing showing unofficial participants !?

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

    everyone is official and it is rated for div2 only

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

      Even if I uncheck "show unofficial participants", it still shows unofficial participants in the leaderboard.

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

Don't know why but I can't find this contest on contests tab even dough I participated. Does anyone else have this bug?

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

    It doesn't appear there until the ratings have been updated.

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

D problem is a good type of game theory

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

    I didnt solve it so maybe I am not objective, but its nothing special. Still, of course its better than theoretical game theory problems which involve grundy numbers or something. I dont think anyone loves that.

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

how to solve E?

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

HubyBee Hacked himself purposely (Problem A). Isn't it illegal? Link: https://codeforces.com/contest/1194/submission/57060726

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

    Sorry guys, I dont understand why you are downvoting me. Is it a lot of bots from HubyBee?

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

      Keep downvoating me. Go ahead.

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

        It's maybe because of the fact that 'Isn't it illegal?' is a stupid question?!

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

          I honestly dont know much about hacks. That is why I asked. If I knew it, I wouldn't ask.

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

How to generate solution for D without observation? Any simple technique and proof?

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

    Fix $$$k$$$, and for each $$$m<=n$$$, $$$f(m)=A$$$ if Alice will win if the strip were to begin at $$$m$$$, and $$$B$$$ otherwise. Obviously $$$f(0)=B$$$ and for the rest, $$$f(m)=A$$$ if and only if exactly one of $$$f(m-1), f(m-2), f(m-k)$$$ is equal to $$$B$$$. (For the rest of the proof we will not deal with the size of $$$m$$$ with respect to 1, 2, $$$k$$$, the proof will still be the same with all those constraints added, just a bit messy).

    We shall proceed by inducing on $$$m$$$ in each case of whether $$$3\mid k$$$ or otherwise. In either case, we observe that $$$f(m)=B$$$ means $$$f(m+1)=f(m+2)=A$$$ (reason being explained above). We claim that for the first case, $$$f(m)=B$$$ iff $$$3\mid m$$$, with base case $$$m=0$$$ explained. Now for inductive step, if $$$3\nmid m$$$ then either $$$3\mid m-1$$$ or $$$3\mid m-2$$$ and therefore $$$f(m-1)=B$$$ or $$$f(m-2)=B$$$, which follows $$$f(m)=A$$$. Otherwise $$$3\mid m$$$ and we notice that neither of $$$m-1, m-2, m-k$$$ are divisible by 3, and therefore by induction hypothesis $$$f(m-1), f(m-2), f(m-k)$$$ are all $$$A$$$, so $$$f(m)$$$ must be $$$B$$$.

    Now $$$3\mid k$$$ is tricky: the first $$$k-1$$$ values follow from the previous case, but $$$f(k)=A$$$. We, instead, consider modulo $$$k+1$$$ and the first $$$k+1$$$ values (0, 1, ..., $$$k$$$) should be clear. Now let $$$m\ge k + 1$$$, which means we should consider $$$f(m-1), f(m-2), f(m-k)$$$. For clarity, consider $$$m_0$$$ as the remainder of $$$m$$$ when divided by $$$k$$$. The induction claim, as suggested by others, is that $$$f(m)=B$$$ if and only if $$$m_0=0, 3, \cdots , k - 3$$$. We have the following cases:

    $$$m_0=0$$$, and $$$m-1, m-2, m-k$$$ are congruent to $$$k, k-1, 1$$$ modulo $$$k+1$$$, and by induction hypothesis it follows that all $$$f(m-1), f(m-2), f(m-k)$$$ are all $$$A$$$ so $$$f(m)=B$$$.

    $$$m_0=1, 2, k$$$: obvious from the previous case.

    The rest of the cases: since $$$3\le m_0 < k$$$, $$$m-1, m-2, m-k$$$ are congruent to $$$m_0-1, m_0-2, m_0+1$$$ modulo $$$k+1$$$. If $$$3\nmid m_0$$$ then either $$$m_0-1$$$ or $$$m_0-2$$$ is divisible by 3 and less than $$$k$$$, so either $$$f(m_0-1), f(m_0-2)$$$ is $$$B$$$ and this case is done. Otherwise, $$$f(m_0-1)$$$ and $$$f(m_0-2)$$$ are both $$$A$$$ so we only consider the last one, $$$f(m_0+1)$$$, which is also equal to $$$A$$$ since $$$3\nmid m_0+1$$$. This concludes the proof.

    Sorry for the poor organization, I am writing in a hurry (though it's fun to do so :P )

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

Good job to laklouch for some high quality hacks: https://codeforces.com/submissions/laklouch

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

    I think he should be banned.what do you think?

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

I changed just two characters in my first submission(douring contest) and I got AC for problem F after the contest (57059435). I was really unlucky during the contest. :(

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

    A moment of silence, please. _ / \ _

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

Why put such a high bound on E when solution is n^2 log n? When n=5000 that is about 3*10^8 operations.My segment tree solution got TLE which cost me a lot of time before i finally stopped thinking about an n^2 solution and optimized my segment tree by a little bit to save those 200-300ms that i needed.

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

    You can solve it in O(K*(K-1)/2) bitset operations, where K = min(horizontal, vertical) so in the worst case, K = N/2. Considering each AND operation runs in N/64 more or less, it's a good complexity ~ 250.000.000 operations which run in aprox 1600 ms

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

      I thought of that during the contest but i thought that would get TLE much easier than the log n solution since it's essentially O(N^3). Interesting to know that works too.

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

Is there a rigorous mathematical proof to problem D (when k% 3 == 0)

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

    Think only about i-1 and i-2. A means Alice wins and B means Bob wins. This is the winning pattern, starting from n==0: BAABAABAABAABAA. Basically, if pos%3==0 the ans is Bob. This happens because you only reach positions that Alice wins form this pos%3==0 positions. When k%3==0, the lowest position that change is pos==k, and it is easy to see the reason why ( you cant go to pos-k because it is < 0). Then, a part of the winning pattern will become: AAApos, id of pos == k+1. So both pos-1 and ipos-2 will reach A, so the ans should be B. And we know that pos-k changed from B to A. So the unique ans to pos is B now. This is the same as restarting the winning pattern, so, this winning pattern in the range [0, k] will be the same as [k+1, 2*k] and so on. I know that this solution is not rigorous mathematical, but I hope it will help you!

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

      Thanks

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

      Assume k % 3 == 0. Let's iterate array from start. 0 is lose, 1 is win. So basically without the k jumps its all 011011011 or (011) repeating infinitely — start is losing, and you can get to start with 1 or 2 jumps so next ones are win, and third is always lose cause opponent wins. Now for first k cell we can't do k-jump so its all (011) then we suddenly can, and we jump to 0, so k'th cell gives us a 1 and the sequence ends like ...011011(1) last 1 being k+1'th position, or k'th index.

      Next, consider this lemma : k — jump is useful iff it lands us from 0 to 0 without k — jump. In this case, we get a 1 in that position where we are jumping from and jump to losing position. So what does that give us?

      At k+1'th index we have 0 again, because we end with three 1 and cannot do usual jumps and k-jump lands us on 1 too. K-jumps are useful only on every third position only, because we had a sequence (011). But every third position is 1 anyways, so we can discard k-jumps and we have repeating sequence of (011) starting from k+1'th index. This holds true until we get to 2*k+1'th index. Because of 111 shift, we have suddenly 0 at index 2*k+1 — k = k + 1 (try doing with k = 3 and 6 to see pattern easily) and we get again 1 at index 2*k + 1 and again there are three 1 there. You can use this reasoning to conclude that structure ((011) + 1) at the end is repeating, first (011) being taken k/3 times. Then knowing that, take remainder of n modulo k + 1 (counting last 1) and check. If we land on last index, return 1. Else divide remaining pattern modulo 3 and return 1 if remainder is 1 or 2.

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

How to solve B ?

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

    Imagine you are in Cell(x, y), now you have to make sure all cells in this row and column must be black. This means some white cells need to be painted. Now how many white cells are to painted? For this, just store the count of white cells in each row and column. Now if at (x, y), cells to be painted, X (lets say) =(White Cells in Row 'x' + white cells in Column 'y'); just make sure if current cell is white, you subtract 1 from X because it will be counted in both row as well as column. Just find minimum of 'X' from all cells in O(n*m); Hope it helps.

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

I was thinking to model Problem D in terms of recursion in n and k and then try to find out value using matrix exponentiation. Did anyone else tried it this way?

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

Pretests too strong only 30 successful hacks so far

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

Is there a better soultion for B than O(n*m).

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

    what do you mean ? don't you want to input the grid that's o(nm)

»
3 months ago, # |
Rev. 4   Vote: I like it -11 Vote: I do not like it

Hey, Guys I just did question A checkout its solution: link

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

    I am not able to understand why you people are downvoting. Is the solution not clear to you/ Is there mistake somewhere??

    You can point it out if there is any.

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

    The problem is no one needs your solution .

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

I will be saved from NEWBIE!! [user:_seyed37_][user:Jefri_007]

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

i don't think that there will be much system failures . Pretest almost cover the test cases set.

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

sir when editorial is going to be released?? need it .

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

How to solve E

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

    Make an events array of three types of events: vertical segment, horizontal segment left point, horizontal segment right point plus one. Sweep from left to right. At every coordinate first process all horizontal segment updates in a segment tree (update the y-value with plus or minus one). If you reach a vertical segment, consider it as the left side segment. Then for each fixed segment loop over all events to the right of it and update the segment tree accordingly. If you encounter another vertical segment, then add (number of horizontal segments intersecting both segments) choose 2 to the answer.

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

      When I was reading your answer I wondered what exactly "update the segment tree accordingly" means. If I understand correctly then you do the following: Once you fixed a vertical segment as left side of a rectangle you loop over all segments to the right of it: On every horizontal-segment-end you update the segment tree (i.e. decrease the corresponding y value by 1). On every horizontal-segment-start you do nothing. On every vertical segment you add some number of new rectangles to the result (as you described it). The reason that no operation is done on horizontal-segment-start is that the horizontal segments that start after our fixed vertical segment do not intersect with our fixed vertical segment and thus should not be considered. Did I understand this correctly or am I missing something?

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

        You're right. But this is kind of the same mistake I made (I had 16 wrong submissions): "On every horizontal-segment-end you update the segment tree (i.e. decrease the corresponding y value by 1)"

        The thing is, you have to store the start point of the horizontal-segment-end, because if you decrease by one and the segment has started after your left segment, then you'll end up undercounting the number of segments.

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

          Oh right! That's quite tricky to see. Thanks for your answer!

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

May you tell me where the Editorial is :>

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

    Probably not published yet.

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

    I'm also hoping to read it and check my opinion and code...

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

When system testing will start??

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

System testing start

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

Quickest system testing seen on codeforces :D

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

Does cf has a YouTube channel. I guess if there is one on which veduo solutions to the contests can be provided , it will be of great help to beginners atleast .

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

editorial please??

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

LOL, I've pushed N^3/64 in E, really want to know the right solution. At first I've used bitset, which gave TL 4. After rewriting bitset myself, it gave AC in less than 600ms, that's amazing.

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

Who wrote solution for E with fenwick tree and complexity O(n^2logn)?

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

Can anyone please tell when will the editorial be out ??

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

Problem D

How to find pattern using generated ans sequence for several n,k??

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

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

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

Why is my solution for problem E giving TLE. I used line sweep algorithm with ordered_set. Time complexity: n^2 log(n)

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

    I think in one of the first blog posts introducing ordered_set to codeforces, they concluded that it was twice as slow as recursive segtree. My recursive segtree solution takes 1400ms on the problem, so it kind of makes sense that it could TLE.