MikeMirzayanov's blog

Mirror of ACM-ICPC NEERC Southern Subregional Programming Contest 2011 (Saratov QF)
By MikeMirzayanov, 12 years ago, translation, In English

Hello!

Today, October 23 (Sunday) at 08:00 (UTC) will begin online contest based on recently completed ACM-ICPC NEERC Southern Subregional Programming Contest 2011. Two days ago a competition was held in Saratov (hosted by Saratov State University), but today you can participate in it informally. Onsite participants will in the standings, to give you an oppotunity to compare your results with onsite teams. The statements will be available as a PDF-file and in HTML. To participate, go to the site http://acm.sgu.ru.

After the contest, you may discuss here the problems. I hope you'll like them.

Chairman of the Jury,
MikeMirzayanov

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

12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can someone explain how to approach C ?
→ Reply
  • 12 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it
    ans = 0;
    for seg1 in vertical segments
        for seg2 in vertical segments (index of seg2 > index of seg1)
          {
             curCnt = 0;
             for seg3 in horizontal segments
               if seg3 intersects seg1 && seg3 intersects seg2 
                 curCnt++;
            ans += curCnt*(curCnt-1)/2;
          }
    print ans
    → Reply
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anyone explain the tricks in problem H?
I tried the following approach: For each character, constructs a number with digits 0 & 1. The i-th digit is 1 if the i-th character of input string = current character
e.g. aabbaa --> number 110011 and 1100
Result = divisors of GCD(all generated number, and one possible number created by mapping the input string to a valid number)
I found a special case when all 10 digits appear and input string's length = 10. In this case, output should be 1 3 9
Did I miss any cases, or is my algorithm wrong?
Thank you for reading this :)
→ Reply
  • 12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    for testcase aaaabcdefghij answer is 1 3
    in the all rest you are right
    → Reply
    • 12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Thanks a lot :)
      I was doing that problem for hours and couldn't think of that case :(
      → Reply
  • 12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it
    If the number of different letter =10, there are only three cases. First is abcdefghij. gcd is 9. 
    Second case is aaaabcdefghij, gcd is 3, and other similar variants of this string.
    In all other cases answer is 1. Let prove it. There is 2 neighboring position, where the letters in this position occur in this world only once (Dirichle principle for string no more than 14 symbols). Let put to this position 1 and 2 alternately and other position let assign random numbers. Then the different between this two numbers is 9*10^k. And it is clear that the string not divisible by 2, 5, 3.
    → Reply
  • 12 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    How can you know that brute-force is too slow for this problem?

    I only see 10! different possibilities, and at each possibilitie you just calculate the gcd with the previous gcd. Is the gcd operation (euclidian's way) to slow for this strategy?

    → Reply
    • 12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      brute is really slow, don't forget that there is 100 test cases in this problem. 
      → Reply
    • 12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I also got accepted using brute force algorithm :)
      Just break after finding around 10^5 numbers. The calculated GCD should be good enough
      → Reply
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Thanks for explaining, I was thinking of O(n^4) .
And how to approach the Berland Chess problem, constraints says solution will be exponential, but looks too complex for me, please elaborate.
→ Reply
  • 12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I used dynamic programming. f(i,j,S) = minimum move if the king is in cell (i,j) and need to capture all opponent's pieces in set S.
    The number of states is quite big. I moved to only opponent's pieces' location to minimize the number of state.
    → Reply
    • 12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Can you tell what exactly will S contain? And if possible give link to your solution.
      → Reply
      • 12 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        S is a bitmask, i-th bit = 1 if we need to capture the i-th opponent's piece, and i-th bit = 0 if we already captured the i-th opponent's piece
        I don't have my code now. I have a bad habbit: deleting my code after got accepted =)
        → Reply
        • 12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Okay,  now to move from one state to another, we need to check whether the *king* can move to that state or not, how did you check that? , I will need O(15*15) for that, is there any simpler way to check whether next state is reachble or not ?

          [nice habbit btw. :) ] 
          → Reply
          • 12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            I pre-calculated that, but it was to simplify my dp function. I think it wasn't necessary in terms of complexity since the number of states is quite small. I even used O(N*N) to calculate the distance to every cell at each state (i,j,S).
            → Reply
            • 12 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              dp will have (2**15)*15*15 states right?
              I guess you are telling it will be lesser, but how?
              → Reply
              • 12 years ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it
                Number of states = 2^15 * 15 since I only moved to opponent's pieces' location. It was small enough :)
                → Reply
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
what's the idea for multiswap problem?

→ Reply
  • 12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    For any array number of steps does not exceed 2.
    → Reply
  • 12 years ago, # ^ |
    ← Rev. 4   Vote: I like it +3 Vote: I do not like it

    Magic.

    It's proofable that any array can be sorted in no more than 2 multiswap operations.
    If array is sorted, answer is 0.

    Now, let's suppose that all numbers in array are distinct. So, we can consider this array as some permutation. Have a look at graph representation of this permutation.

    Answer is 1 if this graph contains cycles only with length no more than 2 (we can swap elements of this cycles and sort array this way).

    If there is at least one cycle of length more than 2, answer is 2. You can notice that swapping two elements of some cycle, divides this cycle into two cycles. This way by one multiswap operation you can divide any cycle into cycles of length no more than 2. goto previous paragraph.

    If not all numbers in array are distinct, we can enumerate all identical numbers as consecutive distinct numbers, and apply algorithm above, so we can still sort array in no more than 2 operations. But not any enumeration will form permutation which requires minimal possible amount of operations for sorting. So, I don't know, what exactly should we do if not all numbers are distinct.

    → Reply
    • 12 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Exactly - try to use greedy matching for sorting in one step, if this fails and two steps are required, you can assume that this is a permutation and use the solution above.

      → Reply
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In problem B I am getting WA on case 8. In i-th index of an array m[] I am storing the maximum amount found in bank i and all banks after i. Then for each bank I am doing a binary search to find the next suitable bank after current and taking the maximum. Code is here. Please help.
→ Reply
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Please help me with the problems here.
I am trying to avoid double posting. Thanks.
→ Reply