We will hold AtCoder Regular Contest 141.
- Contest URL: https://atcoder.jp/contests/arc141
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220529T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: chinerist
- Tester: maspy, satashun
- Rated range: — 2799
The point values will be 400-500-600-700-700-1100.
We are looking forward to your participation!
problem A was terrible
i think so
The sample is really weak :(
Mine passed samples, but failed all system tests XD
I didn't notice that the resulting number can have size less than the size of n. So when n is 100 answer is 99.
Couldn't agree more
Me after reading problem A -
"Why did I register as rated?"
Feel honored that problem B is similar to my probelm in Codeforces: 1329B - Dreamoon Likes Sequences. :)
lol, I solved it 2 years ago with a sane DP, today I solved it with Matrix Exponentiation.
How to solve B?
The mst of Ai must be greater than the previous value. Thus the maximum possible length will be atmost 60. Rest it can be solved using 2d dp.
I think the main idea to solve B is that if the xor of your prefix have k bit then the next element can't not only have k bit because the k-th bit will be appear even number of time which make the xor small than previous, also the a[i] have to be greater than a[i-1] so you can't not use less than k bit -> a[i] has to have more bit than a[i-1]
More and more ARC T1 can't solve, what should I do?
Submit A for so many times but still can't solve it..
Very nice problems, thanks! F is a bit nasty to implement, but the idea behind the solution is nice nonetheless.
C and D are really great problems!
I don't understand why my Problem A failed at first. I think I did the same the editorial says. I looked at the first $$$k$$$ digits of $$$N$$$, call them $$$N'$$$. Then I concatenated $$$N'$$$ first and then $$$N'-1$$$ to create periodic numbers and checked which one was the biggest. This failed for me.
Then in a rush I randomly tried adding $$$N'-2$$$ to the checks and it passed.
Can someone enlighten me what I did wrong or find an counterexample for my first solution and esp. why adding $$$N'-2$$$ makes it pass? I was clueless duting the contest and I still am and assume some form of error in the implementation...
Edit: Oh dear, got it: Testcase $$$11001$$$ breaks it. $$$9999$$$ will never be checked and it will output $$$1111$$$ as answer. Adding $$$N'-2$$$ to checks, adds "accidently" a check for $$$9999$$$ with $$$11-2=9$$$. I guess this is explicitly what the last paragraph of the editorial warns about.
I did $$$N'$$$ and $$$N' - 1$$$, and initially set ans to 99.... .
Problem C was very nice!
I didn't understand the editorial for D, can someone explain? Are there any resources to read the "typical problem of choosing such k by getting upper limit and lower limit"?
Did you get some related resources? Would be nice if you can share them.
Nice problems, thanks to writers and testers.
For problem A, somehow I realized the solution quickly and also noticed the special case 999...9, and feel lucky to get AC with only one try.
Problem B needs some observation that it is sufficient to deal with N up to about 60. Then, if you are familiar with problems, like, longest increasing subsequence, maximum sum of substring, then one could come up with dp, with a classic definition of state, dp[end at index i][if the i-th index has value j]=the number of possible sequences.
Finally, I spent a lot of time on problem C, but, have to end up with nothing. I think this problem really needs quite deep observation and strong logics to reach the conclusion. Would anyone like to share your solution, or your ideas about this problem :)
For A, I wasted a few WAs by directly comparing strings instead of first converting strings to long longs then compare.
In particular, string "999" is > string "1010" when compared as strings. Lesson learned,
C was such a genius problem.
The editorial for problem C wrote:
I can understand the case when S is a correct parenthesis sequence or its reversal. But how to prove the general case？