### chokudai's blog

By chokudai, history, 11 months ago,

We will hold AtCoder Beginner Contest 180.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

• +40

 » 11 months ago, # |   +39 Wow that's an early announcement
•  » » 11 months ago, # ^ |   0 yessir
•  » » 11 months ago, # ^ |   0 I think I'll have to get that contest reminder app.
•  » » » 11 months ago, # ^ |   0 thats y we have google calendar.
 » 11 months ago, # |   0 How to solve D?
•  » » 11 months ago, # ^ |   +3 The idea is that it will only be optimal to use Kakomon Gym (multiply by A) a few times, after which it will always be better to add instead of multiply. You can simulate the first part while x*a <= x+b, then use division to find out the number of operations of the second type to do.
•  » » » 11 months ago, # ^ |   0 Can you share your code?
•  » » » » 11 months ago, # ^ |   0
•  » » » » » 11 months ago, # ^ |   0 Any Idea why this submission gets WA?https://atcoder.jp/contests/abc180/submissions/17481021
•  » » » » » » 11 months ago, # ^ |   0 Because x*a overflow when x = 10^18 && a>10 something like that
•  » » » » » 11 months ago, # ^ |   0 can you please tell me why you subtract 1 from the answer(int ans) at the end??
•  » » » » » » 11 months ago, # ^ | ← Rev. 2 →   +8 The way the code is implemented has the 2 following cases: 1. x stopped right at y, i.e, x == y; 2. x exceeds y after the last increase by b operation, i.e, x > y.This is reflected in the else block inside the while loop. We add 1 to take the remaining y — (y — x) / b * b into consideration. So this add 1 makes x exceeding y. In both case, we must have 1 fewer operation to make x strictly smaller than y. So we subtract 1.
•  » » » » » » » 11 months ago, # ^ |   0 oh! thanks, got it!!
•  » » » » » 11 months ago, # ^ |   0 can you explain LLONG_MAX/x >= a why this was done in if condition?
•  » » » » » » 11 months ago, # ^ |   0 To prevent overflow. If that condition is not my, then x*a will overflow, which can lead to wrong answers and infinite loops.
•  » » » » » » » 11 months ago, # ^ |   +8 ohk thank you so much got it!!
•  » » » 11 months ago, # ^ | ← Rev. 4 →   0 idk why i thought of dp here may be coz i thought inorder to maintain maximum exp you gotta maintain minmimum str
•  » » » 11 months ago, # ^ |   0 Can you prove why that strategy is optimal?
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 Just brute force over all the steps,and calculate the maximum. By steps I mean, steps until you reach target by visiting 1st place some k times and visiting 2nd place to complete the remaining EXP. Check for overflows while dong so.Solution Sorry for my English.
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 My submission Can someone suggest any modification to my code for task D,I am still getting WAs in 2 test cases.
 » 11 months ago, # |   0 How to solve B(only Euclidian distance part) and D ??
•  » » 11 months ago, # ^ |   +3 Sum up the squares of elements in a long long, then cast to long double and take square root.
•  » » » 11 months ago, # ^ |   +1 Can you please explain how to solve D and how to avoid overflow condition?
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   +1 while(a*x <= x+b && a*x < y) This condition was giving me TLE in one case but when I did this while(a*x <= x+b && a*x < y && a
•  » » » » » 11 months ago, # ^ |   +4 using a*x < y will result in integer overflow for larger cases, to avoid that u should use a < y/x, please see https://www.geeksforgeeks.org/check-integer-overflow-multiplication/
•  » » » » » 11 months ago, # ^ |   0 Did the same mistake
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 Can you explain why this works please? i.e why casting to long double works for B.
•  » » » » 11 months ago, # ^ |   0 Only cause is range !!
•  » » 11 months ago, # ^ |   0 The easier thing would be to use Python for questions like D, or Java's BigInteger.
•  » » » 11 months ago, # ^ |   0 or you can cast long long to (__int128) while comparing to prevent overflows
•  » » » » 11 months ago, # ^ |   0 I did using logs .. dunno if that was actually a good practice or not
•  » » » 11 months ago, # ^ |   0 you can use double in c++ also and convert to int final ans as i did my submission
 » 11 months ago, # |   +9 Solution for F, anyone?
•  » » 11 months ago, # ^ |   +29 Let DP[n][m][b] be the number of ways to build a graph with n labeled nodes and m unlabeled edges with b being a flag for restricting the size of the maximal connected component.From there at each iteration and to avoid double counting you only look at the components covering the first node.For example if I want a component of size 5 and n = 10 first I find the number of ways I can choose nodes to form this component which is 9 choose 4 (node #1 is already included). Then I find the number of way to build a path (5! / 2) or a cycle (4! / 2) and call the appropriate state.
•  » » » 11 months ago, # ^ |   +13 I didn't get how are you avoiding double counting?
•  » » » » 11 months ago, # ^ |   0 cause if you reverse a chain, the result will be the same as the origin, so there are k!/2 ways to form a chain with size k, or you will count a chain twice. as to circle, you should consider symmetry and shift, so there are k!/2/k = (k-1)!/2 ways to form a circle with size k.
•  » » » » » 11 months ago, # ^ |   +13 He is referring to the over counting of the total number of ways to make the connected components using DP, not the over counting of a particular component itself.
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   +5 sorry, i misunderstood it.for example, with node 1, 2, 3, 4 and 5, choose 1,2 to form a component, and then choose 3,4,5 to form a component. choose 3,4,5 to form a component, and then choose 1,2 to form a component. these 2 ways generate same graph, but if you count it more than once, then double counting happen.if you only look at the components covering the first node, you will only count the first way.
 » 11 months ago, # |   -19 How was E intended to be solved? I just copy pasted a DP code from stack overflow and calculated distances of graph[i][j] using the formula in the question and got AC.
•  » » 11 months ago, # ^ |   0 Travelling Salesman Problem using dynamic programming
•  » » » 11 months ago, # ^ |   -6 That's what I did, I am saying if it was meant to be solved in a simpler way.
•  » » » » 11 months ago, # ^ |   +1 Given that $n \le 17$, I guess the intended solution $O(n^{2} \times 2^{n})$ bitmask dp.
•  » » » » 11 months ago, # ^ |   +2 Well I guess we'll find out when(if) the editorial comes out
•  » » 11 months ago, # ^ |   0 It is a standard question of Dp with bitmasking.
•  » » 11 months ago, # ^ |   +3 Well, I just honestly implemented dp for traveling salesman problem... I guess it was the intended solution
•  » » 11 months ago, # ^ | ← Rev. 2 →   +11 I guess the main difference in the problem was to visit at least once, while in standard TSP it is exactly once.So consider if the problem was a general directed graph, then the standard DP solution would not have worked, but since the shortest path between two vertices, in this case, is the same as their direct edge between them, the problem had the exact same solution.
•  » » » 11 months ago, # ^ |   +11 Even for the general graph, we can run floyd warshall first, then the classic TSP. It's a shame I took 50 minutes in this problem.
•  » » » » 11 months ago, # ^ |   0 I never thought they would straight away give classic tsp for a problem at "E". Man .. I took so long to implement floyd warshall version of it .. . Should have tested with the classic version first
•  » » » » 11 months ago, # ^ |   0 Can you elaborate on the Floyd-Warshall + TSP Solution for general graphs, or share any resource to learn from.
•  » » » » » 11 months ago, # ^ | ← Rev. 3 →   +3 This is what I did in my submission in contest,now you would have run through comments that direct edge is always optimal in this problem which i never observed so instead what i did was to first apply floyd warshall on the graph with saving a "next" Matrix in order to trace the path when i move from a node to other because when I would do so unintentionally I would also visit some unvisited cities(maybe or maybe not). Now after doing this i just do normal tsp and updating the mask. However i did see printing some paths and saw that direct edges are the shortest ones but thought they have intentionally given such samples.
•  » » 11 months ago, # ^ |   +11 if n<=20 its 95% of the time bitmask dp
•  » » 11 months ago, # ^ |   0 Can you share the link? I searched for such one, but did not found any, and was not able to implement a bugfree version.
•  » » » 11 months ago, # ^ |   0 https://stackoverflow.com/questions/33527127/dynamic-programming-approach-to-tsp-in-javaI think this is rather lengthy after looking at people having much shorter codes.
•  » » » 11 months ago, # ^ |   +6
•  » » » 11 months ago, # ^ |   0 Found the bug, typed r-c instead of max(0, r-c) in distance function :/
•  » » 11 months ago, # ^ |   0 Can you share the link please?
 » 11 months ago, # |   0 Was solution to E was intended to be solved using floyd warshall and then tsp, or did I do some overkill ?
•  » » 11 months ago, # ^ |   0 I don't think you need floyd warshall. Since the distance metric used always gives shortest path between two vertices.
•  » » » 11 months ago, # ^ |   0 So basically it was just classic tsp ?
•  » » » » 11 months ago, # ^ |   0 Yes. That's what I did. https://atcoder.jp/contests/abc180/submissions/17473708
•  » » 11 months ago, # ^ | ← Rev. 2 →   +14 I solved it using dp hint1use $dp(int \; lst, vector \; \; v, bool \; isGoingBack)$$lst$ means last city we visit$v[i]$ shows we visited city $i$ before$isGoingBack$ means : are we visited all and going back to 1 hint2use hash for v in dpmy code : Code#include using namespace std; const int N = 17, M = 272144; int x[N], y[N], z[N]; int dp[M][N]; int dis(int f, int s) { return abs(x[f] - x[s]) + abs(y[f] - y[s]) + max(0, z[s] - z[f]); } int solve(int lst, vector v, bool is_back = false) { if (is_back) { if (lst == 0) return 0; } int h = 0; for (int i = 0; i < v.size(); i++) { h *= 2; h += (int)v[i]; } h *= 2; h += (int)is_back; if (dp[h][lst] != -1) return dp[h][lst]; bool f = true; for (auto x : v) if (!x) f = false; if (lst == 0 && f) { return 0; } if (f) { for (int i = 0; i < v.size(); i++) { v[i] = false; } v[lst] = true; return solve(lst, v, true); } int ans = INT_MAX; for (int i = 0; i < v.size(); i++) { if (v[i]) continue; v[i] = true; int t = solve(i, v, is_back) + dis(lst, i); ans = min(ans, t); v[i] = false; } return dp[h][lst] = ans; } int32_t main(){ int n; cin >> n; for (int i = 0; i < n; i++) { cin >> x[i] >> y[i] >> z[i]; } for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) dp[i][j] = -1; vector v; for (int i = 0; i < n; i++) v.push_back(false); v[0] = true; cout << solve(0, v); } 
 » 11 months ago, # | ← Rev. 2 →   -8 This is my solution to B problem, can anyone tell me why it's WA My codeEdit: After Changing everything to long long, it is working now, even long double didn't work, can anyone explain to me why long long is working and remaining are not.
•  » » 11 months ago, # ^ |   +3 Try long double instead of double, and sqrt instead of pow.
•  » » » 11 months ago, # ^ |   0 Tried now, but still shows WA, can you please help me out and point the mistake in this
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   0 You have to take max of absolute of arr[i] instead of just arr[i] to calculate 3rd distance. This is the same which I did and llost 700 ranks bcoz of thatEDIT: sorry I overlooked that part.
•  » » » » » 11 months ago, # ^ |   0 Hey, but I did that right, as you can see, while taking the input of the numbers, if the number is negative, I have written -arr[i].
 » 11 months ago, # |   +13 How to solve Problem F? DP?
•  » » 11 months ago, # ^ |   0 Yes
 » 11 months ago, # | ← Rev. 2 →   0 how to solve C? UPDATE:got it.
•  » » 11 months ago, # ^ |   0 find divisors of number in root(N) time, add it to a list ,sort the list and print it.
•  » » 11 months ago, # ^ |   0 So, first, you have to find the numbers which are divisible by the given number N. For this, we can run a for loop from 1 to N, but you will notice that we shorten up this process, when you get a number i, which is divisible by N, you will also get a number N / i, which is also a divisor of N.when you need to essentially go up to sqrt(n) numbers, as you will cover everything divisor by that time. (Note that a square number wont 2 divisor at sqrt(n)) for(int i = 1; i * i <= n; i++) { if(n % i == 0) { cout << i << '\n'; if(i * i != n) cout << n / i << '\n'; } } But, now you need to print it in the ascending order, just take a vector, and push_back all the (N / i) numbers, print it in the reverse order. vector div; for(int i = 1; i * i <= n; i++) { if(n % i == 0) { cout << i << '\n'; if(i * i != n) div.push_back(n / i); } } for(int i = div.size()- 1; i >= 0; i--) cout << div[i] << '\n'; 
 » 11 months ago, # | ← Rev. 3 →   0 Hi, could someone point out my mistake in BEdit: But x[i] is long long right?
•  » » 11 months ago, # ^ |   0 x[i]*x[i] may overflow type cast to long
 » 11 months ago, # |   0 Could someone help me.. i dont know why my dp runs incorrectly :< https://paste.ubuntu.com/p/nrYYHqvxw7/
 » 11 months ago, # | ← Rev. 2 →   0 TLE AC Solution after contest 4th problem why anyone?
•  » » 10 months ago, # ^ |   0 Because a * x will overflow for big cases, leading to a negative number and an endless condition
 » 11 months ago, # |   0 How to solve C
•  » » 11 months ago, # ^ |   0
•  » » 11 months ago, # ^ |   0 Count the number of divisors of a number.Here
 » 11 months ago, # |   0 How to solve d please explain anyone?? i was thinking it was dp but other's solution just amazed me
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 Solution Just think about a short case and try to work on it. Keep a check on overflows.
 » 11 months ago, # |   0 Why this solution gets TLE while this gets AC? Using int instead of long long should result in wrong answer instead of TLE, then what other reasons behind it?
•  » » 11 months ago, # ^ |   0 For bigger values of n, i * i will overflow and will result in i * i <= n being true.
•  » » » 11 months ago, # ^ |   0 Great! Thanks.
 » 11 months ago, # |   0 Hi, can you explain to me why i got WA in problem B? Both sample cases work;n = int(input()) x = list(map(int, input().split())) y = list(map(abs, x)) print(sum(y)) #1 res = [a ** 2 for a in x] j = sum(res) #2 print(math.sqrt(j)) print(max(x)) #3
•  » » 11 months ago, # ^ |   0 print(max(y)) instead of print(max(x)) #3
•  » » » 11 months ago, # ^ |   0 Thank you, it works!
 » 11 months ago, # |   0 Please can somebody explain why using even unsigned long long is giving WA on D? I tried different values of x,y,a,b and checked but they were all running fine, but during contest ((ull)x*a<2e18) dosen't work but ((double)x*a) worked; why??
•  » » 11 months ago, # ^ |   0 consider x as 1e18 and a as 1e9. It will overflow range of unsigned long long
•  » » » 11 months ago, # ^ |   0 Thanks
 » 11 months ago, # |   0 How to solve E?
•  » » 11 months ago, # ^ |   0 Use dynamic programming with bitmask, dp[i][j] is the min cost of visting all cities specified by state i with the last visiting city as j. For a given dp[i][j], if we already know its result, we use it to make the next hop. For all valid hops from a city that has been included in i, to a city j from 0 to n — 1, update dp[next][j] where next is i | (1 << j). The final answer is dp[(1 << n) — 1][0].
•  » » » 11 months ago, # ^ |   0 Can you give me your AC code? Thank you.
•  » » » » 11 months ago, # ^ |   0
 » 11 months ago, # |   0 t = int(input()) li = list(map(int, input().split()))manhattan_distance = 0 for i in range(t): manhattan_distance = manhattan_distance + abs(li[i])print(manhattan_distance)import math euclidian_distance = 0 for i in range(t): euclidian_distance = euclidian_distance + (li[i]*li[i])print(math.sqrt(euclidian_distance))chebyshev_distance = max(li) print(chebyshev_distance)Would anyone debug it please?
•  » » 11 months ago, # ^ |   0 li[i]*li[i] may overflow .type cast it into long.
 » 11 months ago, # |   0 I have a problem with B. I am using long long and long double wherever needed and I am still getting compilation error. I think I am getting an error while using "abs(x)". Here's my code, plz help : problem B
•  » » 11 months ago, # ^ |   +3 There are a few problems:The error with abs function is due to ll being defined as unsigned.Then after this, you will be getting a WA because you have your cd as cd=max(cd,x) instead of cd=max(cd,abs(x))After that, you still are getting a WA because you are submitting problem B's solution for problem A :)
•  » » » 11 months ago, # ^ |   0 Brooo.... Thank you a lot for the help. And I can't stop laughing for submitting problem B's solution for problem A. Damn. Thanx again.
 » 11 months ago, # |   0 Hello guys, I need your help on my solution to the third problem. Here's a link to my submission, I kept getting TLE. How could I have optimized my solution? https://atcoder.jp/contests/abc180/submissions/17476685On the second problem, I was flat out getting Wrong Answer. What was wrong also? https://atcoder.jp/contests/abc180/submissions/17474677Thank you very much. PS; ABC 180 was my first CP contest, so also, any general tips for CP will do.
•  » » 11 months ago, # ^ |   0 For C problem,You are running a loop N times which is too slow as N can be upto 10^12.Here you need to run a loop till sqrt(N) and then it will work. Here is my submission:-https://atcoder.jp/contests/abc180/submissions/17445269To understand why this works you can see this tutorial:-https://www.youtube.com/watch?v=ga9N_ey4La4&list=PL2q4fbVm1Ik4liHX78IRslXzUr8z5QxsG&index=2
•  » » » 11 months ago, # ^ |   0 Thank you very much
•  » » » 11 months ago, # ^ |   0 Still getting TLE, but a few more are reading AC https://atcoder.jp/contests/abc180/submissions/17578344
•  » » » » 11 months ago, # ^ |   0 Several things are wrong.Vector should be long long type.U should push j only if i != j which means if i is not the square root.And i and j should be long long type also.
•  » » » » » 11 months ago, # ^ |   0 Finally, I solved it. Thank you!Would you tale a look at my solutiOn to B? https://atcoder.jp/contests/abc180/submissions/17474677
•  » » » » » » 11 months ago, # ^ |   0 You need to take an array as input but you have taken only 2 numbers as input.
•  » » » » 11 months ago, # ^ |   0 i*i may overflow.It is better you write as for(long i=1;i*i<=n;i++) or for(int i=1;i<=Math.sqrt(n);i++)Secondly,You need to count distinct divisors.For eg: 4 has 3 divisors(1,2,4) but yours will print 4 as you do not check the condition that i==n/i or not.
 » 11 months ago, # |   0 A question: How much would be the corresponding rating of problems C, D and E on codeforces?
 » 11 months ago, # |   0 When will the editorials be posted?
 » 8 months ago, # |   0 hello everyone, while solving B question , I took an array arr[n] of int because the numbers lie in range of 10^-5 and 10^5...I think the numbers can easily fit in int....but it gives me WA .. but when i change it to long long int , it gives me AC...why so??My submission : https://atcoder.jp/contests/abc180/submissions/19424524Code :void solve() { long long int n; cin>>n; `**int arr[n];**// when i change it to long long int, it gives me AC, but why? since the constraints are not big, it should have worked fine with int also for(lli i=0;i>arr[i]; long long int m=0; long long int e=0; int c=0; for(lli i=0;i