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

Автор Madiyar, 10 лет назад, По-английски

Single Round Match 630 will be held at 05:00 Fri Moscow time.

Let's discuss here problems after the contest.

  • Проголосовать: нравится
  • +79
  • Проголосовать: не нравится

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

Don't oversleep this round :)

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

а как решать 500?

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

    Посмотрим 2 соседних позиции в суфф массиве. Пусть это a и b. Тогда если a + 1 стоит в массиве раньше, чем b + 1, то мы можем поставить на эти позиции одинаковые символы, а если нет, то обязаны поставить разные. Ответ — сколько раз надо поставить разные + 1

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

500 Div1 is easier than 250, isn't it?

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

    If you notice the trick — medium is obvious. If you do not — you are screwed. And coding is not really much harder for 250

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

      But in 250 there are more possibilities for stupid bugs.

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

        I don't think so. IMO, in topcoder problems should be compared by the underlying ideas to solve them. 250 was pretty straightforward

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

        And much less possibility to not to come up with soluiton at all. Considering n = 1 case is covered in samples I am really puzzled by number of failed submissions. Both ones I challenged have incorrect solution, not a bug in correct one

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

          There is a trick I intended to left uncovered by examples: if the answer is 2, then it don't have a center like answer >= 3 cases.

          When we test this problem, rng_58 don't think this could be a trick, but in fact some people failed by initialize answer to 1 instead of min(n, 2).

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

            I fell in that trick, too. I've thought of the answer==2 case but forgot to put it in my code until it was too late.

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

              I used a different approach: enumerate all pairs, calculate the midpoint, and use that midpoint as center.

              But later I discovered that if the center is not a vertex, answer is 2. So I was just make things more complicated...

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

      If you don't — you can always try some DP :)

      We actually can make DP on prefix. Let R[i] be the answer for prefix i. We should try for the positions SA[i], SA[i+1], ..., SA[j] assign some next letter. The only thing that we should do is to check whether it's possible or not.

      So, you have to compare strings of type like "x<>x>...", "xx>>x<..." and so on. Here 'x' denotes the current character, '<' donotes some previous character, and '>' denotes some future character. There's no problem in comparing 'x' and '<', '<' and '>', and others. The problem is to compare one '<' and with another '<', or '>' with '>'. But actually it is easy to compare them because they are already compared in the input :)

      The code is pretty short and simple, but I guess the other idea is quite better.

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

      What is the trick? I can't figure it out...

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

        I think it is that the lexicographically smallest string will have the minimum number of required character changes.

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

    It depends. I found that 250 was pretty straightforward and came up with the right approach right after I finished reading the statement. The implementation might be a bit trickier than usual, hence it could be set as 275 or 300. For 500, I struggled to find a decent solution and gave it a try with a fairly naive one (keep decreasing the elements if it's still possible). That makes 500 the harder one for me.

    (btw, I assumed that nodes were numbered from 0 to N - 1, which resulted in a resubmission and very low point for my 250)

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

    if you are right, why only 92 user have solved 500 div1, and 192 person solved 250?

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

Very strange to see the same code Failed at contest and Passed on practice system test and also on the webpage I see that
Expected Results "Exists"
FAILED — Result: "Exists"
I think there are something wrong ,hope I get a reply.

http://community.topcoder.com/stat?c=problem_solution&rm=323315&rd=16061&pm=13287&cr=22882911

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

Given a suffix array. Is it possible to find the lexicographically smallest string that satisfies that array?

I was trying something like this for div2 1000, but couldn't came up with any correct idea to find the lexicographically smallest string for a given suffix array...

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

    In fact "find the lexicographically smallest string", "is that string lexicographically smallest", "how many different characters do we need" can be solved by same way.

    I don't know which one is easy and which one is hard, but there is one reason for using "is that string lexicographically smallest" as Div2-Hard: the algorithm "change one character (decrease by 1 if it is not 'a') and check if the SA remains same." can pass, and I thought some people can come up with it.

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

      yep exactly the same algorithm I used & it passed after running system test again

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

Can someone explain me the right approach to Div.2 500 (or at least give some hint)? My idea was to use Floyd-Warshall's algo, but then I wasn't able to figure out what to do next and got stuck.

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

    Try every subset of nodes (backtracking) and check if they meet the condition.

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

      Well, I understand, but... I've got one new question now: is bruteforce and backtracking the same thing ? Because I don't know much about backtracking, but I would call this approach bruteforce =D

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

        Yes, backtracking is brute force.

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

          Thanks mate!

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

          Can you explain this part of solution for Div2 500. Coder was using mask, how does it help us, why do we need mask at all, not just in this solution?

          for (int mask = 0; mask < (1 << N); mask++) { list.clear(); for (int j = 0; j < N; j++) { if ((mask & (1 << j)) != 0) { list.add(j); } }

          Thank you

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

            You can do backtracking using bitmasks. You try every configuration of N bits (from 0 to 2^N — 1). When the bit j is set it means that node j is chosen.

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

              Let N be equal to 3

              Then the result is: 1 0 2 1 3 0 3 1 4 2 5 0 5 2 6 1 6 2 7 0 7 1 7 2

              This first column shows mask, the second j. I did not get what these two columns show. As I understood mask shows the number of all subsets of N, so it must be equal to 2^N. That's why in our case it equals to 8, but what does second column show? Is my thinking going in right way?

              Thank you

              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                • 1 0
                • 2 1
                • 3 0
                • 3 1
                • 4 2
                • 5 0
                • 5 2
                • 6 1
                • 6 2
                • 7 0
                • 7 1
                • 7 2
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Let's take 5 = 101. This means that in this case we consider the set {0,2}. For 6 = 110 we consider {1,2}. And so on.

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

How to solve div.1 500? Sorry that I'm not familiar with string suffix structures.

I just saw many solutions get 490+ points and I guess it will be very tricky.

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

hey all the genius plz help me Need Help here. Link is http://codeforces.net/blog/entry/13505

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

Any ideas how to solve div1 1000?

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

    I guess it is 2-sat ...

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

    The official solution involves 2-SAT, however there was another brute-force-like solution, which passed system test and was working several times faster than the intended one on all test cases we've tried. Unfortunately, we don't know neither how to prove it or how to break it. I think cgy4ever can describe his 2-SAT solution better than me, so I'll describe mine. Maybe someone can prove it or provide a counterexample.

    The idea is quite simple. Let's maintain the minimum and maximum possible value for each variable. At the very beginning they are [1, 100] for all N variables. On each step of the recursion we do the following:

    1) Output the answer if all intervals have length 1.

    2) Repeatedly try to shorten each interval if its ends are conflicting with some other intervals. Stop when we can't change any interval without making any assumptions (i.e. we cut intervals' ends only if we know they conflict with other intervals without making any guesses and going deeper into recursion).

    3) If after the previous procedure some interval has length 0, go out of the recursion.

    4) Take any interval that has length greater than 1 and try to fix the corresponding variable's value (i.e. iterate over all values from its interval). When we fix it's value to X, replace its interval by [X, X] and make recursive call (i.e. go to 1).

    5) Output {} if the recursion didn't find any answer.

    The reason why I think it works is following. I tried to run it against a lot of random test cases and couldn't find any single one where we should go out of the recursion at least once (except for the ones in item #3 in the list above). That's why I suspect it makes exactly N recursion steps and on each one it fixes one variable.

    UPD: I've submitted it to the practice room and its maximum running time is 68ms.

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

      System tests are weak then — I successfully challenged your solution

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

        Cool, fortunately there were no submissions like this during the contest.

        Actually, the original version of my solution had one more optimization: on each recursion step I was choosing the shortest interval among those with length greater than 1. But later I've noticed that even without this it passes system test, so I removed it from the code. Does your test case breaks this version as well? If yes, could you share the test case?

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

          Yes, my test case should break this version too: n=100, x99-x100=0, x99+x100=3

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

            Oh well, I only considered test cases where the answer exists. Of course, it's possible to add something like 'if clock() > 1.85 return {}', but this is kind of cheating and it will make the solution ugly.

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

              x1+x100>=51
              x99-x100=0
              x99+x100<100

              x1+xi>=52 for 1<i<99 (if you have an interval length optimization).

              For this test answer exists, but your solution will still fail on it.

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

                Why should it fail on this test case? After it fix the first variable to [1, 1] and go to the next step of the recursion, it'll first shorten the 100th interval to [50, 100], then the 99th interval to [50, 100] and then it'll notice an error and will return to the previous level. That's because the 2nd step is being applied repeatedly, until no changes are possible.

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

                  I see.. Looks like if answer exists, your solution is equivalent to 2SAT

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

    Yes, the intended solution is 2-SAT.

    For each x[i], we add 99 variables to the 2-SAT system: (x[i]>=2), (x[i]>=3), (x[i]>=4), ..., (x[i]>=100). And we have: (x[i]>=100) -> (x[i]>=99), (x[i]>=99) -> (x[i]>=98), ...

    Then what is amazing is that all conditions can be described in this 2-SAT system. For example if we have x[1] * x[2] >= 50, then it can described as (x[1]<2) -> (x[2]>=50), (x[1]<3) -> (x[2]>=25), (x[1]<4) -> (x[2]>=17), ....

    And you need to think about how to handle these 20 different cases: 4 operations * 5 relations.

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

Can anyone please explain the solution for Div 1 500? I saw many codes and they all do something like if(p[sa[i]+1] > p[sa[i-1]+1]) ans++;, where p[i] marks the position of i in the suffix array. I don't have the faintest idea why that would work and I'm feeling really stupid now. Is it really that obvious?

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

    No, that need some insights, but you don't need to know some advanced knowledge about suffix struct.

    Suppose we know that the rank of each suffix of string S is {2, 3, 0, 1}, then we know s[2]s[3] < s[3] < s[0]s[1]s[2]s[3] < s[1]s[2]s[3]. Thus we know s[2] <= s[3] <= s[0] <= s[1].

    Now we need to know if we can set s[2] = s[3] (and something like s[3] = s[0] and s[0] = s[1]): we must ensure s[2]s[3] < s[3] still holds, that means we need s[3] < "" (or, suffix[3] < suffix[4]), that is not true. So we know s[2] < s[3]. Also we can know s[3] can be equals to s[0] since suffix[3+1] < suffix[0+1].

    After that we can allocate letters into s[]. s[2] = a, since s[2] < s[3], we set s[3] = b and so on.

    And now you can see why that one line of code can work.