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

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

До соревнования
Codeforces Round (Div. 3)
44:22:35
Зарегистрироваться »

→ Трансляции

CodeChef Starters 132 Solution Discussion

aryanc403

До начала 22:32:35

Codeforces Round 943 Solution Discussion

aryanc403

До начала 46:47:35

Всё →

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

№	Пользователь	Рейтинг
1	ecnerwala	3649
2	Benq	3581
3	jiangly	3578
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	tourist	3565
8	maroonrk	3531
9	Radewoosh	3521
10	Um_nik	3482

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

Всё →

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

№	Пользователь	Вклад
1	maomao90	174
2	awoo	165
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
8	SecondThread	146
10	pajenegod	145

Всё →

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

→ Прямой эфир

Детальнее →

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

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

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

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
12 месяцев назад
36

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

Написать комментарий?

Lyrically

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

+46

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

→ Ответить

Lyrically

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

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

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

← Rev. 2 →

+11

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

→ Ответить

Aabhas99

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

+14

DDOS again :(

→ Ответить

absolute-mess

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

+36

Anti-DDoS is very hard to break!

→ Ответить

Mr_7ammoda

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

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

→ Ответить

213976

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

How to solve D?

→ Ответить

Mr_7ammoda

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

-9

Digit DP

→ Ответить

cosenza

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

+18

it's not digit DP

→ Ответить

Scyther_07

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

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

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

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

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

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

→ Ответить

absolute-mess

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

← 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

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

There is no username that goes by "perfect".

→ Ответить

coderdhanraj

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

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

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

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

→ Ответить

Elagamy

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

← Rev. 5 →

I've solved it with a greedy technique.

My Algorithm is:

1- Compute the current value of string S in decimal representation and neglect all '?' symbols in it

2- Iterate over string S from MSB (most significant bit) and check if the current symbol is '?' and the (value of current value of S + pow (2, size(s)-idx-1)) is less than or equal to N, then I'll flip this symbol to 1 and add pow (2, size(s)-idx-1) to current value of s, else I will flip it to 0.

My Source code

→ Ответить

saturnbored

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

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

→ Ответить

Phantom_Performer

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

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

→ Ответить

18o3

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

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

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

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

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

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

→ Ответить

Olerinskiy

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

+11

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

→ Ответить

volcano8

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

← 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

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

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

→ Ответить

volcano8

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

Oh, thank you!

Sorry for the late reply, I am not online very much. I appreciate the assistance.

→ Ответить

_irohasu_

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

-24

I found D much harder to solve than E. 😿

→ Ответить

SummerSky

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

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

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

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

→ Ответить

Nhi_Ho_Rha

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

Can't we use recursion on all the candies, because the maximum count is 18. I followed your first and second as it is but my solution got TLE.

→ Ответить

omeganot

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

+16

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

→ Ответить

MarcosK

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

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

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

← 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

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

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

→ Ответить

Lucky_zajasi

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

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

→ Ответить

Killever

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

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

Время на сервере: 30.04.2024 21:12:26 (f1).

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

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