maroonrk's blog

AtCoder Regular Contest 134 Announcement
By maroonrk, history, 3 years ago, In English

We will hold AtCoder Regular Contest 134.

The point values will be 300-400-500-600-900-1000.

We are looking forward to your participation!

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

Comments Comments (42)
| Write comment?
»
3 years ago, # |
  Vote: I like it +145 Vote: I do not like it

I don't know whether I'm happy there are no stupid meme comments under atcoder announcements, or upset that the contests aren't getting too much attention. Either way, I'm looking forward to being proven yet another time that I know nothing about problemsolving

→ Reply
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I only received a reminder email about the upcoming ABC 237, but no reminder email about the upcoming ARC 134, which will happen earlier. I expect to receive the reminder for the contest that will be held earlier first.

→ Reply
»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Will AtCoder ever consider looking into making the times PST-friendly or varied?

P.S. Not demanding anything, just curious.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Starts in 5 minutes.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

GG

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

When can we expect to see Cpp20 support for atcoder ?

→ Reply
»
3 years ago, # |
  Vote: I like it +90 Vote: I do not like it

In other words, in every box, the number of balls with 1 should be greater than that of the other balls.

How does this not mean "For all box, the number of ball $$$1$$$ is greater than the number of ball $$$i$$$, for all index $$$i \ge 2$$$"?

I wasted like 1 hour solving the wrong version :(

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Really? Problem C means "The number of ball 1 should be greater than the sum of ball 2 to ball N" ?

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    read it the same way for like 10 mins... doesnt help that the small samples were also consistent with this wrong version

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I was about to ask for a clarification but then decided just to go with the word "majority" and disregard the "in other words" part.

    I think they should have added "combined" to the end, as in "...than that of the other balls combined".

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I did so,then I wasted 1 h.(

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I was also confused by it.

    Luckily, after thinking about the problem for some time, I thought if it was "For all box, the number of ball $$$1$$$ is greater than the number of ball $$$i$$$, for all index $$$i \ge 2$$$", it would be too difficult, so that I decided to go with the word "majority".

    And after a while, I saw the clarifications came out.

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

    Us Moment

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

The problem E... I can't imagine the solution has an exponential complexity until i write it out.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Regarding task A). When a tarp covers the range [x, x+w], both ends included, then the tarp has length w+1, right? Am I stupid? Doesn't that make the answer ceil(l_i/(w+1)) for each segment?

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

    "x is real"

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

    You are thinking in terms of number of integers. If you look at them on a number line, the distance between them is W.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it -6 Vote: I do not like it

    It is written that it is real numbers, so the length is not w+1, but simply w.

    Edit: For me the statement of A reads like the setter tried to make it more interesting by not giving a clear statement, but a overformal mathematical sounding one. And actually that style of statement repeats, in example also in C.

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

    I see, I guess reading is not my strength

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

      I would second what _lowerBound said , can anyone elaborate how being defined as "real" makes the length W and not W+1? I too was stuck on this in the contest.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +4 Vote: I do not like it

        so when you have w = 3 and a tarp starts at 0, then it covers [0.00000, 3.00000], however, 3.00001 is not included. That means to, cover a range from 0 to 7, you need three tarps, one at 0.0000, one at 3.00000, one at 6.0000. (in contrast, if we talk about integers: 0-3, 4-7 would only require 2)

        For me, this task was rather reading comprehensions ... :(

        → Reply
»
3 years ago, # |
  Vote: I like it -36 Vote: I do not like it

I registered 5 minutes before the contest so that I forgot to check the author today.

As a result, I found that the problems are not my style and I got negative delta.

I have no idea about "(4,8) is a corner case".

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve problem C? I am not smart enough to understand the editorial.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    First, you need to know about https://en.wikipedia.org/wiki/Composition_(combinatorics). Then, for every other-colored ball, pretend that you always stick a ball colored 1 to it. Then, put a ball colored 1 in all of the boxes. Now the requirement that 1 is the majority can be ignored, and the ways to put the balls in the boxes can be solved independently for each color. The problem then becomes, to find the number of weak compositions of the number of remaining balls of each color.

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

      Got your idea. Thanks~

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      I'm having slight confusion with the formula posted in editorial. I understood the editorial .

      if i want to distribute $$$a_2$$$ identical balls into K blocks without any constraint then isn't the formula [](https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)) $$$ \binom{a_2 + K -1}{K-1} $$$

      why is this value $$$\binom{a_2 + K +1}{K+1} $$$ in the editorial ?

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

        The English translation has a typo. In the Japanese editorial, the formula is correct.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A I wonder where the mistakes are QwQ

#include<bits/stdc++.h>
#define int long long
//define LOCAL
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
using namespace std;
 
int N,L,W;
const int SIZE=1e5+7;
int a[SIZE];
 
signed main()
{
	#ifdef LOCAL
		freopen(".in","r",stdin);
		freopen(".in","w",stdout);
	#endif
	cin>>N>>L>>W;
	REP(i,N)cin>>a[i];
	sort(a,a+N);
	a[N]=L;
	//REP(i,N+1)cout<<a[i]<<" ";
	int cnt=0;
	REP(i,N)cnt+=ceil(max(0LL,(a[i+1]-a[i]-W))/(1.0*W));
	cnt+=ceil((a[0]-0)/(1.0*W));
	cout<<cnt<<endl;
	return 0;
	
}

`

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

    you need to set int to long long

    and also you have to cast w to long double while division

    here is the new AC code

    #include<bits/stdc++.h>
#define int long long
//define LOCAL
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
using namespace std;
 
long long N,L,W;
const int SIZE=1e5+7;
long long a[SIZE];
 
signed main()
{
	#ifdef LOCAL
		freopen(".in","r",stdin);
		freopen(".in","w",stdout);
	#endif
	cin>>N>>L>>W;
	REP(i,N)cin>>a[i];
	sort(a,a+N);
	a[N]=L;
	//REP(i,N+1)cout<<a[i]<<" ";
	int cnt=0;
	REP(i,N)cnt+=ceil(max(0LL,(a[i+1]-a[i]-W))/((long double)W));
	cnt+=ceil((a[0]-0)/((long double)W));
	cout<<cnt<<endl;
	return 0;
	
}
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you!But actually,I have already set int into long long (line2) QwQ

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

        Oh, I didn't notice the #define int long long, it is somewhat weird. But Then, the problem is the long double, I got a WA because of it too.

        → Reply
»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

The clarification did not popup? I saw it after the contest ended.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/arc134/submissions/28877523 plz see this wa on 3 test case in q2 i tried alot of tc but cant come up with AC solution if anyone can figure out tc or whats wrong plz tell

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

    I tried but couldn't find a counter-example. Looks like you have to run a script which keeps looping and trying random strings as inputs to your solution vs a passing solution.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sorry, for wrong post.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone identify what i am missing? WA*4, AC*91

int main(){

    FIO;
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output2.txt", "w", stdout);
    #endif
    
    ll t;
    t = 1;
    //cin >> t;
    
while(t--){
    
    ll n;
    cin >> n;
    
    vector<ll> a(n);
    vector<ll> b(n);
    
    for(ll i=0; i<n; i++) cin >> a[i];
    for(ll i=0; i<n; i++) cin >> b[i];
    
    vector<ll> smallestElement(n);
    smallestElement[n-1] = a[n-1];
    for(ll i=n-2; i>=0; i--){
        smallestElement[i] = min(smallestElement[i+1], a[i]);
    }
   
    vector<ll> ans1;
    vector<ll> ans2;
    ll sid = 0;
    for(ll i=1; i<n; i++){
        if(a[i] < a[sid]){
            sid = i;
        }else if(a[i] == a[sid] && b[i]<b[sid]){
            sid = i;
        }
    }
   // cout << a.size() << " " << b.size() << endl;
   
    if(a[sid] >= b[sid]){
        cout << a[sid] << " " << b[sid] << endl;
        continue;
    }
    
    //cout << a.size() << " " << b.size() << endl;
    for(ll i=0; i<n; i++){
        if(a[i] == smallestElement[i] && (ans2.size() == 0 || a[i] < ans2[0])){
            ans1.pb(a[i]);
            ans2.pb(b[i]);
        }    
    }
    
    
    for(ll i=0; i<ans1.size(); i++)
        cout << ans1[i] <<" ";
    for(ll i=0; i<ans2.size(); i++)
        cout << ans2[i] << " ";
    
    cout << endl;
    
}
}


~~~~~
Your code here...

~~~~~

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Regarding the last sentence of editorial for F,

"explicit" formula
→ Reply