Блог пользователя maroonrk

Автор maroonrk, история, 3 года назад, По-английски

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!

  • Проголосовать: нравится
  • +210
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +145 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

P.S. Not demanding anything, just curious.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Starts in 5 minutes.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

GG

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

When can we expect to see Cpp20 support for atcoder ?

»
3 года назад, # |
  Проголосовать: нравится +90 Проголосовать: не нравится

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 :(

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    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".

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    I did so,then I wasted 1 h.(

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Us Moment

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    "x is real"

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I see, I guess reading is not my strength

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

        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 ... :(

»
3 года назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

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".

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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;
	
}

`

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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;
    	
    }
    
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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.

»
3 года назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Sorry, for wrong post.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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...

~~~~~

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Regarding the last sentence of editorial for F,

"explicit" formula