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

Автор rng_58, история, 5 лет назад, По-английски

We will hold DISCO Presents Discovery Channel Code Contest 2020 Qual.

The point values will be announced later.

We are looking forward to your participation!

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

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

Last line of the registration says "I read all statements.". No, I didnt, or more specifically, I couldnt.

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

Your contest names are dope.

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

How to solve E?

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

    Use binary search on a sequence to find two adjacent segments which differ exactly one element and have different majority color.

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

    Ask for the first $$$n$$$ balls, say color $$$x$$$ appears more. Then binary search some position such that in the balls $$$i, \dots, i + n - 1$$$ the other color appears more, and in $$$i-1, \dots, i+n-2$$$ $$$x$$$ appears more. Note that in the last $$$n$$$ balls the other color must appear more, so at least one such transition point exists. If at $$$i, \dots, i + n - 1$$$ color $$$x$$$ appears more, then at least one transition point must occur between $$$i$$$ and $$$n$$$. If the other color appears more, then at least one much appear between $$$0$$$ and $$$i$$$. So we can find such a position in $$$1 + \log_{2}(100) \approx 8 < 10$$$ operations.

    But now we know that - Ball $$$i-1$$$ has color $$$x$$$, ball $$$i+n-1$$$ has the other color - Hence both colors appear an equal number of times in $$$i, \dots, i+n-2$$$ - Hence both colors appear an equal number of times in $$$i+n, \dots, i-2$$$ (where the interval wraps around $$$2n$$$)

    Now we can ask for every ball $$$j$$$ either the query with $$$j$$$ and interval $$$i, \dots, i+n-2$$$ or with $$$j$$$ and interval $$$i+n, \dots, i-2$$$. Since the intervals contain the same amount of both colors, the answer will be the color of ball $$$j$$$.

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

      I test your code and think that it fail on this testcase.

      Spoiler

      I tested like this. Am I missing something?

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

        Looks like askEq doesn't count the character at position $$$i+1$$$. I went through that test case by hand and my code did give the correct answer:

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

          Oh, that’s strange. I thought that the test cases might be weak because my code gave wrong answer with that test case too. Turned out that I was wrong. I tested by hand and it did give correct answer too. I’ve tested many submissions, but I found only your codes having the same issue. I still don’t get the reason.

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

Can someone provide a good test case for D?

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

In D, beware of taking mod 9.......Its a terrifying mistake, took 1 hr for me to correct. Here if anyone wants to refer to my solution : https://atcoder.jp/contests/ddcc2020-qual/submissions/8586574

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

How to solve D?

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

    As much as i could find, the order of combinations matter very less in this question, so for me it was a matter of finding answer to input sets fast and combining them (HINT : FAST EXPONENTIATION)...

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

    We can show that the order or operations we is the same as the optimal if we keep combining the first 2 digits of the number. (I didnt prove this but it seems to work). Let's see how we can find the number of time we need to combine the first 2 digits.

    Firstly notice if we were to keep combining with some number (for example 4), we will get a cycle. 4->8->12->3->7->11->2->6->1->5->9->13->4

    We can work out the cycles for all these numbers by hand. Then when we see alot of repeated digits we can quickly remove alot of them because they cycle.

    I think you just need to be careful with 0 and 9. Since they cycle into them selves.

    code: https://atcoder.jp/contests/ddcc2020-qual/submissions/8584626

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

      The order doens't matter. In each operation, the number of digits decreases by one or the sum of digits decreases by nine, so the value (number of digits * 9 + sum of digits) always decrease by 9.

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

        This is great!

        But, how to think about that particular quantity ( $$$9*digits + sum$$$ ) during the contest?

        I was trying to check / prove if order matters, but couldn't think of anything. I guess I go about it wrongly, thinking of mathematical proof directly. Maybe I should've tried out a few examples by hand.

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

        But why is this value (digits*9 + sum) important. How does ensuring that this value remains maximum possible , gives the optimal solution.

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

    During one operation, the number of digits decreases by one and the sum of digits stays the same or the number of digits stays the same and the sum of digits decreases by 9. So the number of rounds is something like digitCount - 1 + (digitSum-1)/9.

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

      ll r = DC-1 + (S-1)/9;

      Could you tell me why will this give the number of operations to be performed?

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

        Since, digitCount-1 operation has to be performed. For the other part i.e (S-1) when the sum of all digits would exceed the value of 9, you would need another round. So, this explains why S/9 is done. For "-1" in S, it done in order to cut the corner cases where S == 9*m, i.e S is multiple of 9. Let's say S = 18(excluding DC), then only one round would be required, but if we go by the formula of S/9, the number of rounds would be 2.

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

Problem C is very similar to this problem from GCJ 2017 Round 1A

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

Could any one please tell how to solve Modified version of C…. i.e. what is total number of such partioning ?? (satisfying given condition.)problem_link_C

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

How to solve C?

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

    Consider it as a implicit graph problem
    In a matrix whenever you find '#' and mark it something starting from 1 then run a dfs in a matrix till you reach the either end of that row or you find '#' in the row and mark them the same number you marked the '#'. So for k '#' you use only k numbers.
    So if you have some matrix like
    3 3 3
    ..#
    .#.
    .#.
    then after 3 dfs calls from (1,3),(2,2),(3,1)you get something like this
    1 1 1
    2 2 2
    3 3 3
    Now the edge case is
    3 3 1
    ...
    ...
    ..#
    Now you will get something like
    0 0 0
    0 0 0
    1 1 1
    So use the trick that if ans==0 or if you have taken it -1 or some number then you must find the next non-zero number or previous non zero number in the column and you need to do it for every column
    Code
    https://atcoder.jp/contests/ddcc2020-qual/submissions/8582555

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

In which case my solution of C is wrong?? https://atcoder.jp/contests/ddcc2020-qual/submissions/8580853

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

    Actually nevermind, i read didnt read the k=# will still try to find cornercase

    3 1 1
    .
    .
    #
    

    I think i found the test case

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

      There must be exactly K occurrences of '#'.

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

      Hi, the issue with the code is about certain empty rows. Your output is:

      -1
      -1
      1
      

      If you look at your code at lines 74 to 90, what you have done is for an empty row at i, check the row below if it is empty, and copy the values if it is not empty. For some reason, it doesn't check if the row above is empty and copies it regardless.

      So in this case, when you process row 0, it's empty, but row 1 is also empty, so it doesn't copy the value, and you'd get -1 for the row 0. As for row 1, you copy the value from row 2, but then again you copy -1 from row 1, so it ends up as -1.

      To fix it, you probably have to check if the row above is empty. Also, you should repeat this "copying" step many times to ensure that all empty rows are eventually reached.

      (Edit: errorgorn advised me to use a block for the output. Sorry I'm new to CF comments)

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

I would like clarification for why one of my submissions doesn't work for C. Here are too different submissions i wrote with exactly the same code except for how I inputted and outputted:

https://atcoder.jp/contests/ddcc2020-qual/submissions/8584045 and https://atcoder.jp/contests/ddcc2020-qual/submissions/8587572

I figured out the second one worked because I inputted a character at a time instead of a whole line. Why is this the case?

(Edited because I originally thought it was a different status for a different reason)

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

When the English editorial will be available ? Actually I want to know the solution of F. Seems like there is a detailed editorial but only in Japanese .

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

    Sorry for delay, sometimes we can't finish editorial translation in time.

    For AGC/ARC rounds (including this round) we'll publish English editorials.

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

    Idea for F: Firstly, let $$$ga = \gcd(H, T), gb = \gcd(W, T)$$$. Then, we can partition the grid into $$$ga \times gb$$$ independent parts, and thus from here on we let $$$\gcd(H, T) = \gcd(W, T) = 1$$$ (by appropriate scaling) and raise the answer to the $$$ga \times gb$$$-th power.

    The main idea is the consider when a board is invalid. Since $$$\gcd(H, T) = \gcd(W, T) = 1$$$, we have that for each row, we cannot have both R and . (or else by Bezout's Lemma there exist a time they will coincide). Similar result holds for each column.

    Suppose our grid only has R or D but not both. Then, it is easy to count the number of valid grids: it's just $$$2^{H} + 2^{W} - 1$$$ (it is easy to see all such grids work).

    Suppose our grid has both R and D. Note that if the R and D have coordinates $$$(x_{1}, y_{1})$$$, $$$(x_{2}, y_{2})$$$ respectively, then we cannot have $$$x_{1} + y_{1} \equiv x_{2} + y_{2} \pmod{G}$$$, where $$$G = \gcd(H, W)$$$ (you can prove this by writing out exactly when an R and D will coincide for some time $$$kT$$$). Furthermore, you can prove that if a . exist, then the grid cannot contain both R and D. Hence, for each remainder mod $$$G$$$, we must have at least one of R and D. Also, R and D must both appear. Thus, the number of ways is $$$2^{G} - 2$$$.

    Combining the two cases and raising the power by $$$ga \times gb$$$ gives us the answer.

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

      Hence, for each remainder mod $$$G$$$, we must have at least one of R and D.

      This should be "Each diagonal mod $$$G$$$ should contain only R or D", am I right?

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

        Well ya it's pretty much each diagonal mod G since I'm looked at $$$x+y$$$ mod $$$G$$$.

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

I wonder how to write the checker for problem C?

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

    exactly! me too. I think the checker itself will be a solution of the problem

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

      Not exactly. Think about the following subproblem:

      You are given a set of cells of $$$R \times C$$$ matrix. Check if the set forms a rectangle.

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

Hi rng_58, it's just a little feature request. Can you please consider compiling programs on AtCoder with the macro ONLINE_JUDGE defined. Many of the international judges use it like codeforces, codechef, UVa, Spoj, HackerEarth, etc. My original template relies on this macro to read from the input file locally, and I believe there might be other people too that use this feature. Although, I tend to change my template slightly before the contest by defining a custom macro in the local environment, I do think that having this feature will be helpful, as I can have the same template across all the judges that I mentioned earlier. Thanks.

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

    You can use #ifndef LOCAL_DEBUG instead of #ifdef ONLINE_JUDGE and add -DLOCAL_DEBUG option every time when compiling.

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

      It's actually just a request. As I said in my previous comment, I do define a custom macro in the local environment while writing solutions for AtCoder, but I do find the ONLINE_JUDGE thing helpful as the program will work on my machine, even if I have to switch to some other IDE. Thanks anyways.