### rng_58's blog

By rng_58, history, 9 months ago, , 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!  Comments (48)
 » 9 months ago, # | ← Rev. 2 →   Last line of the registration says "I read all statements.". No, I didnt, or more specifically, I couldnt.
 » Your contest names are dope.
 » How to solve E?
•  » » Use binary search on a sequence to find two adjacent segments which differ exactly one element and have different majority color.
•  » » 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#include #include using namespace std; using ll = long long; const ll MOD = 1e9 + 7; int askRow(int s, int n) { cout << "?"; for (int i = s+1; i <= s+n; ++i) cout << ' ' << i; cout << endl; string res; cin >> res; return (res == "Red") ? 1 : -1; } int askEq(int i, int s, int n) { cout << "? " << i+1; for (int j = s+1; j < s+n; ++j) { if (j > 2*n) cout << ' ' << j - 2*n; else cout << ' ' << j; } cout << endl; string res; cin >> res; return (res == "Red") ? 1 : -1; } const int N = 100; int col[2*N]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; // Ask first N. Shift window right one-by-one until the answer changes. // Since last N must have opposite answer, this happens at some point. // Binary search where it happens. Note that we don't need to find the first such position. // 1 + log2(100) ~ 8 < 10 int x = askRow(0, n); // Sum of first n has more of x int low = 1; int high = n; while(low != high) { int mid = (low + high) >> 1; int y = askRow(mid, n); if (x != y) high = mid; else low = mid + 1; } // Now askRow(low-1, n) and askRow(low, n) give different answers, hence both colors appear an equal number of times in [low, low+n-2]. for (int i = 0; i < low; ++i) col[i] = askEq(i, low, n); for (int i = low; i < low + n - 1; ++i) col[i] = askEq(i, low + n, n); for (int i = low + n - 1; i < 2*n; ++i) col[i] = askEq(i, low, n); cout << "! "; for (int i = 0; i < 2*n; ++i) { if (col[i] == 1) cout << 'R'; else cout << 'B'; } cout << endl; } 
•  » » » I test your code and think that it fail on this testcase. Spoiler5RBRRBBRBBRI tested like this. Am I missing something? Code#include #include using namespace std; using ll = long long; const ll MOD = 1e9 + 7; string hidden = "#RBRRBBRBBR"; int askRow(int s, int n) { //cout << "?"; int R = 0, B = 0; for (int i = s+1; i <= s+n; ++i){ if(hidden[i] == 'R') R ++; else B ++; } //cout << ' ' << i; //cout << endl; string res = (R > B) ? "Red" : "Blue"; //cin >> res; return (res == "Red") ? 1 : -1; } int askEq(int i, int s, int n) { //cout << "? " << i+1; int R = 0, B = 0; for (int j = s+1; j < s+n; ++j) {/* if (j > 2*n) cout << ' ' << j - 2*n; else cout << ' ' << j;*/ int t = (j > 2 * n) ? (j - 2 * n) : j; if(hidden[t] == 'R') R ++; else B ++; } //cout << endl; string res = (R > B) ? "Red" : "Blue"; //cin >> res; return (res == "Red") ? 1 : -1; } const int N = 100; int col[2*N]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; // Ask first N. Shift window right one-by-one until the answer changes. // Since last N must have opposite answer, this happens at some point. // Binary search where it happens. Note that we don't need to find the first such position. // 1 + log2(100) ~ 8 < 10 int x = askRow(0, n); // Sum of first n has more of x int low = 1; int high = n; while(low != high) { int mid = (low + high) >> 1; int y = askRow(mid, n); if (x != y) high = mid; else low = mid + 1; } // Now askRow(low-1, n) and askRow(low, n) give different answers, hence both colors appear an equal number of times in [low, low+n-2]. for (int i = 0; i < low; ++i) col[i] = askEq(i, low, n); for (int i = low; i < low + n - 1; ++i) col[i] = askEq(i, low + n, n); for (int i = low + n - 1; i < 2*n; ++i) col[i] = askEq(i, low, n); cout << "! "; for (int i = 0; i < 2*n; ++i) { if (col[i] == 1) cout << 'R'; else cout << 'B'; } cout << endl; } 
•  » » » » 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: Interaction5 ? 1 2 3 4 5 Red ? 4 5 6 7 8 Blue ? 3 4 5 6 7 Red ? 1 4 5 6 7 Red ? 2 4 5 6 7 Blue ? 3 4 5 6 7 Red ? 4 9 10 1 2 Red ? 5 9 10 1 2 Blue ? 6 9 10 1 2 Blue ? 7 9 10 1 2 Red ? 8 4 5 6 7 Blue ? 9 4 5 6 7 Blue ? 10 4 5 6 7 Red ! RBRRBBRBBR 
•  » » » » » 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.
 » Can someone provide a good test case for D?
•  » » I think your solution is wrong for "1999"
•  » » » Thanks !!
 » 9 months ago, # | ← Rev. 2 →   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
 » How to solve D?
•  » » 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)...
•  » » 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->4We 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.
•  » » » 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.
•  » » » » 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.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   But why is this value (digits*9 + sum) important. How does ensuring that this value remains maximum possible , gives the optimal solution.
•  » » 9 months ago, # ^ | ← Rev. 2 →   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#include using namespace std; typedef long long ll; int main(){ ll M, DC = 0, S = 0; cin >> M; for(int i = 0; i < M; ++i){ ll d, c; cin >> d >> c; S += d*c; DC += c; } ll r = DC-1 + (S-1)/9; cout << r << endl; } 
•  » » » ll r = DC-1 + (S-1)/9;Could you tell me why will this give the number of operations to be performed?
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   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.
•  » » » » » Thank you so much!
 » Problem C is very similar to this problem from GCJ 2017 Round 1A
 » 9 months ago, # | ← Rev. 3 →   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
•  » » I think that might require a bitmask solution, not sure though.
 » How to solve C?
•  » » 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
 » 9 months ago, # | ← Rev. 2 →   In which case my solution of C is wrong?? https://atcoder.jp/contests/ddcc2020-qual/submissions/8580853
•  » » 9 months ago, # ^ | ← Rev. 5 →   Actually nevermind, i read didnt read the k=# will still try to find cornercase 3 1 1 . . # I think i found the test case
•  » » » There must be exactly K occurrences of '#'.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   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)
•  » » My solution was just failing on tc6 :D
 » 9 months ago, # | ← Rev. 3 →   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: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)
 » Are there any english editorials？
 » 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 .
•  » » Sorry for delay, sometimes we can't finish editorial translation in time.For AGC/ARC rounds (including this round) we'll publish English editorials.
•  » » » Thanks a lot.
•  » » » UPD: uploaded now.
•  » » » » Thanks!I have finished all the problems after the contests,but I can only solve 3 problems during the contests.
•  » » 9 months ago, # ^ | ← Rev. 3 →   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.
•  » » » 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?
•  » » » » Well ya it's pretty much each diagonal mod G since I'm looked at $x+y$ mod $G$.
 » I wonder how to write the checker for problem C?
•  » » exactly! me too. I think the checker itself will be a solution of the problem
•  » » » 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. AnswerFind the minimum and maximum row index, and minimum and maximum column index. Then you can find the size of "bounding rectangle" (by calculating $(maxrow - minrow + 1) * (maxcolumn - mincolumn + 1)$. The set forms a rectangle if and only if the size of the bounding rectangle corresponds to the size of the set.
 » 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.
•  » » You can use #ifndef LOCAL_DEBUG instead of #ifdef ONLINE_JUDGE and add -DLOCAL_DEBUG option every time when compiling.
•  » » » 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.