Madiyar's blog

By Madiyar, 10 years ago, In English

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

Let's discuss here problems after the contest.

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

| Write comment?
»
10 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Don't oversleep this round :)

»
10 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

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

    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 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      But in 250 there are more possibilities for stupid bugs.

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

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

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

          it looks like many 250 solutions failed challenge or systests, unlike 500, natalia was right

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

            What's your topcoder handle, buddy?

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

              alliumnsk. Why do you care?

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

                You didn't solve the 500-pointer and claim it was easier than 250.

                Looks funny, you know :)

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

                  500 pts comes after 250 pts. Could you stop mocking me please?

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

                  kill yourself

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it +12 Vote: I do not like it

          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 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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 years ago, # ^ |
      Rev. 2   Vote: I like it +16 Vote: I do not like it

      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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

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

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        Yes, backtracking is brute force.

        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks mate!

        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                • 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 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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 years ago, # |
  Vote: I like it -11 Vote: I do not like it

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

»
10 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Any ideas how to solve div1 1000?

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

    I guess it is 2-sat ...

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

    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 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      System tests are weak then — I successfully challenged your solution

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              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 years ago, # ^ |
                Rev. 2   Vote: I like it +8 Vote: I do not like it

                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 years ago, # ^ |
                    Vote: I like it +8 Vote: I do not like it

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

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

    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 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.