パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301） Announcement

→ Обратите внимание

До соревнования
Codeforces Round 986 (Div. 2)
06:02:23
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Codeforces Round 986 (Div 2) - Solution Discussion

Shayan

До начала 08:07:21

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301） Announcement

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

We will hold パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）.

Contest URL: https://atcoder.jp/contests/abc301
Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230513T2100&p1=248
Duration: 100 minutes
Number of Tasks: 8
Writer: yuto1115, kyopro_friends, evima, physics0523, Nyaan, m_99
Tester: cn449, leaf1415
Rated range: ~ 1999

The point values will be 100-200-300-400-475-500-600-625. (Since this ABC, we adjust the point values depending on problems.) We are looking forward to your participation!

chokudai
18 месяцев назад
36

Комментарии (33)

Показать архивные | Написать комментарий?

Lyrically

18 месяцев назад, # |

+46

Finally Atcoder is adjusting point values depending on their difficulties:P

→ Ответить

Lyrically

18 месяцев назад, # ^ |

Moral of this contest: Never use alts to try to consume all the penalties for your main account. (even with unrated register) If so, both accounts will be deleted automatically.

→ Ответить

volcano8

18 месяцев назад, # |

← Rev. 2 →

+11

Perfect, 502 Bad Gateway and 504 Gateway Time-out was all we needed!!

→ Ответить

Aabhas99

18 месяцев назад, # |

+14

DDOS again :(

→ Ответить

absolute-mess

18 месяцев назад, # |

+36

Anti-DDoS is very hard to break!

→ Ответить

Mr_7ammoda

18 месяцев назад, # |

Imagine Naming a problem Anti-DDoS and the server suffers from DDoS problem

→ Ответить

213976

18 месяцев назад, # |

How to solve D?

→ Ответить

Mr_7ammoda

18 месяцев назад, # ^ |

-9

Digit DP

→ Ответить

cosenza

18 месяцев назад, # ^ |

+18

it's not digit DP

→ Ответить

Scyther_07

18 месяцев назад, # ^ |

Can you point out the mistake in this approach? We first replace all '?' with '0' and store indices of all '?' in a vector. Then we iterate on every element x of the vector and check if setting xth bit to 1 would give a number smaller than or equal to N. If you get a valid number, change '0' to '1' at that index.

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define sz(a) (ll)(a.size())
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

ll binTodec(string x){
    ll k = 1, ans = 0;
    while(!x.empty()){
        int b = x.back() - '0';
        ans += b*k, k*=2, x.pop_back();
    }
    return ans;
}
void solve(){
    vector<int> v;
    ll n, k, x; string s; 
    cin >> s; cin >> n;
    k = sz(s);
    for(int i=0; i<k; ++i) 
        if(s[i]=='?') 
            s[i] = '0', v.push_back(k-i-1);

    x = binTodec(s);
    if(x > n) {cout << -1; return;}
    for(auto i: v)
        if((x | (1 << i)) <= n) 
            x = x | (1 << i);
    cout << x;
}
signed main(){
    IOS
    solve();
}

→ Ответить

Scyther_07

18 месяцев назад, # ^ |

Never mind, I got it. It should be 1LL << i instead of 1 << i.

Got WA x 2 due to this small mistake. :(

→ Ответить

Mr_7ammoda

18 месяцев назад, # ^ |

I didn't know that there exists an easier solution, I just said how I solved it.

→ Ответить

absolute-mess

18 месяцев назад, # ^ |

← Rev. 2 →

+29

You guys did DP?

I did it by greedy

    string s;   cin>>s;
    int n; cin>>n;
    int val=0;
    fi(s.size()) {
        if(s[i]=='1') 
        val+=(1LL<<(s.size()-1-i));
    }
    if(val>n) {
        cout<<"-1\n";  return;
    }
    vi ind;
    int sz=s.size();
    fi(s.size()) {
        if(s[i]=='?') 
        ind.push_back(sz-1-i);
    }
    fi(ind.size()) {
        if(val+(1LL<<ind[i])<=n) {
            val+=(1LL<<ind[i]);
        }
    }
    cout<<val<<"\n";

EDIT- My username is actually defining me, I did mess up three times before AC

→ Ответить

Scyther_07

18 месяцев назад, # ^ |

There is no username that goes by "perfect".

→ Ответить

coderdhanraj

18 месяцев назад, # ^ |

Implementation :( I unwanted memoized it with dp my submission.

DDOS didn't get chill with me.. when I play good round gets unrated and when bad gets rated :(

→ Ответить

cp_first

18 месяцев назад, # ^ |

← Rev. 3 →

Solution of D

#include<bits/stdc++.h>
using namespace std;
#define int long long

int bin_to_int(string s, int n) {
    int ans = 0, base = 1;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '1') ans += base; // ignoring ? and 0s
        base *= 2;
    }
    return ans;
}

signed main() {
    string s; cin >> s;
    int k; cin >> k;
    int n = s.size();
    int num = bin_to_int(s, n);
    
    for (int i = 0; i < n; i++) {
        if (s[i] == '?') {
            int t = (1ll << (n - 1 - i));
            if (num + t <= k) num += t;
        }
    }
    if (num > k) cout << -1 << "\n";
    else cout << num << "\n";
}

→ Ответить

saturnbored

18 месяцев назад, # ^ |

I tried solving it using DP. Here is my solution (in case, you are interested).

→ Ответить

Phantom_Performer

18 месяцев назад, # |

Can I somehow download the test case? problem E, last test.

→ Ответить

18o3

18 месяцев назад, # ^ |

I also was getting WA on that test case. I had a typo in my solution. While checking the distance from the starting point to the goal, I was doing $$$<t$$$ instead of $$$<=t$$$

→ Ответить

Believe

18 месяцев назад, # ^ |

I faced the same problem,

I thought he had to stop once he reached the Goal square (meaning he can't visit the goal square multiple times). This was giving WA.

Maybe the wording of the question could have been better :(

→ Ответить

Phantom_Performer

18 месяцев назад, # ^ |

I thought exactly the same lol, could not figure out what the mistake was for 1 hour.. Thanks!

→ Ответить

Olerinskiy

18 месяцев назад, # ^ |

+11

Explanation for sample 1 shows that you can move through the goal square

→ Ответить

volcano8

18 месяцев назад, # |

← Rev. 3 →

Why does my code fail 2 out of 34 cases in problem C? Is there some edge case I am not considering?

Python: https://atcoder.jp/contests/abc301/submissions/41383662

C++: https://atcoder.jp/contests/abc301/submissions/41382728

→ Ответить

coderdhanraj

18 месяцев назад, # ^ |

← Rev. 2 →

Counter:

Input:  
ttttac
@@@tac
Output:
No
Correct Output:
Yes

You should reduce firstone[i] by 1 when firstone[i] > secondone[i] similar for secondone[i].

→ Ответить

_irohasu_

18 месяцев назад, # |

-24

I found D much harder to solve than E. 😿

→ Ответить

SummerSky

18 месяцев назад, # |

My solution to problem E is as follows.

use bfs(two times) to find the minimum distance from S to any cell, and from G to any cell;
use bfs again, to find the distance between any two cells with candies;
use dp[st][last], where st is the state of bitmask whose 1s denote that these candies have been taken, and last denotes the last candy that we take, and this dp could be computed with the help of a queue.
from each dp[st][last], we compute the total distance to reach G, and if it is <= T, then we could update the maximum number of candies that we can take.

Is this the intended solution or there is some simpler one.

→ Ответить

weakestOsuPlayer_244

18 месяцев назад, # ^ |

you just re-invented the traveling salesman problem. Congrats!

→ Ответить

omeganot

18 месяцев назад, # |

+16

didnt get in contest but f was fun, thanks to authors

→ Ответить

MarcosK

18 месяцев назад, # |

Something really weird happened to me in problem C today. I got WA and I lost almost the entire contest trying to find what was wrong with my code. Now I managed to get AC by changing only one line in my code:

WA: Link
AC: Link

The only difference is how I iterate the string "atcoder". I guess in my first code there is some kind of undefined behavior. Does anyone know why iterating with for(auto c:"atcoder") is wrong?

→ Ответить

llc5pg

18 месяцев назад, # ^ |

← Rev. 3 →

+30

Please run the following snippet in AtCoder's custom test page:

Spoiler

#include <bits/stdc++.h>
using namespace std;
int main() {
  string p = "atcoder";
  int i=0;
  for(auto c:"atcoder")
    cout << i++ << " ";
  cout << "\n";
  i = 0;
  for(auto c:p)
    cout << i++ << " ";
  cout << "\n";
}

→ Ответить

Atlas

18 месяцев назад, # ^ |

That's because in the first case, "atcoder" is considered as a character array and not as a string.

→ Ответить

Lucky_zajasi

18 месяцев назад, # |

May I ask when the data for abc301 will be available? Thank you.

→ Ответить

Killever

15 месяцев назад, # |

How to solve F? tutorial hard to grasp.
I reversed the string and was looking for SoDD, I can maintain capital followed by small letter So but not sure how to maintain two equal capital letters DD in the DP solution?
https://atcoder.jp/contests/abc301/tasks/abc301_f

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 10.11.2024 12:32:39 (j2).

Десктопная версия, переключиться на мобильную.

При поддержке