rng_58's blog

By rng_58, history, 5 years ago, In English

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!

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

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +82 Vote: I do not like it

Your contest names are dope.

»
5 years ago, # |
  Vote: I like it +36 Vote: I do not like it

How to solve E?

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

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

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

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

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

      Spoiler

      I tested like this. Am I missing something?

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

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

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

Can someone provide a good test case for D?

»
5 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

How to solve D?

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

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

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

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

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

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

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

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

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

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

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

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

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

»
5 years ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

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

    I think that might require a bitmask solution, not sure though.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C?

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

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

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

  • »
    »
    5 years ago, # ^ |
    Rev. 5   Vote: I like it +12 Vote: I do not like it

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

      There must be exactly K occurrences of '#'.

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

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

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

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

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

      Thanks a lot.

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

      UPD: uploaded now.

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

        Thanks!I have finished all the problems after the contests,but I can only solve 3 problems during the contests.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +38 Vote: I do not like it

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

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

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

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

I wonder how to write the checker for problem C?

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

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

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

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

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

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

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

      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.