Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

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

Автор atcoder_official, история, 2 месяца назад, По-английски

We will hold AtCoder Beginner Contest 474.

We are looking forward to your participation!

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

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hope I could solve Task A~D.

»
2 месяца назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

I hope I solve A,B,C,D,E.

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Hopefully I solve A,B,C,D!!

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hope I will solve A,B,C,D.(%%%) (I am a Chinese student)

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится -18 Проголосовать: не нравится

Irregular

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Hope not rubbish round.

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится -10 Проголосовать: не нравится

Why is this ABC contest on Sunday instead of Saturday?

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

i HOPE ...

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hope that we won’t get another TERRIBLE problem like last time’s Problem D.

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

hope i can wirite A,B,C,D.my Rated is to low

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hope it

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Thank god this contest starts on 12:10(UTC+8)(I have to go to school at 18:00)!

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Why Sunday?

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Maybe I can't solve D,I think it's hard.

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Solve only A problem

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится -11 Проголосовать: не нравится

没人AK吗?(Chinese Students)

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Well,I solve the D.

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

YESSSS Finally solved A-D!!! I think I had the idea for E but couldn't implement in time

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How do you solve E?Greedy?

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

**HOW F?61/71 **

#include<bits/stdc++.h>
#define I return
#define AK 0
#define IOI ;
using namespace std;
long long t, n, mx, m, k, a[1234567], z = 1, ans;
vector<long long>g[234567];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i], mx = max(mx, a[i]);
		for(int j = i + i; j <= n; j += i)g[j].push_back(i);
	}
	for(int i = n; i >= 1; i--) {
		if(!z)break;
		k = 0;
		if(a[i] < mx) {
			k = mx - a[i], a[i] = mx, ans += k;
			for(int j : g[i]) {
				a[j] += k;
				if(a[j] > mx)z = 0;
			}
		}
	}
	if(z)cout << ans;
	else cout << -1;
	I AK IOI
}
  • »
    »
    2 месяца назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится

    Sometimes you need to go above mx.

    Smallest counterexample has N=94.

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

      Would you like to share with us that counter example. Really curious to know what is it. Thank you so much!

      • »
        »
        »
        »
        2 месяца назад, скрыть # ^ |
         
        Проголосовать: нравится +3 Проголосовать: не нравится
        94
        1 24 32 36 39 40 41 42 43 43
        44 44 44 45 45 45 45 45 46 46
        46 46 46 46 46 46 46 46 46 46
        46 47 47 47 47 47 47 47 47 47
        47 47 47 47 47 47 47 47 47 47
        47 47 47 47 47 47 47 47 47 47
        47 47 47 47 47 47 47 47 47 47
        47 47 47 47 47 47 47 47 47 47
        47 47 47 47 47 47 47 47 47 47
        47 47 47 47
        

        Correct output: 47.

        Choose each index from 48 through 94 once; every element becomes 48.

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

          Thank you so much for your kind reply, a really beauitful counter example!!

          By the way, would you like to tell (teach) us, why intuitively the above solution is wrong?

          Because that approach is very very intuitively correct, at least for me.

          What kind of mind trap did I fall into?

          • »
            »
            »
            »
            »
            »
            2 месяца назад, скрыть # ^ |
            ← Rev. 2  
            Проголосовать: нравится +8 Проголосовать: не нравится

            The mind trap is accepting unproven statements into your logic.

            In the case of this problem, your entire algorithm is correct... assuming everyone should become mx. This part of the solution is so small that maybe you don't realize that this is unproven. And as demonstrated, it's actually really hard to come up with a counter example in your head.

            The solution is to develop a practice of having a proof behind every claim you use. It takes care, and it's definitely easier said than done. Even the best of the best will use unproven observations sometimes.

            Anyway, the knowledge that the target need not be mx finishes the problem for you. Now you just need to see if a feasible common value exists. The cost for a particular target will just be a linear function in terms of that target.

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

              Thank you so much for giving me such invaluable inspirations and suggestions. It is true that, somehow I believe "become max" is correct and consider it as a "fact". Yes, I should be more careful about this in the future.

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

                Thank you so much for giving me such invaluable inspirations and suggestions. It is true that, somehow I believe "become max" is correct and consider it as a "fact". Yes, I should be more careful about this in the future.

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

          Could you tell me how you think and make this corner case?

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Why there's still no official editorial?

»
2 месяца назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

I think that I am very weak than the bosses. I just passed problem G once! This maybe because this problem is so similar to abc454_e, and I solved it ago.

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится -7 Проголосовать: не нравится

I hope I could solve Task A~C.

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

For problem G, how to prove that a correct k satisfies k%2=0 ?