Блог пользователя ch_egor

Автор ch_egor, 6 лет назад, По-русски

Всем привет!

В воскресенье в Москве пройдет шестнадцатая Московская командная олимпиада — командное соревнование для школьников, проходящее в Москве как отборочное соревнование на ВКОШП. Над туром работала Московская методическая комиссия, известная вам также по Открытой олимпиаде школьников по программированию, Московской олимпиаде для 6-9 классов и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507).

Раунд состоится в 13:05 14 числа и продлится 2 часа. В каждом дивизионе будет предложено по 6 задач.

Задачи соревнования подготовлены vintage_Vlad_Makeev, Glebodin, Andreikkaa, qoo2p5, mingaleg, Flyrise, cdkrot, achulkov2, grphil, Sehnsucht, Aphanasiy, Sender, DebNatkh, GreenGrape под моим руководством, а также GlebsHP, meshanya, Endagorion, Zlobober и Андреевой Е. В.

За координацию раунда и перевод условий спасибо cdkrot, а так же MikeMirzayanov за системы codeforces и polygon, который использовался при подготовке задач этой олимпиады.

Всем удачи!

UPD1: Разбалловка:

500 — 10001000 — 1500 — 2000 — 2500 для div. 1.

500 — 1000 — 1500 — 20002000 — 2500 для div. 2.

UPD2: Разбор

UPD3: Победители:

Div. 1:

  1. mnbvmar
  2. bmerry
  3. jcvb
  4. TLEwpdus
  5. WA_TLE

Div. 2:

  1. Ebola_Emperor
  2. Orange_User
  3. orbitingfIea
  4. little_waxberry
  5. fnch
  • Проголосовать: нравится
  • +194
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится -52 Проголосовать: не нравится

will it be rated for any division?

»
6 лет назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

Unfortunately clashes with GP of Korea.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

unfourtunately that's on my school time :(

»
6 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +68 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Немного странно, что в анонсе не было указано, что участники МКОШПа должны воздержаться от этого раунда. Или МКОШП и раунд проводятся в одно и тоже время?

»
6 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Perfect time for Chinese users!

»
6 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

GL&HF

»
6 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

hope not a mathforces

»
6 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Really bad time for US users :(

»
6 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Perfect time for Chinese users.Thank you Codeforces!

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The site has slowed down significantly.

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Div2 D pretest 13?

»
6 лет назад, # |
  Проголосовать: нравится +91 Проголосовать: не нравится

Interactive Problem and Binary Search again.

»
6 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

What were the hacks on Labyrinth about?

  • »
    »
    6 лет назад, # ^ |
    Rev. 10   Проголосовать: нравится +25 Проголосовать: не нравится
    Input
    Output

    for those who used a single queue.

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Then my D will fail systest

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      I am using single queue but i pass this test

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Lol?

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

      Could you elaborate on why was that supposed fail?

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        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)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

CSAcademy saved me on E with the geometry tool.

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +61 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +83 Проголосовать: не нравится

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

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    what is the correct approach to this problem?

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится +53 Проголосовать: не нравится

      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.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Deque is enough, thought

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится +13 Проголосовать: не нравится

            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

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -139 Проголосовать: не нравится

I am eblan.

»
6 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

whats the correct approach for div2 d?

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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?

»
6 лет назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

how to solve F?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +34 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      It won’t :(

      Try to replace binary search with some monotonic observation.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -17 Проголосовать: не нравится

Time limit for Problem D is too strict :(

»
6 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

How to solve Div1 D?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What’s pretest 10 in div 2 E?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Probably something like 1 black and 29 white.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yeah I was getting wrong answer on pretest 10

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

      I am trying to understand this formula you stated.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 ?

»
6 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

gag forces?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

So that i upsolve after that :)

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +73 Проголосовать: не нравится

    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!

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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()
    
»
6 лет назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

Test 40 Div2D distroyed so many dreams :(

»
6 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

weak pretests in div2 D

»
6 лет назад, # |
  Проголосовать: нравится +63 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    Impossible

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's Test 27 in Div2 D?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

44306721

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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

»
6 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

How to solve Div2 E??

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Sixth sense!

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I manually checked it for random strings of length 10

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

where is the editorial?

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

shorest solution I ever encountered:

input();print(''.join(sorted(input();input())))
»
6 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

what is this c

ugh

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

BFS with one queue is fine for div2 D: 44322392

»
6 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

Thank you for pretests, GreenGrape

»
6 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

So much math.

»
6 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Test 40 for Div2-D be like

»
6 лет назад, # |
  Проголосовать: нравится -67 Проголосовать: не нравится

Моё решение 44312339 по задаче 1064B значительным образом совпадает с решениями других участников и находится в группе одинаковых решений Alexey01/44312143, Elisey_Muxin/44312339, the_stig/44312467 так как я и эти 2 участника соревнования решали задачи вместе. Мы думали, что если олимпиада командная, то можно решать задачи вместе. Мы можем это легко доказать, если это потребуется.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Олимпиада не командная, а проводилась по задачам командной олимпиады. Если бы она была командная, то была бы доступна командная регистрация. В самом деле, глупость какая-то предполагать, что могут решать команды из под какого-то одного аккаунта (и рейтинг изменится только у него). Отмечу, что регистрируясь вы подтвердили соглашение, в котором написано "не используете несколько аккаунтов, а в соревновании принимаете участие со своего личного и единственного аккаунта". Короче, на лицо явное нарушение правил. Пользователю Alexey01 я тоже засчитаю нарушение и выброшу его из рейтинга.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      will also give 0 which is equal to a right?

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Nice Contest overall! Thanks Codeforces.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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̶

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

Ну не bad такой контест вышел

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Where are the winners?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.net/contest/1064/submission/44454781

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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