maroonrk's blog

By maroonrk, history, 3 weeks ago, In English

We will hold AtCoder Regular Contest 145.

The point values will be 400-500-600-700-800-1200.

We are looking forward to your participation!

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

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

Looking forward to ARC !!

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

As the writer, good luck and enjoy yourself! :D

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

What's the approximate rating of ARC's problems B & C according to CodeForces rating distribution?

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

math and counting round

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

I really suck at counting, but today I couldn't figure out what the 16 different permutations were in C, the most I found was 12 :P

Can anyone list those out please?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +22 Vote: I do not like it
    1 2 3 4
    2 1 3 4
    1 2 4 3
    2 1 4 3
    3 4 1 2
    4 3 1 2
    3 4 2 1
    4 3 2 1
    1 3 2 4
    2 3 1 4
    1 4 2 3
    2 4 1 3
    3 1 4 2
    4 1 3 2
    4 2 3 1
    3 2 4 1
    
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Code that prints
»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Could someone point out what case am I missing in my submission for B?

Submission : https://atcoder.jp/contests/arc145/submissions/33632229

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

My first AtCoder contest. The problems were good, it was interesting for me. Thanks !

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

D is just cantor set...

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

As a contestant, I was not a big fan of A,B,D. Those problems' ideas are not hard to get, but have very annoying corner cases...

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

Problem D is magic, but I want to know, why the set $$${1,2,4,7,11,...}$$$, which the differential sequence is $$${1,2,3,4,...}$$$ is not the optimal one.

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

    The set $$$1,2,4,7,11,\dots$$$ has an $$$\mathrm{O}(n^2)$$$ value on the $$$n$$$-th element, while the optimal set has $$$\mathrm{O}(n^{\log_2 3}) \approx \mathrm{O}(n^{1.585})$$$ value on the $$$n$$$-th one ,which is enough to meet the constraint of $$$[-10^7,10^7]$$$ .

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

      U R right.I tried that,and the number can be as large as 4e7

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

    That doesn't even work, $$$1+7=2\cdot 4$$$

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

Sequence of pC can be found here.

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

My friend told me the problem C is in the OEIS, what do you think of it?

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

void jaiishriRam(){ ll n; cin>>n; string s; cin>>s; if(n==2) { if(s=="BA" || s=="AB") { cout<<"NO"<<endl; return; } } if(s[0]=='A' && s[n-1]=='B') { cout<<"NO"<<endl; return; }

cout<<"YES"<<endl;

} could anyone help me to know what thing I did wrong in A above is the code

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

Can anyone plz tell me whats wrong here in my submission for problem B

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

    Consider the test case :- 6 5 4 ,
    Your O/P — 4
    Correct O/P — 2
    for value (5 and 6 only Alice will win )

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

      Corrected that mistake but still getting WA on 3 test cases ;-; Here is my submission

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

        I'm not sure if binary search is a good idea here. You can try 30 10 3 correct ans: 7 your code gives: 9

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

        Consider this test case :- 8 4 3
        Your O/P — 6
        Correct O/P — 4
        Aice wins game (4,5,6 and 8)
        Error is in line 58 loop that you are multiplying . They will depend on remainder of (n%a).

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

          Thank you guys so much, my code got AC , there was implementation mistake at the end . In case anyone wants to see binary search solution — Here

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

    your code doesn't handle the cases for $$$n$$$ in the range $$$a \le n < a+b$$$

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

Can anyone please tell me whats wrong here in my submission for problem D?

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

    I don't know how your code works, but it fails at the input 4 2

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

      thx.

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

      It works in such way:

      $$$\pi(n)\sim \frac n{\ln n}$$$

      So the dfs is expected to stop in very low depth.

      p.s. What about this one? It could pass 4 2.

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

        It fails at 10000 0.

        The output has these three integers:

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

          Sorry, but it got 9999991 -9999991 9999973 -9999973 9999971 ... here.

          Maybe there's some Undefined Behavior in my code?

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

            It is not a UB, because the output is a set, and these three numbers are in it, which is against the constraint.

            Actually, they are not the first three numbers of the output on my computer as well.

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

        Are you assuming primes don't have arithmetic sequences of length 3? Because that is not true, for example: $$$101, 107, 113$$$.

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

          Oh, that's it.

          Sincerely thanks for your help!

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

C could be solved by writing a brute force and searching the sequence on OEIS. Maybe those problems should be avoided by for example having problems parametrized by some more values, or making sure it isn't easy to find on the internet. It makes the contest experience less fun, if the answer is easily found on the internet. Problems A and B were fine. Problem D also suffered from this issue.

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

C is actually A152029(OEIS).

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

Why does this code give WA for problem A?

lng dp[3][SZ],n;string s;
lng solve(lng i,lng x)
{
 if(i==n-i){return 1;}
 if(i>n-i){return (x==0);}
 if(dp[x][i]!=-1){return dp[x][i];}
 lng j=(n-1)-i;
 char a=s[i],b=s[j];
 if(x==1){a='B';}
 if(x==2){b='A';}
 if(a==b)
 {
  lng z=solve(i+1,0);
  if(a=='A'){z=max(solve(i+1,1),z);}
  else{z=max(solve(i+1,2),z);}
  return dp[x][i]=z;
 }
 if(j-i==1){return 0;}
 if(a=='A'){return 0;}
 return dp[x][i]=max(solve(i+1,1),solve(i+1,2));
}
int main()
{
 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 cin >> n >> s;
 for(lng i=0;i<3;i++){for(lng j=0;j<SZ;j++){dp[i][j]=-1;}}
 if(solve(0,0)==1){cout << "Yes";rtr;}
 cout << "No";rtr;
 return 0;
}

Here lng=long long, rtr=return 0, SZ=2e5+7

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

This was my first contest on AtCoder, Can someone tell me, when do the editorials be out ?

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

nok0 My submission for A get AC but can be hacked with n=4 AAAA My submission

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

In problem A:

Why is "AB" a valid palindrome or can be changed to a palindrome according to editorial and tests?

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

    AB doesn't satisfy the first condition (s[0] == "B" or s[-1] == "A") in the editorial.

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

for D you can just use brute force to get a set meet the last restriction,and change the largest/smallest number,then add x to all numbers to get sum=M

base 3 solution is beautiful but not necessary

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

My solution to B in the contest seems to be wrong.

When $$$n<a$$$, the answer is obvious 0, and when $$$a<b$$$, Alice can win when $$$n\geq a$$$, so the answer is $$$n-(a-1)$$$.

When $$$a>b$$$, Alice can win when $$$(n\bmod a)<b$$$, so between Game $$$ka$$$ to Game $$$(k+1)a-1$$$, Alice can win $$$b$$$ games. Consider unexisted Game 0,There are $$$\left(\lfloor\frac{n+1}{a}\rfloor-1\right)$$$ groups of games, and there are $$$(n+1)\bmod a$$$ ungrouped games, which Alice can win $$$\min ( (n+1)\bmod a,b ) $$$ games. Therefore, the answer is

$$$b\left(\lfloor\frac{n+1}{a}\rfloor-1\right)+\min\left((n+1)\bmod a,b \right)$$$

But it seems to be wrong and Here's my submission. I also found another AC submission with formula

$$$b\left(\lfloor\frac{n}{a}\rfloor-1\right)+\min\left(n\bmod a+1,b\right)$$$

I wonder what makes the answer passed and mine failed.

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

I have different approaches for problem D and E:

D:

Ingore the limit of sum for now. Let $$$f(n)$$$ be the set of integers, one can find that

$$$ f(1)=\{0\} \\ f(2n)= f(n) \cup (f(n)+2\max f(n)+ {\color{red}1}) $$$

is good. Now consider the limit of sum. One can find that if we change the $$$\color{red}1$$$ into $$$2$$$, and add $$$1$$$ to some greatest elements in $$$f(n)$$$, it is still good.

E:

We can change $$$A_j$$$ to $$$A_i\oplus A_j$$$ ($$$i<j$$$) by performing operations $$$j,i+2,i+3,\ldots,j$$$ in order.

Now we change $$$A_i$$$ into $$$B_i$$$ from right to left, taking the lexicological largest basis each time. It turns out that the number of operations is OK. (It can take up to $$$N-1$$$ operations to change a single number, but each operation will move some basis vectors to the right)

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

    Your code on E submitted during contest can be hacked using the data generated by the code below.

    #include<bits/stdc++.h>
    #define rep(i,a,n) for (int i=(a);i<=(n);i++)
    
    int main() {
    	int n = 1000;
    	printf("%d\n", n);
    	rep(i, 0, 59) printf("%lld ", 1ll << i);
    	rep(i, 1, n - 60) printf("%lld ", (1ll << 60) - 1);
    	printf("\n");
    	rep(i, 0, 59) printf("%lld ", 1ll << i);
    	rep(i, 1, n - 60) printf("%lld ", (1ll << 60) - 1 - (i & 1));
    	return 0;
    }
    
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Thanks for pointing this out! I tried to add some randomization and it worked pretty good.

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

My randomized solution for E:

If the answer is Yes, we first randomly manipulate the sequence for a small number of times, and then operate on index $$$n$$$ more than $$$n$$$ times repeatedly. Then we can (roughly) assume that $$$a_n \oplus b_n$$$ is a linear combination of $$$a_{n-r+1 \cdots a_{n-1}}$$$, where $$$t$$$ is about $$$60$$$.

We can then solve $$$a_n \oplus b_n = \bigoplus_{j \in S} a_j$$$ with Gaussian elimination. If $$$a_{n-1} \not \in S$$$, operate on $$$n$$$ so that $$$a_{n-1} \in S$$$.

Then we operate on the second minimum element $$$t$$$ in $$$S$$$. Then $$$\min S$$$ is removed from $$$S$$$ and all indices between $$$\min S$$$ and $$$t$$$ are added. Repeat this process until $$$S = {a_{n-1}}$$$ and operate on $$$n$$$. Do this for $$$n - 1 \dots 2$$$ and we are done. This solution uses ~60000 operations in randomly generated inputs.

implementation

UPD: More than 1000 random operations at first are needed to guarantee randomness.

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

Can somebody explain here problem D, how exactly are we constructing the required set after we have figured out the base 3 condition where each digit should be 0/1.

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

F is some wild generalization of IMO 1995 P6. I like it

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

Such a magical problem D!

Base-3 representation is such a trick that could perfectly beat the rule of $$$2y \neq x + z$$$.

Next, by first keeping the rightmost digit of all n integers as zero and then change some of them to 1, so that $$$|m - sum| \% n = 0$$$. At the same time, all n integers are still distinct and satisfy the "good set" rule.

Finally, add $$$(m - sum) / n$$$ to each integer so that $$$sum = m$$$, and at the same time, adding the same integer will not lead to any $$$2y = x + z$$$, although they may not belong to the "good set" anymore.

Thanks to the problem writer for coming up with such a clever and unbelievable construction problem!

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

Was only able to solve A, although I misread the problem at first and somehow thought that I could use the operation only when adjacent characters are equal, lead to 3 WAs but we move....

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

In terms of codeforces ratings, what would be the difficulty rating for problem A?

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

can anyone explain logic of c plz?

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

This round is good, arc should contain magical counting and constructing problems like this.

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

A different way to think for D.

We can construct as follow (P is a set,initial $$$P={1},len=1$$$): $$$P\to P\cup (P+(2len-1)),len\to 3len-1$$$

$$$P+a$$$ means add $$$a$$$ to all elements in $$$P$$$.

And it can prove that $$$y−x\not=z−y$$$ for every triple $$$x,y,z (x<y<z)$$$ of distinct elements in $$$P$$$.

(Which is similar to the official editorial)

and we can construct the set with $$$n+2$$$ elements, and enumerate which two to delete. It can solve the problem.

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

    Could you please talk more about why your construction will not lead to 2y=x+z? And, how to construct these n+2 elements, and how to determine which two to delete?

    Thank you so much for providing such a clever idea.

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

      Let $$$P'=P+(2len-1),\forall x\in P,y\in P,z\in P',$$$ we can found that $$$|x-y|<len,|x-z|\ge len$$$.

      This is my submission for D.

»
11 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Sorry for asking it late,

Can any one please the explain this line of editorial :

Here, if the elements in P are scanned from left to right, there must always be more left elements than right elements. The number of such arrangements corresponds to that of parenthesis sequences.

What I understood is that, lets say we have (1,2),(3,4),(5,6),(7,8) as corresponding (ai and bi).
Permutation : (1,2,4,3,5,6,7,8) have more right elements(2) than left elements(1) in first 3 elements (1,2,4) but still it can be divided it into two sequences A(1,3,5,7) and B(2,4,6,8), but in editorial it is told that it should not be possible ( as per I understood ) .
I know I have understood it wrong.
Anyone who did this problem or got the editorial please explain the line in blue

Editorial link : Link