We will hold AtCoder Beginner Contest 138.
- Contest URL: https://atcoder.jp/contests/abc138
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20190818T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: camypaper, evima, sheyasutaka, tozangezan, yosupo
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-600.
We are looking forward to your participation!
Oh~All of us can participate in the Codeforces contest after finishing the Atcoder Beginner Contest,that's so good!
Good luck to all && High rating :D
(Unofficial) I'll do English problem discussion streaming starting from 13:50 UTC (10 minutes after the contest): URL
If you are interested but you are participating in the CF round, check it after the contest!
Will you do it for codeforces (div1 ?) too?
No, it's too late here
Problem statements on AtCoder be like
when you finished the contest in less than 30 min. so you make a meme in free time during the contest
And Cheetas like you there to reply
i am getting TLE on E problem any solution i am doing it in 1 traversal dont know why ?? please help
my first 32 test cases out of 40 get passed & rest of them are giving WA
:'(
Maybe you did not use long long?
no long-long in Python :(
when you first time give AtCoder & get rank under 500....#Durgesh the coder
same here i have used binary search as well then 40 passed but 8 are giving TLE i dont know why ?? anyone know the solution please share
yup use c++ i was using python in c++ it passed @chaudhary use c++ it will be passed and do the binary search . not using two loops hope it helps ?
I was also using python & binary search....sed lyf :'(
Actually, I didn't participate in the contest.
In Atcoder infinity is always an even number
ABCDE is quite easy, F is so hard.
getting TLE in both D and E ;(
To avoid tle in D you can use path prefix sums and do dfs just once.
This is exactly what I did...
You are Purple ...but question E is hard for a noob like me
E is kinda classical problem, thus is easy to those who have solved similar problem
PS: F is hard XD
Could you give me a link to a problem that is similar to E on a education oriented site. Thanks
I didn't realized that the contest is not ended yet.
even if it is you shouldn't publicize it in midst of contest
Don't you think it would have made more sense to post this comment after the contest ends? I think you should delete the comment so that others won't gain an unfair advantage.
How to solve F? I was thinking with digit dp but was unable to think the states. Please Help
Quick editorial:
maybe easier to understand without your template...
Thanks for the quick explanations.
In F, could you please explain a little more on These constraints mean that if we construct the bits of x and y from most significant to least significant, they should share their leading bit and the set of "on" bits in x should be a subset of the "on" bits in y. I mean how do we infer this? Also what exactly does this mean the set of "on" bits in x should be a subset of the "on" bits in y.. An example would really help! Thanks in advance!
We need $$$y \geq x$$$ with $$$(y \textrm{ XOR } x) = (y \textrm{ MOD } x) = y - x$$$. $$$(y \textrm{ XOR } x) = y - x$$$ is true when $$$y$$$'s binary representation has $$$1$$$'s in all of the places that $$$x$$$'s binary representation does. $$$(y \textrm{ MOD } x) = y - x$$$ is true when $$$x > y/2$$$, which (in combination with the other requirement) simply means that they should have the same leading bit.
Hi can you tell what is wrong in my approach I am using DP for problem C just like in matrix chain multiplication.
Here is my codecode
I was able to solve D and E but not C can you please help me..
I don't think there's a need for dp here.
I used a greedy approach which is to build a multiset or priority queue and we just can take the minimum $$$2$$$ elements and remove them from the queue and push the new value $$$(x+y)/2$$$ to the queue until we end up with one element only which wil be the answer.
Code
the main logic behind taking the smallest element first is that every time you take two number and add it's sum to by taking half to another number the relevance of first number to your new sum becomes 1/4 then 1/8 then 1/16 .......and so on. that's why u would always like to decrease the smallest u have and add the largest numnber to your answer as here u want the sum to be maximum if they would have asked for minimum u would have gone another way round.that's why the approach of using priority_queue, multiset or sorting works. I hope this helps
I don't think your solution is not standard, this problem just sorts arrays and solve
even though i know memset can fuck me up at times, why do i still use it :|
ps:F anyone ?
How to solve F,it seems to be a math problem
How to solve F?
How to solve E and F?
For Task E, I used Binary Search just like others. But still I am getting TLE in 4 test cases even in C++. I tried to think really hard, but could not find the problem. I would really appreciate if someone can help me in this regard.
~~~~~
include <bits/stdc++.h>
using namespace std;
define ll long long
int main() {
string s,t; cin>>s>>t;
ll n = s.length(), m = t.length();
vector<vector > ids(26,vector());
for(ll i=0;i<n;i++) { ids[s[i]-'a'].push_back(i); }
ll prev = -1, ans=-1, count=0;
for(ll i=0;i<m;i++) {
} cout<<ans+1<<endl; return 0; } ~~~~
I think its because of vector cur = ids[a -'a'] if there is 10 ^ 5 elements in ids[a — 'a'] and copying it 10 ^ 5 times from ids[a — 'a'] will be TLE, i think you can binary search for just ids[a — 'a'] without creating new array
Thank You so much. If you would not have told this, I would have been still wondering and be in doubt. Thank You really.
For me same problem with E.
I still don't get it why it does not work. I inspected several solutions. They all do more or less the same. But mine does not work :/
Can somebody point me in the right direction, or, once again post the link to the testcases? Thanks!
https://atcoder.jp/contests/abc138/submissions/7001559
PS: And I think that code looks really nice, fairly simple solution ;)
You are doing upper_bound every time
Let's check this test case
s = contesc, t = c
in line 53 you take ll ans2 = 0, and in this test case your answer would be 7 instead of 1
You need to take ans2 as -1 in the start
OMG... Thank you.
Will test cases be made available?
Problem E can be solved without binary search. My sub
This is O(n^2). Looks like testcases are weak chokudai
aaaaaaaaaaaaaaaaaaa..........aaaab (a 99999 times then b)
bababababa......................ba (alternating ba)
where editorials can be found for this contest??
You have to switch to japanese version in order to find it
how can i get Japanese editorials?
https://img.atcoder.jp/abc138/editorial.pdf
can anyone please explain logic behind Question D . It will be very helpful
In question D, my BFS solution got AC but now it is failing for 3 test cases added after competition, whereas DFS is getting AC unable to find the glitch, please help. My DFS and BFS codes are given below:
Does your BFS solution fail because of Time Limit? Or Wrong Answer?
In DFS code, you linked both (a[x], a[y]) and (a[y], a[x]), though only (a[x], a[y]) in BFS one.
Additional testcases represent a tree structure like "1-3-2" (V = {1, 2, 3}, E = {(1, 2), (2, 3)}), which x isn't a parent of y.
Try the case below. AC is "1 3 1" and DFS returns it but your BFS return "1 2 1".
3 2
1 3
2 3
1 1
2 2
Thank you, I finally know where I am wrong, I thought the data was given by the structure of the tree....
Is there tutorial part for Atcoder Problem ?