maroonrk's blog

By maroonrk, history, 3 weeks ago, In English

We will hold AtCoder Regular Contest 153.

The point values will be 300-500-600-800-800-1000.

We are looking forward to your participation!

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

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

The whole 2 problems I read were both very good. How do you solve B?

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

    Congratulations um_nik pulling this 5 seconds before the end of the contest

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

    One of my classmates use BST.

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

    Note that for the operation $$$a\ b$$$, you can independently flip the indices for the height and the width respectively. So specifically, consider the first sample. We initially start with the indices $$$[0, 1, 2, 3, 4]$$$ for the height. When we apply the operation 3, we flip the first 3 and the last 2 to get $$$[2, 1, 0, 4, 3]$$$. You can verify that within each row, the original indices of each letter corresponds to this array, both the original position from the top and from the left.

    So the question is, can we compute these arrays for the height and width efficiently, and then we can just print out the result using these indices. The observation that we can make is that the operation flipping by $$$x$$$ is equivalent to

    1. rotating the index array right by $$$x$$$
    2. reversing the entire array

    We can also perform the reversal first, which gives us the equivalent set of instructions:

    1. reversing the entire array
    2. rotating the index array right by $$$len - x$$$ (where $$$len$$$ is either the height or width depending on which array it is)

    If we do two operations in a row, then we can do the reversals for both operations one right after the other, so they cancel out. So operation $$$x$$$ followed by operation $$$y$$$ is rotating right by $$$x$$$, then by $$$len - y$$$. We can do this to simulate an even number of operations, and if $$$Q$$$ is odd, we can just directly simulate the last step.

    Solution code can be found here.

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

    In C++ you can complete all reverse queries with __gnu_cxx::rope<int> in $$$O(log(n))$$$. My accepted solution.

    Reverse $$$[i,j)$$$ is equal to swap segment $$$[i,j)$$$ in direct order of items with segment $$$[n-j,n-i)$$$ in reversed order of items. The rope can erase and insert segments in $$$O(log(n))$$$.

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

    I treat a cell at $$$(1,1)$$$ as pivot point. By knowing the position of this pivot cell at the end, we can determine the rest of the positions

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

A binary version of problem D has appeared on codeforces before. Here is the link.

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

When Um_nik becomes rainboy

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

I felt like Problem B was standard. It is simply a straightforward implementation of Treaps. Sadly I don't have a pre-written template for treaps and wasted about an hour finding an easy-to-understand template for treap.

C seems nice.

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

How to solve Problem A?

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

    To count up these numbers, start at the first one (110000000). You can't increment the ones place because you also have to increment the hundreds place, which is why the first 3 numbers are increments of the tens place. This means you never should directly increment the ten millions digit, the ten thousands digit, or the ones digit--just their respective counterparts.

    This means you can take them out of the equation entirely, and simply increment 100 000 N times and then duplicate the applicable digits when printing the answer. code

    Note that this problem can be solved in O(1) time similarly--just add 100 000 to N and then use std::to_string to construct your answer. O(N) is fast enough though.

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

    I use brute force.

    Since $$$S_1 = S_2$$$, $$$S_5 = S_6$$$ and $$$S_7 = S_9$$$, therefore we only need to iterate 6 different indices in $$$S$$$ (only $$$10^6$$$ digits possible)

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

Very nice problemset, thanks!

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

Why did everyone pass B with a splay?????? I feel humiliated.

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

I think many people solve B with data structures.

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

B was a nightmare for me

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

please explain b.

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

Editorial for problem C looks scary! https://atcoder.jp/contests/arc153/editorial/5523

I have another approach, is this correct?

WLOG, if A[0] = -1, flip the sign of A[i]. So A[0] is always positive.

Let S = sum of x[i] with A[i] positive, R = sum of x[i] with A[i] negative. Problem hence asks to find x[i] such that S = R and all x[i] distinct.

Initialize x[i] = i.

We have 2 cases. If S > R, then we can simply set x[i] = x[i] — (S-R).

If S < R, then for i = n-1 to 0, set x[i] = x[i] + (R-S). If by doing so, S == R at some point, stop here and we are done. If in the end S != R, then if sum of A[i] = 0, we know for sure there is no answer. Otherwise, reset x[i] = i, then for i = 0 to n-1, set x[i] = x[i] — (R-S) and stop when S = R.

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

    Your solution is correct (I implemented it and got AC). There are a couple of things I would like to say:

    1. We have 2 cases. If S > R, then we can simply set x[i] = x[i] — (S-R). This should be $$$x[0] = x[0] - (S - R)$$$, not $$$x[i] = x[i] - (S - R)$$$.

    2. If in the end S != R, then if sum of A[i] = 0, we know for sure there is no answer. This is true, but unnescessary. We can just check for answer in the other direction and if there still is no answer found, we print "No".

    3. When implementing the code, make sure to use long long instead of int, the integers will get very large.

    I won't link my code here, because it's messy and I don't want to spoil the implementation part for you. If you need any help, I'll be glad to help!

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

Can anyone tell what the problem ratings are Thanks.

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

    To view problem ratings, go to the ARC section here.

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

      What's rating 500 in relation to cf ratings? Specialist?

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

        I'm not 100% certain, but I heard from someone that approximately atcoder = cf — 200.

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

          If that's so then I think cf rating 1300 should solve Atcoder F-1000 ?

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

            i don't know for sure.. probably atcoder rating is a better proxy than cf rating

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

            1000 is F's score in contest, not its rating.

            Move the cursor over the circle before the problem title, you can see its difficulty (rating).

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

Can anyone please explain Problem B?

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

For me as A junior one student, except for the A question, it is too difficult

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 
 int N;
 cin >> N;
 vector<int> S(9, -1);
 N -= 1;
 S[0] = S[1] = N / 100000 + 1;
 N %= 100000;
 S[4] = S[5] = N / 10000;
 N %= 10000;
 S[6] = S[8] = N / 1000;
 N %= 1000;
 S[2] = N / 100;
 N %= 100;
 S[3] = N / 10;
 N %= 10;
 S[7] = N;
 for(int i = 0; i < 9; i++) {
  cout << S[i];
 }
 cout << endl;
 return 0;
}

Where my logic is going wrong?