ch_egor's blog

By ch_egor, 5 weeks ago, translation, In English,

Hi everybody,

This Sunday there will be a 16th Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507).

Round will be held at 10:05 UTC on Sunday and will last for 2 hours. Each division will have 6 problems.

Problems are prepared gritukan, Glebodin, Andreikkaa, qoo2p5, mingaleg, Flyrise, _kun_, achulkov2, grphil, Sehnsucht, Aphanasiy, Sender, DebNatkh, GreenGrape under my supervision with great help of GlebsHP, _meshanya_, Endagorion, Zlobober and Helen Andreeva.

Thanks to _kun_ for the round coordination and statement translation, and also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

UPD1: The scoring distribution will be:

500 — 10001000 — 1500 — 2000 — 2500 for div. 1.

500 — 1000 — 1500 — 20002000 — 2500 for div. 2.

UPD2: Editorial

UPD3: Winners:

Div. 1:

  1. mnbvmar
  2. bmerry
  3. j_______________________
  4. tlwpdus
  5. WA_TLE

Div. 2:

  1. Ebola_Emperor
  2. Orange_User
  3. orbitingfIea
  4. little_waxberry
  5. fnch
 
 
 
 
  • Vote: I like it  
  • +194
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it -52 Vote: I do not like it

will it be rated for any division?

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

Unfortunately clashes with GP of Korea.

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

unfourtunately that's on my school time :(

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

    On Sunday? :o

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

      Yes, in arabic countries the firday is a day-off, not the sunday

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

        Lol, this comment chain is a copy of this one from the first Moscow Team Olympiad held on Codeforces.

        Guess somethings never change xD

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

        i wish there a country where every day is off the school :P

        And Hii Bau :D

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

        not only Arabic countries , in Iran the friday is a day-off.

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

    In many Chinese senior high schools, Saturday and Sunday are school time. ( >﹏<。)~

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

A Russian Olympiad clashing with open cup, why am I not surprised?

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

We're going to write it tomorrow official and my team is really scared of Mr.GreenGrape in problemsetters

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

Perfect time for Chinese users!

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

Perfect time for Korean users, as the contest is in 7PM, and they can't take today's GP!

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

GL&HF

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

hope not a mathforces

»
5 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

Really bad time for US users :(

»
5 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

is it rated?

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

Perfect time for Chinese users.Thank you Codeforces!

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

The site has slowed down significantly.

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

In Div 2 problem D, the time limit is very strict. Python solution not passing pretest 8 even after all possible optimisations.

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

Div2 D pretest 13?

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

    Yes, this one killed me too

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

      Mine too gave WA on 13, using DFS. Bypassed it by using BFS. Probably recursion stack size was the issue.

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

        recursion stack size has never been an issue for me ON CODEFORCES.

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

        the same experience as yours,but my bfs was hacked because i didn't use priority_queue.

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

      I too got WA, solved using DFS!

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

Interactive Problem and Binary Search again.

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

What were the hacks on Labyrinth about?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 10   Vote: I like it +25 Vote: I do not like it
    Input
    Output

    for those who used a single queue.

    UPD: It seems that not everyone used a single queue failed on this test.

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

      Then my D will fail systest

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

      I am using single queue but i pass this test

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

      Lol?

      I used a single queue and passed systests in 140ms.

      Could you elaborate on why was that supposed fail?

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

        Your solution works cause you're checking for a better answer on

        if(lf[xx-DX][yy-DY] < lx)
        

        Which is pretty much the same thing as removing the if and making sure you visit the node with the least amount of horizontal moves as possible (i.e., by using a priority queue and sorting by increasing number of horizontal moves)

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

CSAcademy saved me on E with the geometry tool.

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

yeah i managed to hack the Grandmaster last minute!!!

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

After one hour of rocket science, I realised that answer for C is.

sort(s.begin(), s.end()); cout<<s;

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

    So the correct answer for asasas is aaasss, isn't it asasas better? First one has 8 palindrom substrings and the second one has 12.

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

      First one also has 12

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

      First one has:

      a

      a

      a

      s

      s

      s

      aa

      aa

      ss

      ss

      aaa

      sss 12 in total.

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

      both have 12. 3 as, 2 aas, 1 aaa and similarly for s.

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

      No, first one too has 12 palindromic substrings..

      'a - 3 times, aa - 2 times aaa - 1 time, total - 6

      and similarly 6 for sss so, 12

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

      It's 12 for both. Single character is also a palindromic substring.

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

    what is the correct approach to this problem?

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

      It is a correct approach, which can be proven.

      Basically the idea is that if you consider any palindrome, its both ends must have same character.

      This implies natural bound on the number of palindromes having end of character c occuring x times: x(x + 1) / 2.

      One can see, that sorted string reaches that bound exactly.

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

I bet there will be lots of FST (failed system test) on Div1.B/ Div2.D, since lots people are using queue instead of priortiy queue, which will results in TLE. Though, it is not easy to hack them :(

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

    Deque is enough, thought

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

      Wait. I don't understand. Wouldn't the same element be put into queue for more than one time? Just like SPFA? Does anyone want to explain that to me?

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

        Usual 0-1bfs — deque + array that indicates visited cells

        You won't visit cell with better cost than first visit.

        First time (using 0-1bfs) — cell will be visited with L left moves and R right moves, all other times it will be L+k and R+k where k>=0

        P.S. I hope it understandable enough

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

          So the cost will be different if you move vertically instead of horizontally, right? which means the cost in your queue can be not monotomous.

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

            No, it will always be monotonous.

            The idea, is to push a vertex at back of deque if the weight is 1, and at the front of deque if weight of edge is 0. Since, there can be atmost two levels of weight in queue, it will always be monotonous.

            My submission

            You can read about it here

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

              Oh! Use deque, then it is always monotonous! Such a neat application of deque! I got it. Thank you so much!

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

          I didn't think of why you use a deque instead of queue. Now I get it. Thank you!

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

I am eblan.

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

whats the correct approach for div2 d?

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

    0-1 bfs

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

      I have done same but got TLE in pretest 8

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

      So it's dijkstra

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

      great idea numb!

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

      so why does bfs fail ??

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

        usual bfs will find (8;3) with 5 lefts and 2 rights and won't go to (8;4)

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

          If we were to use dijkstra's instead, do we sort the items in the priority queue based on the number of left moves, or the number of right moves, or does it not matter? And also, do we sort it in ascending or descending order?

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

            the number of left plus right moves, ascending order (firstly take the least)

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

          so we should always go up or down first

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

      By 0-1 bfs do you mean we will have to take n*m*4 states.I was doing the same.But I could not submit the code because of a bug I had in my code.But my code passes the test you have given above.

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

        Why 4nm?

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

          Because n*m states for each cell and 4 states for from which direction i entered to that cell.Otherwise if i take n*m states then it was not unique enough and creating conflict.

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

            Why do you need the information "from which direction i entered to that cell"?

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

              Yeah.The extra state is not needed.My code is giving correct answer without it.Thank you.

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

          ignore

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

I had RE 8 on D problem because of pragma

pragma

I think it can be a problem of new servers. MikeMirzayanov, can it be fixed?

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

how to solve F?

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

    Let dp(i) be the maximum length of a journey starting at position i.

    Then, dp(i) ≥ x iff there exists such j that i + x ≥ j, dp(j) ≥ x - 1 and s[j, j + x) matches either s[i, i + x) or s[i + 1, i + x + 1).

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

    You can get different and solutions with the following observation:

    There exists an optimal journey such that these conditions hold:

    1) The maximal length of a string in the journey is .

    2) The difference in lengths of two consecutive strings in the journey will always be 1.

    Mine didn't pass but maybe someone passed with such a solution.

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

    My solution is . Not sure if it will pass.

    I am going to assume the string to be reversed.This way the strings in a journey are going to be increasing in length.

    We can prove that there always exists an optimal answer when ti has length i. Now, let dpi be the largest possible length, such that the last string ends at position i. Note that if we can have a valid length l ending at i, we can also have a valid length l - 1, so it makes sense to define such a dp state.

    We can binary search on dpi. For a length l, the second last string is either same as si - l + 1... i - 1 or the same as si - l + 2...i. We find the rightmost such string which doesn't intersect the last string, and check if this string could be used according to the dp state.

    Finding the rightmost possible second last string can be done using persistent segment tree in . Basically, we have a range on the rank in suffix array the secondlast string can belong to, and a maxmium possible rightmost index for the secondlast string as the constraints.

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

      It won’t :(

      Try to replace binary search with some monotonic observation.

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

        Passed with small optimizations. Sad that both the accepted solutions have worse complexity.

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

Time limit for Problem D is too strict :(

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

    Not at all. It can be solved in O(nm).

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

      my solution is also O(nm) but i am using map which give me TLE on test 8

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

        So your map don't have a log?

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

          I am using map<pair<int,int>,pair<int,int>> which is very slow When I get the idea why my solution is slow I am very late

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

            Each access is O(log(n)) time, which seem to be timing out under the current constraints. Instead, try using a 2D array of pairs, so that the time required for each access is constant.

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

How to solve Div1 D?

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

My solution for Div2 D is failing on test 13. Could anybody help me where I am making a mistake? Thanks!!

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

    My approach it is the same, if u get the solution tell me

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

    The time limit is too strict, possibly due to recursion and stack size.

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

    As far as I understand you did a dfs and checked the conditions and you dont visit the same place twice. However consider this

    .....

    .*.**

    .x.**

    x is where you are initially.

    lets say you can go left at most once and right at most twice.

    Then if you go left and go up twice and go right twice you will mark (0,2) as visited and when you come there again from (2,1) -> (2,2) -> (1,2) -> (0,2) you wont continue since it (0,2) is visited however you went right only once and if you continued you could go right.

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

What’s pretest 10 in div 2 E?

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

    Probably something like 1 black and 29 white.

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

    Yeah I was getting wrong answer on pretest 10

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

    n = 30, jury mostly assigns colors randomly.

    However there is a small twist: in all of jury tests (except for sample) if it is possible to assign a color, such that it makes impossible to separate points later jury will always do that :).

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

Div 2 Problem C was tricky. I can't prove solution correctness. Can anyone give me a proof ?

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

    answer is just sorted s. if Nx is number of occurrences of x in s. then number of palindrome substrings because first and last letter of palindrome must be same. on the other hand this number is achieved when s is sorted.

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

      I am trying to understand this formula you stated.

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

        is number of ways to choose substring so that it starts and ends with x

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

          Shouldn't it be (nx) * (nx — 1) / 2 then ?

          Number of ways of picking 2 things out of nx. (Combinations)

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

            substring can have only 1 character

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

              Oh thanks!

              Got the same formula after accounting for substrings of length 1 (adding Nx to my formula)

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

      I am still not able to understand this formula. The no. of palindromes in a string of length n having all characters equal to c will definitely be n * (n + 1) / 2 but how does that justify that summing over this expression over the frequencies of all chars in a string having more than one character gives an upper bound on the no. of palindromes that we can have in a permutation of the string ?

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

gag forces?

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

With new Judging infrastructure, I hope System testing would be a bit faster.

So that i upsolve after that :)

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

C and D combined made this the worst problemset in my opinion I've seen so far in codeforces.

C was binary search. Nothing else, just binary search, just hidden behind a silly problem statement about lines. There's lots of complaints about every interactive problem being binary search and then we get new problems like this :/

D was a math problem emphasizing exactly what I hate about most math problems. You just have to make a trivial observation (either n or the number of rounds is small), and then calculate stuff. Of course, the calculation isn't interesting either, It's just super annoying case handling.

The especially annoying thing about D was that the last person can take just one candy, even if they have a sweet tooth. That adds nothing to the creative part of solving the problem, and around doubles the amount of case handling. Why was that there?

In my recent memory I don't remember any problem worse than either of these, and now we got two of them on the same round :/

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

    I 100% agree. Missed that sweet tooth — one candy case for 30 minutes during contest...

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

      Remembered comment of some cf user but can't find that comment. It was something like follow

      F*ck math problems

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

    Well, while I will agree that D had hard technichal part, I not very much agree with your complaints on C.

    You just needed to come up with cute binarysearch-like construction and the implementation is very short. If the problem was obvious to you -- just get AC in 5 mins and move on!

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

    For me div1C was not trivial, and had a lot of challenges, not just "implement binary search". I don't think the geometrical construction was obvious at all.

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

In problem D Div 2, why dfs not working ?? thanks

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

    (edited) dfs won't work, because you can end up in a square with "wastefully expended left/right moves". Meaning, you could end up in the same square later with fewer left/right moves. What do you do at this point? If you reprocess the square and start doing dfs again from it, you will TLE for sure. If you don't reprocess the square, you might get WA if later on you fail to reach some square because you had wastefully expended left/right moves earlier.

    edit 2: or maybe dfs will work if you can do dfs in such an order that you never wastefully expend left/right moves?

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

    Consider you started from vertex 'X' and at some point you are at vertex 'Y'

    DFS ensures that you visit every vertex only once so you won't come to vertex 'Y' again. But as the graph formed might be cyclic i.e. there can be multiple ways to reach a vertex 'Y' from 'X' and there can be a possibility that there is some shorter path to 'Y' that you'll miss.

    PS: Dijkstra :)

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

    20 7
    3 6
    5 2
    ......*
    .****.*
    .****.*
    ..ox*.*
    ..*
    ..*
    ..*
    ..*
    ..*
    ..*
    ..*
    ..*
    ..*
    ..*
    ..*
    ..*
    ..*
    ..*
    **....*
    ******* you may dfs to the point "x" from the path above and stop at the point "o", when you then dfs along the path below, you're blocked at the point "o" which is visited. You could have reached "x" but not. :) I also used dfs :) this case has been mentioned above(if it is shown unexpectly)

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

I got trolled by div2 C lol :/ Wrote 80 lines of buggy code...

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

    My solution in python:

    def ans():
        n = int(input())
        c = bin(n).count("1")
        ans = pow(2, c)
    
        print(ans)
    
    tc = int(input())
    for _ in range(tc):
        ans()
    
»
5 weeks ago, # |
  Vote: I like it +47 Vote: I do not like it

Test 40 Div2D distroyed so many dreams :(

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

    There goes my hopes of entering div1 :(

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

      wat is hope?

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

        form Red's point of view !

        Hope is a dangerous thing ! hope van drive a man insane

        from Andy's point of view !

        hope is a good thing, maybe the best of good things and no thing good ever die

        you choose to be realistic (Discussion), ok but don't try to make people give up their dreams/goals please !

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

weak pretests in div2 D

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

The Div1 problem E about lasers is beautiful in my opinion, thanks to the authors!

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

I guess that my solution to F has complexity O(n2.5)... I implemented O(n1.5·log(n)), but it turned out to be slower and more memory-eating, so I resubmitted older brute force, which passed with max time lower than one second.

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

I GOT TLE IN TEST 10,IN DIV 2 C MY SOLUTION time complexity in o(nlogn) but still it got timed out. is it due to slow input output?

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

Can somebody please help me finding why my code for DIV2 D gives a run time error?? CODE

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

The difficulty curve was.. 98.9%, 75.2%, 73.7%, 5.9%, 2.1%, 0.4% (percentage of people who solved each problem)

Perhaps codeforces should consider including problems solved by between 6% and 73% of participants???

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

    Impossible

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

    It was a bit... unexpected to us.

    We held a presolving of the moscow team olympiad, from which the problems are. And most of the teams got accepted all problems except problem corresponding to Div1F.

    So I was even worrying whether our Div1D and Div1E are a bit too easy.

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

      maybe the next time the presolvers group should contain not only red and orange coders, not only ROI prizers and ROI winners?

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

What's Test 27 in Div2 D?

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

Can someone explain why Div2 D Test 40 failed for me??

44306721

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

    Just go left, straight up and down, then go right. You can visit all the free cell. 0-1 bfs can solve this problem. Because moving up and down costs 0, you should push one colomn into the queue at the same time when visiting a new cell.

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

      but what is the issue with normal bfs even in normal bfs i am trying to find the node closest to a popped node so that the nearest nodes are reached first.

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

        Normal bfs just visits the nodes as quick as possible. This means it may go left and right for several times and reach the limits. But it is possible that existing a path which is longer than the first one but turn left or right less. In this situation, bfs will visit a node that already been visited, and won't push the new node into the queue, leaving some of the nodes not visited. My code

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

How to solve Div2 E??

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

    Use binary search! Put x somewhere to the middle (from 1 to 999999999) and fix it (x=3, for example) and try (3,0) (save the color). Next try (3,500000000). If these two point have the same color next point you should try is (3, 750000000) if colors are different next point should be (3, 250000000). Beware of edges cases: one with all points with the same color and when another one only one color is different 44313158 (very bad code, sorry)

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

Can someone look into my solution for DIV 2 D problem 44308344 and tell me where I am going wrong. Thanks :)

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

How would you guys come up with the solution for problem C, Div 2? And how would you test it to make sure that every time you sort the string’s characters you get maximum number of palindromes?

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

    Sixth sense!

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

    I manually checked it for random strings of length 10

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

    I was trying something on paper and I suddenly saw that for aaaaab the count is much higher than its other permutations, once I realised that I could prove it easily as :

    suppose you are counting palindromes with a as it ends, now if you insert anything in between two a's, that may decrease count by 1. Hence all occurences of a character must be together.

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

where is the editorial?

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

DIV1 B:
Suppose, system tests are weak.
This solution based on simple BFS and single queue (not BFS-0-1) 44319324 passed all the tests.
UPD: tests are not weak, my solution differs from BFS in visiting vertexes twice and more times.

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

    I think this solution is right. It has right answer on my hack

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

    This is equivalent to SPFA (or Bellman-Ford with queue). It is a correct shortest path algorithm, and although its worst case complexity is O(VE), practically it's very fast for most graphs.

    SPFA can be hacked by specially constructed graphs, but I don't know whether such graph exists given the restrictions of this problem. Also, since SPFA is not popular outside China, non-Chinese problem setter usually don't make anti-SPFA tests.

    Disclaimer: My solution used the same algorithm.

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

      Thanks for the information, didn't know neither about SPFA neither about Bellman-Ford. There is a reason to read something.
      Finally, found the difference between my solution and simple BFS: in my case one vertex can be visited once again, if there is better path found.

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

      I've just known that some of the solutions implement BFS using deque instead of a queue, which allows them to keep the queue monotonous. Then the complexity is the same as a standard BFS — O(V + E), which is correct. However, I do think those solutions using queue is hackable, but there might not be anti-SPFA tests.

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

Div2 D Time depends a lot on Compiler, same solution in c passed and c# TLE

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

It's possible to pass Div2 D using shortest path if you use a faster heap in C++... http://codeforces.com/contest/1064/submission/44318340

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

How to solve Div2 F? Can this problem be solved with binary search?

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

Can anyone tell me why i am getting runtime error on pretest 8 44315444 Please help i am not getting the mistake

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

Hey, ch_egor MikeMirzayanov _kun_, my submission 44312315 gave TLE during contest, but identical submission 44320638 gives AC now. Can anything be done about it?

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

    Nothing can happen now. Same thing has happened with me twice, but they don't re-evaluate our code after the contest. See the codes 37815677, 37820871. They are identical but one gave TLE during system testing while the other one passed after the contest. I also posted about it in a comment, but no one even cared to reply. I also messaged Mike on CF, but he also just ignored the message. Here is the link for the discussion.

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

    Dude, your identical submission also nearly TLE'd. So the TLE during the contest seems reasonable. There is no reason to judge your solution again.

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

shorest solution I ever encountered:

input();print(''.join(sorted(input();input())))
»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The problem C in Div.2 is amazing!!!!!!

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

what is this c

ugh

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

Is it possible to get the complete input for test #10 in div2D? I'm really curious what I did wrong in #44322132 and can't get it...

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

BFS with one queue is fine for div2 D: 44322392

»
5 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

Thank you for pretests, GreenGrape

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

    Joke’s on you, but I was involved only in d1F.

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

      You stole my rating and now you’re trying to steal my contribution

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

        Funny, its the first time i have seen author trolling the participant xD

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

So much math.

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

Test 40 for Div2-D be like

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

How to solve Div 2 B i didn't able to find the approach

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

    Brute force solution for a from 0 to 20 and try to find a connection between a and the answer

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

      This is a good tip in general, it's way easier to prove if something in particular works (or doesn't) rather than finding the solution itself

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

    just observe that since

    If i'th bit of a is 1, then if i'th bit of x is 0 or 1, in both cases i'th bit of is 1, and we are safe.

    But if i'th bit of a is 0, then i'th bit of x must be 0, i'th bit of will be 2,i.e, greater than 0. which will make greater than a.

    hence the answer is

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

      Oh my god!

      I was just thinking what will I do with the minus sign in . Just that if I did I would have seen it. :(

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

      But in case when ith bit of a=0 and x=0,

      will also give 0 which is equal to a right?

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

        Yes, that's the point, if i'th bit of a is zero then i'th bit of x must be zero.

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

        I made little mistake in my statement, edited that now !!

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

DIV1 B:

Suppose, system tests are weak.

Solutions: 44298986 44296043 Test:

3 3
1 1
1000000000 1000000000
.**
***
**.

Solutions have different answers: "1" and "2"("1" is correct answer).

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

In Div2 C,Can Anyone explain why the sorted String is the best answer.

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

Hello, could you throw a link to the analysis of this round

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

Nice Contest overall! Thanks Codeforces.

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

T̶h̶e̶r̶e̶'̶s̶ ̶p̶e̶o̶p̶l̶e̶ ̶a̶s̶k̶i̶n̶g̶ ̶f̶o̶r̶ ̶t̶h̶e̶ ̶e̶d̶i̶t̶o̶r̶i̶a̶l̶.̶ ̶T̶h̶i̶s̶ ̶i̶s̶ ̶t̶h̶e̶ ̶e̶d̶i̶t̶o̶r̶i̶a̶l̶.̶ ̶I̶ ̶g̶u̶e̶s̶s̶ ̶t̶h̶e̶ ̶a̶u̶t̶h̶o̶r̶ ̶f̶o̶r̶g̶o̶t̶ ̶t̶o̶ ̶l̶i̶n̶k̶ ̶i̶t̶ ̶h̶e̶r̶e̶?̶ ̶

̶h̶t̶t̶p̶s̶:̶/̶/̶c̶o̶d̶e̶f̶o̶r̶c̶e̶s̶.̶c̶o̶m̶/̶b̶l̶o̶g̶/̶e̶n̶t̶r̶y̶/̶6̶2̶4̶5̶5̶

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

    I was busy and came home a few minutes ago.

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

      Sorry I didn't realize editorial and announcement authors were different people

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

Sorry for this, but can anybody tell me how to view others code in gym? Maybe I need high rating or anything else? And I can't find any announcement about it.

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

can someone explain why my solution for D is wrong?

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

I'm getting TLE when I'm not using if(visited[x][y]) continue; // for checking whether the node is visited before or not here is my code link https://ide.geeksforgeeks.org/bcROnzM4qJ

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

    It's possible for BFS (0-1 variant too) to have repeats of same element in (de)queue, so this is actually to be expected.

    For example, try drawing a "triangle" graph (three node cycle) to convince yourself. You will see that two of the nodes repeat.

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

Where are the winners?

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

i am looking for its tutorial.

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

....................................

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

1654605415065460

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

can anyone help me with div2. D i tried floodfill but it got WA on test case 5

my approach now is to BFS but i get WA in test case 40 https://codeforces.com/contest/1064/submission/44454781

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

How to solve div 2 F? Will there be tutorial?

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

Can anyone please explain Problem B in div2?