atcoder_official's blog

AtCoder Beginner Contest 474 Announcement
By atcoder_official, history, 6 weeks ago, In English

We will hold AtCoder Beginner Contest 474.

We are looking forward to your participation!

  • Vote: I like it
  • -16
  • Vote: I do not like it

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

I hope I could solve Task A~D.

→ Reply
»
6 weeks ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it -18 Vote: I do not like it

Irregular

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Hope not rubbish round.

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

Why is this ABC contest on Sunday instead of Saturday?

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i HOPE ...

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I hope it

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Thank god this contest starts on 12:10（UTC+8）（I have to go to school at 18:00）！

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why Sunday?

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Solve only A problem

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it -11 Vote: I do not like it

没人AK吗？（Chinese Students）

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Well,I solve the D.

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How do you solve E?Greedy?

→ Reply
  • »
    »
    5 weeks ago, hide # ^ |
     
    Vote: I like it -24 Vote: I do not like it

    我觉得是反悔贪心，先假设所有东西都不用优惠卷，然后依次按 $$$a_i - b_i$$$ 从大到小的顺序尝试将其用优惠卷购买，如果优惠卷不够，就可以尝试用原价额外购买 $$$a_i$$$ 最小的东西以获得足够的优惠卷（当然，前提是这样更划算）。我这样成功的 AC 了。

    I used Chinese to anser this question because I am not good at English. You can try to translate it by AI if you can not get it.

    → Reply
    • »
      »
      »
      5 weeks ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      You can look my submit

      my atcoder name is same codeforces

      I think my solution is easy

      I don’t go at English

      → Reply
      • »
        »
        »
        »
        5 weeks ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        bro why do chinese comments get downvoted fast? can anyone answer?

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

          I suspect that many of the downvotes come from Chinese users. They may feel that using Chinese in an English-language discussion is out of place. However, I don’t think there’s anything wrong with this comment, especially since the commenter explained that he used Chinese because his English isn’t very good.

          → Reply
      • »
        »
        »
        »
        5 weeks ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Yes, I saw some easier ways to solve this problem then mine.

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

    at the time of contest I thought of a similar idea as Atcoder ABC 437 C. But I had too little time so did not solve it.

    → Reply
»
5 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i am idiot.

zero...

0x3f.... > 1e18 :(

ac

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

**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
}
→ Reply
  • »
    »
    5 weeks ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it

    Sometimes you need to go above mx.

    Smallest counterexample has N=94.

    → Reply
    • »
      »
      »
      5 weeks ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 weeks ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like it 
        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.

        → Reply
        • »
          »
          »
          »
          »
          5 weeks ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 weeks ago, hide # ^ |
            ← Rev. 2  
            Vote: I like it +8 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, hide # ^ |
               
              Vote: I like it 0 Vote: I do not like it

              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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, hide # ^ |
                 
                Vote: I like it 0 Vote: I do not like it

                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.

                → Reply
        • »
          »
          »
          »
          »
          5 weeks ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
5 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why there's still no official editorial?

→ Reply
»
5 weeks ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

I hope I could solve Task A~C.

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply