chokudai's blog

By chokudai, history, 3 weeks ago, In English

We will hold AtCoder Beginner Contest 182.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Six hours left =.=

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

yay ! I am on a binge solving At Coders problems. They are really cut-the-shit and ad hoc awesome xD !!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

6 minutes left. Come on guys!!

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

4 wa in problem C.Know why getting WA but still can't fix that.That's how every contest made my day

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used lots of if-else :v :v

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can see my solution it's easy to understand

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Just tell that what is output for 55555555 for problem c? My accepted code give -1..but after getting accepted I feel.it is wrong for above test as for it ans is 2(555555).. Am I missing something?

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

      Hey.Can u explain u r solution little bit?-emli-

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        He is checking all possibilities of digits. For each i, he considered each bit equal to 0 as not chosen and each bit equal to 1 chosen.

        For each combination, he get the sum of digits and de number of used digits (# of one on bit representation). If the sum is divisible for 3, this combination is divisible too.

        Then he printed the biggest combination that sum is divisible for 3.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can make use of dynamic programming, everytime either leave a digit or add it to your total sum, if at the end the total sum is divisible by 3, then store the total no. of digits you erased from the given string of numbers. print the minimum of it. My solution : https://atcoder.jp/contests/abc182/submissions/17971476

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it +19 Vote: I do not like it

      I used $$$2^{len(|N|)}$$$ brute force. I know there are a lot of more efficient solutions, but this is the fastest to implement.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What is the brute force solution for this problem ?

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

          Statement says: we can erase some subset of digits. There are at most $$$18$$$ digits, so at most $$$2^18$$$ subsets which is quite small. Just run through all subsets, check if remaining number is divisible by $$$3$$$ and if so update the answer taking minimum of current answer and number of erased digits.

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

            I did exactly same using bitmasking. code

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh nice . This idea did not even come to my mind because i was focusing on an efficient solution. Thanx

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

        There is another brute force, That I think is easier to implement. At the first build array cnt[3] that cnt[i] is the number of digit x such that x % 3 = i. Now lets brute force on the number of digit 1 and the number of digit 2 we will remove. code

        UPD: After I think a little bit more about it, It's unnecessary to remove digit 1 or 2 more than 2 times. This solution will be O(length of the number). code

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      didn't need the memoization though.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Tried to fix a runtime error on E for an hour QAQ
Does anyone know any compilation flags that will be helpful in detecting out of bounds error?

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve F ??

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve F plss

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

    hint: Transform the problem to finding the number of (y — X) instead of y.

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

      I think find the number of (y+X) is much easier!

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

        How? There is no (y + X) is the problem?

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

          Y is the change. I think “add” is very convenient

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

            Oh, I mean the same thing by (y-X). let z = y-X. find z and z + X.

            I thought your y is the y in the problem.

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

    First of all notice that any number $$$X$$$ has unique minimal representation. This can be proved by greedy exchange (using the fact that each successive number is a multiple of the previous number).

    Now, notice the isomorphism (structure equivalence) between the number bases and the (minimal) representation of each number in the system of Yens. There are two properties which are maintained:

    1) If highest bit of $$$A$$$ is greater than $$$B$$$ in our Yen-system, then $$$A>B$$$.

    2) Each number has unique representation.

    So we can think of an equivalent problem: given a number $$$X$$$, how many numbers $$$b$$$ there are such that $$$X+b=a$$$ and $$$a$$$ and $$$b$$$ have no bit in common?

    This can be solved, after some thinking, with DP.

    Array g[] represents the representation of $$$X$$$ in Yen-system

    We introduce the concept of "span". span[j] represents the number of elements after the $$$j^{th}$$$ bits of X which have maxed out values of their bit. Then if g[j]>0, we can use this bit in the number $$$b$$$ such that DUE TO the process of carry-over, we don't have this bit in $$$a$$$. You can see the details of dp transition in my Beautiful AC Code

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow you are so smart! Great explanation!

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain the concept of Span a bit more. I couldn't get it. By the way your approach seems better than those of others to comprehend .

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

        the "span" array is the count of consecutive elements whose bit is "maxed out" in $$$X$$$.

        For example, consider a representation where $$$A_{i}=3A_{i-1}$$$ FOR ALL $$$i$$$. This is exactly similar to base-3 representation, and every bit can have atmost $$$2$$$ as coefficient. When a bit in X has 2 as its coefficient, I say that it is "maxed out".

        So lets say the yen-array in given input is

        1 3 9 27 81 243

        and $$$X=271$$$ so that it is $$$222001$$$ in our yen system. Now $$$dp[j]$$$ denotes the number of ways in which we can have $$$b$$$ (in the equation $$$X+b=a$$$) such that $$$b$$$ has no bits in common with $$$a$$$ and only bits from index $$$j$$$ to $$$n$$$ is possibly ON in $$$b$$$. That is every bit from $$$1$$$ to $$$j-1$$$ is definitely $$$0$$$.

        Now ,for example, if we want to have the $$$2^{nd}$$$ bit ON in $$$b$$$, and all before that OFF, we must have that bit equal to $$$1$$$, because BY THE PROCESS OF CARRY OVER, that bit will be OFF in $$$a$$$. And now, notice that carry over makes $$$3^{rd}$$$ bit $$$0$$$ in $$$a$$$. So the span of the $$$2^{nd}$$$ bit is 1, since now we can't have any bit as upto after span bits after $$$j$$$ as ON in $$$b$$$, because then there can't be a carry over.

        After that it is simple DP transition.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Are you considering bit numbering from left to right?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice explanation! Can you suggest some more problems like this?

  • »
    »
    12 days ago, # ^ |
    Rev. 4   Vote: I like it +1 Vote: I do not like it

    I just came out this solution, not pretty sure that it is correct. However it does get me AC.

    The problem is same as "Find the number of integer $$$r$$$ with length $$$N$$$ (leading 0 is allowed) in base $$$A$$$ that shares no common digit with $$$X + r$$$, i.e., $$$\forall_{0 \le i \lt N}, r_i = 0 \lor (X + r)_i = 0$$$".

    Let $$$c$$$ be carry, $$$y = X + r$$$, we have ($$$N$$$ = 4):

    $$$ \begin{array}{r} &c_3 &c_2 &c_1 &0 \\ &x_3 &x_2 &x_1 &x_0 \\ +\quad &r_3 &r_2 &r_1 &r_0 \\ \hline &y_3 &y_2 &y_1 &y_0 \end{array} $$$

    In particular, all digits $$$i$$$ satisfy ($$$m_i = A_{i + 1}/A_i$$$ is the limit of digit $$$i$$$):

    $$$ y_i = (c_i + x_i + r_i) \pmod {m_i} \\ c_{i + 1} = \lfloor \frac{c_i + x_i + r_i}{m_i} \rfloor $$$

    Let $$$dp[i, c]$$$ = the number of valid ways to fill digits $$$[0, i)$$$ while $$$c_i = c$$$. This dp is computed from lower digit to higher digit due to carry-over.

    By iterating all possible values ($$$0 \le r_i \lt m_i)$$$ of $$$r_i$$$, we can get an correct state transition, but it will get TLE. Key observation is that we don't need to iterate all values of $$$r_i$$$. Since $$$r_i = 0 \lor y_i = 0$$$, there are only few valid conditions.

    We decompose $$$r_i = 0 \lor y_i = 0$$$ into 3 disjoint conditions:

    1. $$$r_i = 0 \land y_i = 0$$$
    2. $$$r_i = 0 \land y_i \ne 0$$$
    3. $$$r_i \ne 0 \land y_i = 0$$$

    Let's consider when will these conditions be true?

    1. By substituting $$$r_i = 0, y_i = 0$$$ into the formula of digit $$$i$$$, we find that only when $$$(c_i + x_i) = 0 \pmod {m_i}$$$, condition 1 is true. We transfer to $$$dp[i + 1, c_{i+1}]$$$.
    2. Substituting $$$r_i = 0$$$ into formula, we find that only when $$$(c_i + x_i) \ne 0 \pmod {m_i}$$$ will $$$y_i \ne 0$$$ be true. We transfer to $$$dp[i + 1, c_{i+1}]$$$.
    3. Substituting $$$y_i = 0$$$ into formula, we find that only when $$$(c_i + x_i) \ne 0 \pmod {m_i}$$$ will $$$r_i \ne 0$$$ be true. Notice that in this condition, there will be a carryover. We transfer to $$$dp[i + 1, 1]$$$.

    That's all for the dp transition. Here is my submission.

    Chinese version

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a dp solution for C?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. link

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

      Please elaborate what are you storing at dp[i][j]. I was thinking something like declaring

      dp[index][sum]---->Maximum digits required till index to make sum. Is that correct? thanks.

      snippet
      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I'm storing the maximum number of digits that I can take,upto index i, such that sum%3==0.
        I think your code should work if you store the same. (PS. i'm very bad at iterative dp. xD)

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Solved it. here is updated DP code for T: O(9*N*N) , S: O(9*N*N)

            /*
            dp[index][sum]==>Maximum number of elements required to make 'sum' till 'index'.
            Base Case:
            dp[1....n][0]=0 , zero coins required to make sum zero
            */
           
            vector<vector<int> > dp(n + 1, vector<int>(sum + 1, -1e18));
            for (int i = 0; i <= n; i++)
                dp[i][0] = 0;
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= sum; j++)
                {
               
                    dp[i][j] = dp[i - 1][j];//excluding the current element
                    if (j - arr[i - 1] >= 0)
                        dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - arr[i - 1]]);//including it
        
                    if (j % 3 == 0)
                    {
                        ans = max(ans, dp[i][j]);
                    }
                }
            }
            if (ans == 0) {
                cout << -1;
            }
            else
                cout << n - ans;
        
        
  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Just try every subset with bitsets or recursion. my solution

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

      No need for that. Just count all digits modulo 3 and use this

      if(n<3 and c[0]==0 and (c[1]==0 or c[2]==0)){
       cout<<"-1\n";
      } else {
       cout<<min(abs(c[1]-c[2])%3, abs(c[1]%3-c[2]%3))<<"\n";
      }
      
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what do you mean by "count all digits modulo 3"? Please explain. Do you mean that if number is k digits long then for every digit calculate it's modulo 3?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            ok thanks!

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            what is the significance of min((c1-c2)%3,(c1%3-c2%3)) can anyone explain because I tried without this and only 1 test case failed

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yeah happened to me too. Try with 2224. The ans is 1. That's how I thought of this.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah that's exactly what I mean. In the above code, c[i] is count of digits with modulo 3 as i, ex c[2] is the count of digits with modulo as 2.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I feel so dumb now , I somehow assumed in my head that over all complexity of brute-force will be ~10^18 and discarded this approach immediately . Thanks anyways.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can think of finding the longest subsequence which has sum divisible by 3. Then you can do number of digits — longest subsequence

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    O(logn) Solution using DP. My Code : Link

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

      Brilliant solution , thanks for sharing , but is'nt the TC O(n)? Edit: TC would be O(n) where n is the length of the string , or O(logn) in this reference.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does we have to use dfs in E?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    No, just annoying implementation.
    I used prefix and suffix sums on the rows and the columns.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i think DFS will work fine.I wasted time on D.or I Don't know if dfs will work or not

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

      Not sure if this is what you meant, but you can just iterate over each column twice, once up and once down, and then each row twice, once left and once right. If you go over a block, everything after it is dark, and if you go over a bulb, everything after it is lit. So you just copy paste the same for loop like 5 times, change the bounds and you get the answer. Not really annoying implementation

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ohh now I understand,thanks bro

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    we can solve it simply for every row right to left + left to right observation and every column from up to down + down to up simple operation

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

    No, just optimize the brute force solution a little bit.

    The brute force solution is, for each bulb, and for each direction, start from the bulb, and go along with this direction until you meet a block, set each grid passed illuminated by the bulbs. And then, iterate all grids, count the number of grids illuminated by the bulbs. The time complexity is $$$O((H + W)N + HW)$$$.

    The brute force solution might get TLE, although I think it's time complexity is good enough to pass.

    While going along with one direction, you can stop not only when you meet a block, but also when you meet a bulb. If you do so, the time complexity will be $$$O(HW)$$$ cause you will pass a grid at most 4 times.

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

      Thanks! That brute force modification helps to not get TLE.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Using this matrix struct with already clock_rotate, you only need to repeat 4 times rotating the matrix every rotation.

    Submission

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

please anyone explain solution for D

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hope u understand
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Calculate prefix sums on the input. Also calculate the maximum sum you achieve on the input for every $$$0$$$ to $$$i$$$, where i is from 0 to N — 1 (0-based indexing). Then, you can find the maximum coordinate by iterating from 0 to n and adding the maximum sum in range(0, i) to your current coordinate.

    Code
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Let us define end[i] as coordinate after the end of ith round (let us assume 0-based index) then, end[i] = end[i-1] + prefix[i]
    Now, if your answer is after round i, and before round i+1

    ans = max(end[i], end[i]+prefix[0] , end[i]+prefix[1] , end[i]+prefix[2] ,..)

    ans = max(end[i], end[i]+max(prefix[0],prefix[1],..,prefix[i]))

    sudo code :

    prefix[0] = a[0]
    for i = 1 to n-1
       prefix[i] = prefix[i-1]+a[i]
    end[0] = prefix[0]
    for i = 1 to n-1
       end[i] = end[i-1]+prefix[i]
    
    max_so_far = prefix[0];
    ans = max(0,prefix[0]);
    for i = 1 to n-1
       max_so_far = max(max_so_far , prefix[i]);
       ans = max(ans, end[i-1] + max_so_far);
    
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was an issue in translation. In Japanese version of issue description it stated that 'positive direction' = direction where it should move. So we take final position of robot after series of move and apply next line of steps. Taking a sample 2, we have robot movements: I1 (-2) [-2] I2 (-2, 1) [-4, -3] I3 (-2, 1, 3) [-5, -4, -1] I4 (-2, 1, 3, -1) [-3, -2, 1, 0] I5 (-2, 1, 3, -1, -1) [-2 ,-1, 2, 1, 0] Among all steps robot position 2 was biggest one

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the idea for E? I spent 50 mins on it thinking it was easier than D but I couldn't get it to work on one of the sample tests; probably some implementation errors. D was easier than I thought though. Great contest, thanks!

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Hint
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    There are a lot of ways. Shortest would be: assume light doesn't pass through a square with another light bulb, which doesn't affect the answer, and then for each light bulb iterate through all squares it illuminates and mark them (with the modified rules each square will be touched at most $$$4$$$ times, so it's $$$O(HW)$$$).

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

    am I the only one who solved it with Binary Search ?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What's your idea with binary search?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you provide link of your solution?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • The cell will be illuminated if it has bulb closer than block in any of its four sides.
        • Lets say cell is (r,c) and direction is right.
        • Now do lower_bound on row 'r' for bulb position and block position.
        • If bulb position is less than block position, that means there is no block between that cell and bulb position.So,cell will be illuminated.
        • Similarly we can try in another directions with little modifications.
        • MyCode:Link
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E. My O((H+W)*N) solution gave TLE.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    solution with comment
»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone explain sample test case 2, problem D, how the answer is 2?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    The positions after each step are:

    Spoiler

    Therefore, the greatest coordinate occupied is $$$2$$$.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C and D were easier to do than B for me. Can anyone explain how B should be done?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can just brute force for the possible value of the answer from 2 to 1000. Whichever value gives maximum count of divisions is the answer.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Brute force numbers from 2 to 1000 and calculate how many numbers in A are divisible by them. The one with the maximum count of numbers divisible is the answer.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem F?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C? People are saying it can be solved using DP. I don't know DP. Can anyone please tell me which variation of DP should actually I learn(as DP is huge) to be able to solve this problem(C)??

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's a standard knapsack problem. For every digit you either use it in the answer or you don't.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh! Thanks dude. I shall really look forward to learn standard knapsack asap and solve it.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Pls share your solution.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Code
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Just an optimization that will help you in solving a lot more problems, when you call the solve function, you pass $$$sum + c$$$ you should take module $$$3$$$, this way the sum will never be $$$\ge 3$$$. In the return statement, check if the sum is $$$0$$$ then the number is divisible by $$$3$$$. This way you will reduce the states and your code will be much more faster.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    u can use recursive, it will be O(2^digit)

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It can also be solved by observation.

    https://atcoder.jp/contests/abc182/submissions/17985247(The code is a bit messy though)

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    It can be solved using greedy approach as well. As for N to be divisible by 3, sum of its digit must be divisible by 3. And sum%3 can be either 0, 1 or 2.
    If its 0 than we have to do nothing.
    If it's 1 then we remove one digit (which is 1 mod 3 i.e. d%3=1) or 2 digits (which are 2 mod 3 .i.e, d%3=2).
    Similarity for the case where sum%3 = 2.

    If we aren't able to remove the digits in such a way then answer is -1.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. i feel so dumb for not seeing this. xD

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Great! How I missed this idea! :")

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Same greedy done by me and i thought i had done a very similar problem on cf earlier with almost same approach.

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

    I think the solution with bitmasks is pretty nice

    My submission

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me what are the 21 solutions to the last sample of problem F, I don't get how there are so many.

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone please tell me what's wrong with my code for E: https://pastebin.com/1WPa7pUD ? EDIT: I finally fixed it...I am so stupid!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is it possible to see the submission of other participants after the contest at Atcoder.??

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, for example, see my submission in my comment here.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But I am not able to see the solution of particular participant in the standing section as we have in codeforces where we just double click on the submission to view the code.

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

        Click the magnifying glass next to a user on the standings to see their submissions.

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

I recorded a video of me solving the contest: https://youtu.be/VsUvBvgeb9Y. I got 64th, solving all problems in about an hour.

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

    Your solution for solving F is fantastic.

    Thanks for sharing that.

»
3 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

Here is my editorial for this contest.

English editorial

中文题解

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can we use line sweep for E to solve for any H,W.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C what am I missing , its WA https://atcoder.jp/contests/abc182/submissions/17965994

Please help!!

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Here's a screencast of being destroyed by daylight saving time, also includes solutions to all problems

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    Thanks. It' ll be great if you could upload some video on algorithms and important data structure for beginners that will be really helpful for all beginners.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please tell me, what is the test case20? I just get WA in this case...QAQ

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For Question E will a flood fill(dfs) approach work?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    probably TLE, why don't you try it..

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it wont work,thought on it as it will try searching for connected components of squares which is not what we want