### Ashishgup's blog

By Ashishgup, history, 6 months ago, ,

Hi everyone!

It has been almost 2 years since I joined Codeforces, and it has been a great journey as a contestant. I now try to take a shot at problem-setting with my friend Mahir83.

With that said, I bring to your attention my new Codeforces Round #508 (Div. 2) that will take place on Sep/06/2018 18:35 (Moscow time). If your rating is less than 2100, this round will be rated for you; otherwise, you can participate out of competition.

I would like to thank Mahir83 for his help with preparing problems, _kun_ & 300iq for coordinating my round and Um_nik, senek_k, gritukan, Vovuh & BledDest for testing my problems. I would also like to thank MikeMirzayanov for Codeforces and Polygon platforms.

You will be given 6 problems and 2 hours to solve them. Scoring distribution will be announced later.

Good luck!

UPD: Scoring Distribution: 500-1000-1500-1750-2250-2750

UPD2: Editorial

•
• +784
•

•  » » 6 months ago, # ^ |   +41 It will be added there after today's contest
 » 6 months ago, # |   +183 Wow,an indian as a problem setter without any fest of their institution :))
•  » » 6 months ago, # ^ |   -17 Indian coders make great problems in codechef :)
•  » » » 6 months ago, # ^ |   +143 (Except when there was a "notorious coincidence"...)
 » 6 months ago, # |   +6 this will be amazing
 » 6 months ago, # |   -17 Sadly, another midnight contest for chinese participants.
 » 6 months ago, # |   +19 If your rating is less than 2100, this round will be rated for you. Codeforces says: You are registering "out of competition", reason: rating should be between 0 and 1,899 in order to register for the contest.
•  » » 6 months ago, # ^ | ← Rev. 2 →   +38 The registrations have been postponed to account for today's contest rating changes. This glitch will no longer be there.
 » 6 months ago, # |   +38 ashishgup i hope you saw round 507
 » 6 months ago, # |   +16 All the best Ashishgup!
 » 6 months ago, # |   +29 two consecutive contest in two days! it is wonderfull. (the day after tomorrow will be educational contest so three consecutive contest.) thank you codeforces .
 » 6 months ago, # | ← Rev. 2 →   +62 I am very excited about the contest by Ashishgup.Because of this blog on Quora.
•  » » 6 months ago, # ^ |   +43 Here in my college, if you don't have 75% attendance, they don't let you sit in for exams directly :( .Dedicating your time to do what you like is really good thing to follow.Looking forward to a good problem set :)
•  » » » 6 months ago, # ^ |   -6 Same here in my college :p
•  » » » 6 months ago, # ^ |   0 same in my college.
•  » » » 6 months ago, # ^ |   -24 not same in my university
•  » » » » 6 months ago, # ^ |   -49 Numb MotherFucker!!!
 » 6 months ago, # | ← Rev. 7 →   +17 How to approach D?
 » 6 months ago, # |   -28 i am to much happy about the contest due to problem setter is my neighbor
 » 6 months ago, # |   +9 congrats Ashishgup
 » 6 months ago, # | ← Rev. 2 →   +79 Indian problem setter on Codeforces. This seems to be the start of an era.This is sure going to be fun! Looking forward to more such rounds!
 » 6 months ago, # |   +18 I hope, we will see some interesting problems in this round. And, Ashishgup congratulations for your first contest as problemsetter...
•  » » 6 months ago, # ^ |   0 you turn green again. that's very sad to solved only one problem.
•  » » » 6 months ago, # ^ |   0 This was very sad for me because I lost my internet connection when I was about to submit the solution of problem B.
 » 6 months ago, # |   0 I joined Codeforces for over 2 years and even not enough color to be a problem setter...
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 I think, problem setting is not about any color, problem setting is an art. Keep trying...!!! ... Never lose your hope.
•  » » » 6 months ago, # ^ |   +5 Thank you, man. We're same color :D
 » 6 months ago, # |   +30 Hope for strong pretests. X3
•  » » 6 months ago, # ^ | ← Rev. 2 →   +5 I think the problem setter is happy when there are many hacks :v Strong pretests will make the number of hack decreases. :(
•  » » » 6 months ago, # ^ |   +7 he's also not gonna be happy when a lot of people are upset over the contest
•  » » » » 6 months ago, # ^ |   0 While many people are upset, many person also have extra points :)And the person, who are hacked, will have an experience never have same bug like that. :D
 » 6 months ago, # |   +19 Hope to see a great blend of classic problems involving (dp,algo,ds,numtheory etc..)in a single contest:D
 » 6 months ago, # |   +20 20 min to go !! :DBest of luck Ashishgup for your first contest as problemsetter. Looking forward to a really nice set of problems. :)
 » 6 months ago, # | ← Rev. 3 →   -11 strong pretest
 » 6 months ago, # |   0 CF so slow can't load other people submissions
 » 6 months ago, # | ← Rev. 2 →   +35 feel stupid enough to ask this type of questions again, yet I have no choiceHow to solve D? :(
•  » » 6 months ago, # ^ |   +2 Take sum of abs(a(i)) for all i as sum. Now ans=max(ans,sum-abs(a(i))-abs(a(i-1))+abs(a(i)-a(i-1))
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Same here. please help
•  » » 6 months ago, # ^ |   +14 if all negative abs(sum) — 2 * maxif all postive abs(sum) — 2 * minelse abs(sum)
•  » » » 6 months ago, # ^ |   0 Except that for all negative the answer should be abs(sum) + 2 * max — I hacked two solutions with this mistake.
•  » » » » 6 months ago, # ^ |   0 true i had the same mistake then resubmitted before 5 min of the end
•  » » » » » 6 months ago, # ^ |   0 What was the hack case for this ??
•  » » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 2-4 -5
•  » » » 6 months ago, # ^ |   0 I got stuck for some time because i forgot the base case when n = 1, then the answer is the no. itself.
•  » » 6 months ago, # ^ |   +4 Here's a hint: You can pick any subset and multiply it by -1 (except subset of size 0 and n)
•  » » 6 months ago, # ^ |   +13 For n > 1, you can show that you can choose the order of the eatings in such a way that the final number is  ± a1 ± a2... ± an for any combination of signs, in such a way that at least one of the  ±  is  +  and at least one of the  ±  is  - . Then, if you order a, the answer will be simply .
•  » » 6 months ago, # ^ | ← Rev. 2 →   +3 let sum store sum of abs(a[i])when all a[i] > 0, ans is sum — 2*min_elementwhen all a[i] < 0 ans is sum + 2*max_elementwhen there exists a[i] of each type ans is sum
•  » » 6 months ago, # ^ |   +1 You can show that if every number has the same sign, you can get the sum of their absolute values as a result except for one of them that you have to exclude. In this case you can choose to exclude the one with minimum absolute value and the result ends up being the sum of the absolute value of all the elements minus two times the one with the minimum absolute value (two times because you've already counted it in once).If there are positive and negative numbers it's similar, but this time you can avoid having to exclude anything, so the result ends up being the sum of the absolute values of all the elements.
•  » » 6 months ago, # ^ | ← Rev. 2 →   +12 Tried a linear-dp, only to realize by now it was pure mathematical observations. Got things now :
•  » » » 6 months ago, # ^ |   0 I also tried linear dp and got some 5 — 6 WA because of it.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 That's right. The solution made me realize that I misunderstood the problem. I thought I had to do a[i]-a[i+1] to combine the i and i+1 slime.
 » 6 months ago, # |   +39 Thanks for the n = 1 pretest in problem D! :D
 » 6 months ago, # |   +1 How to solve D please ?
•  » » 6 months ago, # ^ |   0 you just need to have some a[i]<=0 and a[j]>=0 then the answer is the abs sum of all numbers.
•  » » » 6 months ago, # ^ |   0 what ! T_T hmm , any proof ?
•  » » » » 6 months ago, # ^ |   +1 Make negative numbers from the positive numbers by subtracting the positives from the negatives, leaving exactly one positive number. Then use this positive number to make all the negative numbers of positive contribution by subtracting them from the positive number.
•  » » 6 months ago, # ^ | ← Rev. 2 →   +1 you just need to have some a[i]<=0 and a[j]>=0 then the answer is the abs sum of all numbers.UPD: Sorry for repeated comment, I am having the worst Internet connection now :(
 » 6 months ago, # |   +17 How to solve problem E? >_<
•  » » 6 months ago, # ^ | ← Rev. 2 →   +11 Hint: If we denote colours by nodes and blocks by edges, then all blocks of a connected component can be taken into final sequence if no. of nodes with odd count is 0 or 2 in that connected component.Let us count occurences of colours. Now, no. of colours having odd count can be 0,2 or 4 obviously. Now we can put two odd colours at the ends of the sequence. So, for odd=0 or odd=2, maximum of sum over all connected components can be considered(like for blocks(ignoring value)- (1-2),(2-3),(1-3),(4-4) connected components are- (1,2,3),(4)). Now for odd = 4 we will need to remove at least one of blocks. So, we can find answer by taking maximum of above thing over all 1-block removals which make odd=2. Sorry, if I am unclear.42588216
•  » » » 6 months ago, # ^ |   +5 Thanks you commented my question, so I need to delete some edges until no. of those nodes with odd count less or equal to 2?
•  » » » » 6 months ago, # ^ |   0 Yes, deleting one edge which is not self loop would be enough always.
•  » » » » » 6 months ago, # ^ |   0 But why no. of those nodes with odd count only 0.2 or 4, It can be constructed more right?
•  » » » » » » 6 months ago, # ^ |   0 There are 4 colours, each time we add a block(edge) parity of 2 of them changes. So, there can be only 0,2 or 4 with odd count.
•  » » » » » » » 6 months ago, # ^ |   0 Got it very appreciate, I misunderstood your meaning before >_<
•  » » » 6 months ago, # ^ |   +5 I agree with you.That's like my solution here.http://codeforces.com/blog/entry/61659?#comment-456568
•  » » » 6 months ago, # ^ |   0 Why do you need all 1-block removals. We can just remove the lowest value edge that has different colors on the two sides. Right?
•  » » 6 months ago, # ^ |   0 Alternative solution (harder to implement but was easier to come up with for me): While there are 3 or more edges between two colors, we can remove two most valuable edges and note that if any of these vertices is visited than we need to add the value of all corresponding removed edges. Now there are no more than 2 (edges per color-pair) * 6 (color-pairs) = 12 edges. The graph became small enough to bruteforce all possible edge-paths: After making 11 steps there will be only 1 edge left so we won't have a choice at that point. First 11 times there will be no more than 3 (number of other colors) edges to choose from. This gives an upper bound of 3^11 = 177147 node traversals. We will need to try starting at all four colors so the final number is 4 * 3^11 = 708588. In practise it works surprisingly fast: 31ms. If you for some reason would like to look at my solution: https://codeforces.com/contest/1038/submission/42595983
 » 6 months ago, # | ← Rev. 3 →   +23 Maybe it's first time in my life when it isn't nessacary to know anything (except sort()) to solve Div2 A, B, C, D... But... somehow they were very interesting!
 » 6 months ago, # |   0 what is pretest 16 problem D
•  » » 6 months ago, # ^ |   0 An array with size 1. Such as 1 5
 » 6 months ago, # |   0 What was the hack for D?
•  » » 6 months ago, # ^ |   +6 All numbers negative.
 » 6 months ago, # |   0 Any "Hint" for problem E ?
•  » » 6 months ago, # ^ |   +26 View the blocks as edges. Conditions for the edges: 1. all edges are connected together 2. the edges can form an euler path
 » 6 months ago, # |   +13 E was an interesting problem... but it took me a bit too long to implement. Is there a simpler solution than a dp with n*2^4*2^10 states?
•  » » 6 months ago, # ^ |   -7 Is it your second account — eygmath? Name and name of the school match.
•  » » » 6 months ago, # ^ |   +9 What are you talking about? I don't break any rules. I'm a good boi. Idk why our names are so similar though. I think that it is just a notorious coincidence.
•  » » » » 6 months ago, # ^ |   +21 I noticed that you've just changed the name but Google still remembers your old name — https://webcache.googleusercontent.com/search?q=cache:https://codeforces.com/profile/eggmath.
•  » » » » » 6 months ago, # ^ |   -25 Well, it's sad that such a great company like Google is so slow at updating. Maybe some competitive programmers here can write some faster algorithms for updating.
 » 6 months ago, # | ← Rev. 3 →   +35 Congrats for an amazing contest!
 » 6 months ago, # | ← Rev. 2 →   0 What is case 15 in problem D?
•  » » 6 months ago, # ^ |   0 n = 1
•  » » » 6 months ago, # ^ |   0 what is testcase 16
•  » » » » 6 months ago, # ^ |   0 same n = 1 but a[0] < 0
•  » » » » » 6 months ago, # ^ |   +3 shit
 » 6 months ago, # |   +2 Can E be done with max cost max flow?
 » 6 months ago, # |   0 How to solve B?
•  » » 6 months ago, # ^ |   +6 For n=1, n=2, output is "No". For n>2 Break into 2 sets, one containing odd numbers, other containing even numbers. Or Break into 2 sets, one containing 'n', other containing remaining numbers.
•  » » » 6 months ago, # ^ |   0 How about n = 5 and n = 6?
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +3 n=5 ==> {1,3,5} and {2,4} n=6 ==> {1,3,5} and {2,4,6}
•  » » » » » 6 months ago, # ^ |   0 ???
•  » » » » » » 6 months ago, # ^ |   0 You can test that with code like this: Test codeint main() { int n = 45001; int ev = 2, od = 1; for (int i = 3; i < n; i++) { if (i & 1) { od += i; } else { ev += i; } if (__gcd(ev, od) == 1) { return printf("NO"), 0; } } printf("YES"); return 0; } I did that during the contest to be sure that it will be AC.
•  » » » » » 6 months ago, # ^ |   +1 n=6 means Gcd=3I solved it with getting n*(n+1)/2 first devisor
•  » » » » » 6 months ago, # ^ | ← Rev. 3 →   +1 Still can's understand how 1 + 3 + 5 = 9 can be even. Maybe 'even' means something else in English?
•  » » » » » » 6 months ago, # ^ |   +1 My bad on saying the sum would be even. But it could be easily proved that partitioning odd and even numbers into 2 different sets, the sum of both sets will always have a common divisor k, where k=ceil(n/2). eg n=5,n=6 ==> k=3 is a divisor for both sets.
•  » » » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Oh, thank you! In fact, I didn't know that it can be easily proved considering pairs (k-i, k+i). I was using gcd() ans sum formulas...
•  » » » » 6 months ago, # ^ |   +3 The solution given by Mr_Maverick works because:Sum of first n numbers : n * (n+1) /2Sum of first n even numbers : n(n+1) ....(1)Sum of first n odd numbers : n^2 ....(2)Now gcd of (1) and (2) would be >= n ....That is why it is safe to partition like this..
•  » » » 6 months ago, # ^ |   0 But they said first n numbers, and for n = 2, the only possible numbers are 1 and 2. gcd(1,2) can never be greater than 1
•  » » » » 6 months ago, # ^ |   +3 Hence "No" for n=2
•  » » » » » 6 months ago, # ^ |   0 I see. I thought you were saying for n = 2 we can obtain a solution. I was taking the rest of your explanation as though you were talking for n>1
•  » » 6 months ago, # ^ |   +3 I think there are many solutions, mine was adding up all the odd numbers if they were an even amount (so the gdc would be two), or partitioning the elements into [1,N/2] and [N/2+1,N] otherwise.
•  » » » 6 months ago, # ^ |   0 Okay, but still, I don't understand why it works. Is there any proof this will work?
•  » » » » 6 months ago, # ^ | ← Rev. 3 →   +1 I did it this way for n>2, there can be two cases: 1. n is even: answer would be two subset having even and odd numbers respectively (as there would be even number of odd elements). 2. or n is odd: the answer would be one subset having middle element and other having remaining elements. This works as sum of digits equidistant from center would be equal to double of middle element (hence gcd=middle element).
•  » » » » » 6 months ago, # ^ |   0 Ohh, yes, nice solution :D
•  » » » » 6 months ago, # ^ |   +3 Let's n = 2d + 1.a = 1 + 2 + ... + d = d(d + 1)/2.b = (d + 1) + ... + n = (2d + 1)(2d + 2)/2 — a = (2d + 1)(d + 1) — a.gcd(a, b) = gcd(d(d + 1) / 2, (2d + 1)(d + 1)). If d is even then gcd(a, b) = d + 1. Otherwise, gcd(a, b) = (d + 1) / 2.
•  » » 6 months ago, # ^ |   +4 if n < 3, answer is no else, one set is n, the other set is 1, 2, 3, ..., n-1this is because the sum of the second set is (n-1)*(n)/2, so if n is odd, they have a common factor n, and if n is even, they have common factor n/2, and as n > 2, n/2 > 1
•  » » » 6 months ago, # ^ |   0 Nice solution. Given solution of sample test cases made me think in a different way :/
 » 6 months ago, # | ← Rev. 6 →   0 In problem C 100000 1000000 1000000 1000000 . . . 1 1 1 . . .Why this was a wrong/invalid hack? Link
•  » » 6 months ago, # ^ |   0 so the answer will be 50000 * 106 = overflow with int ... hmm it seems to be valid due to the input constraints !
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Hmm,I tried this as hack to get TLE/WA but they rejected it saying invalid hack input. I messaged @Ashishgup also, but he seems to be busy in wrapping up the contest.
•  » » 6 months ago, # ^ |   0 The hack log tells it all:Validator 'val_b.exe' returns exit code 3 [FAIL Expected EOLN (stdin, line 3)]Don't forget to put a new line character in the end of test.
•  » » » 6 months ago, # ^ |   0 Why does it expect newline character at the end of file? Yes, this was my first attempt to hack through the generator. In fact i specially handled cases to not print any additional space/endl.
•  » » » » 6 months ago, # ^ |   -8 I just realised that code which I was trying to hack got AC? Why we did not have this test case?
•  » » » » » 6 months ago, # ^ |   0 Can you give the link of solution please? Because the test you made for hack was alredy in pretest.
•  » » » » » » 6 months ago, # ^ |   0 https://codeforces.com/contest/1038/submission/42569122This solution prints sa-sb, and both sa and sb are declared as int. I did not see that int has been defined as long long on the top.
 » 6 months ago, # |   +54 Nice problems by Ashishgup.
 » 6 months ago, # |   +1 E is bitmask ,right?
 » 6 months ago, # |   +2 I need 35 to go back to DIV. 1, predictor says if all my solutions are accepted I will get +36 :D
 » 6 months ago, # |   0 Why God ??I did all things right but then shitted while typing in Div2-D. I calculated difference and max_difference correctly and then instead of using max_difference for calculation used difference instead :(Submission: https://codeforces.com/contest/1038/submission/42588288 JUST LAST MINUTE THINGS !!
•  » » 6 months ago, # ^ |   +13 Morale power, bro — such things will take time to be perfect. Better luck next time ;)At least you were so close to it. I myself couldn't come up with a proper idea during contest time.
 » 6 months ago, # |   0 Hi, I have a doubt regarding problem A. My code gives the required output on other IDEs as well as on my system. But on codeforces it is showing wrong verdict for pretest 1. Can anyone help me ? My solution link is : https://codeforces.com/contest/1038/submission/42582475
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 The ASCII code for 'A' is 65 not 64.EDIT: Ignore that, maybe it's because you didn't set the values in the a[ ] array to 0 ?
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 That '(int)ch-64' is just for hashing it doesn't affect anything just the indexing. Afterwards he has used indexing starting with 1 which is fine. His code looks fine.
 » 6 months ago, # |   0 Solved D, but was defeated by pretest 3 on A? What's going on there? Please, SEND HELP!
•  » » 6 months ago, # ^ |   +5 int ans = 30;Your initial value for ans should be at least equal to n (since that variable shows the minimum frequency of any letter, and such could rise up to n in certain circumstances).
•  » » » 6 months ago, # ^ |   0 Unless ans < n it's initial value does not affect anything within my code.
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +5 Take this case for example:n = 108, k = 3, s = "ABC" * 36 (i.e. the string s is the concatenation of 36 consecutive substrings "ABC").Obviously you'd find that the minimum frequency is 36 (all 3 letters have the same frequency).However, since you initialized ans = 30, the value will be kept at 30, and thus, the output will be 90 (while it should be 108).Keep in mind that n is at most 105.
•  » » » » » 6 months ago, # ^ |   +3 Oh, indeed.Thank you very much for pointing out!
 » 6 months ago, # |   0 how to solve E?
•  » » 6 months ago, # ^ | ← Rev. 3 →   +6 I know how to solve E in O(n^2). But it can be done with O(n) as well.If we have one component, we can take all edges, if we can make there Eulerian cycle or Eulerian path. And it is enough to delete one edge or none at all to get AC.Then pick one edge and then run dfs.
•  » » » 6 months ago, # ^ |   0 Why deleting one edge is enought?
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 When we have component of 3 or less vertices, we always can make Eulerian cycle or path.If we have 4 vertices, then parity of edges from vertices can be (odd, odd, even, even), (odd, odd, odd, odd), (even, even, even, even). First and second case have Eulerian cycle or path.When we have case with all odd parity, when we delete ane edge, we will get case (odd, odd, even, even) and this case have Eulerian cycle or path.
 » 6 months ago, # |   0 Is it just me or for the past 2 weeks during contests CF is taking too much time to load??? It's like...it's fine right now and 5 minutes later, it's not loading. And then it suddenly loads. Anyone?
•  » » 6 months ago, # ^ |   0 yesterday was fine this one was really bad
 » 6 months ago, # |   +17 Can someone share their library code for min cost max flow with negative edges and negative cycles which I believe is implemented using Bellman Ford irrespective of whether today's E has some other solution.Thanks!!
•  » » 6 months ago, # ^ |   -31 It can be done with simple dfs.
•  » » » 6 months ago, # ^ |   0 I did not ask for solution. I have mentioned irrespective reason just to avoid answers being put here instead of my original purpose :(
•  » » » » 6 months ago, # ^ |   +12 Oh, sorry
•  » » 6 months ago, # ^ |   -27 That's my solutionhttps://ideone.com/dZbEb2
•  » » » 6 months ago, # ^ |   +13 Seems pretty similar to 42583527. Did you forget to re-login?:)
•  » » » » 6 months ago, # ^ |   -17 You are right!
•  » » » » 6 months ago, # ^ |   -22 I am NSArray, and yes, you are right.
•  » » 6 months ago, # ^ |   +10
 » 6 months ago, # |   0 I used to solve D several minites after the time is over :)
 » 6 months ago, # |   +59 One of the best codeforces contests ever!!!
 » 6 months ago, # |   +3 Intuition for Question C?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +4 In terms of score difference it doesn't really matter to take your number or to erase your opponents' number. So you always want to deal with biggest number of both lists: if it yours you take it, if it opponent's you erase it from his list
•  » » 6 months ago, # ^ |   0 Its based on this optimal strategy from a player: If I don't have any element, I would delete the largest element from the list of the other player. Else If the other player doesn't have any elements, I would simply add the largest element in my list to my sum. Else if the largest element that I have has a greater value than the largest element of my opponent, I would add my element to my sum. Since if I go for deleting the largest element in my opponent's list, he would in turn delete mine and I will have to incur a greater loss. However, if I add my current largest element to my sum. Either my opponent will delete some no. in my list that has a lesser value or he will add to his own list an element that has a value <= the value of my element. In case my new difference would be >= my previous difference. Similarly, if other player has a larger element than the largest element I have, I would go for deleting the element in his list. All this can be simulated by using 2 vectors, 1 for each player and sorting both the vectors and accessing only the last elements of both at any instant.
 » 6 months ago, # |   +36 The strong pretests. I like it :)
 » 6 months ago, # |   +40 Thanks for the nice contest.
 » 6 months ago, # |   +69 Well balanced contest with interesting problem set. Clear and concise statements. Good job Ashishgup :)
 » 6 months ago, # | ← Rev. 2 →   +22 The pretests were great, but IMHO, the contest was a bit on non-algorithmic side. A bit disappointed with this.
•  » » 6 months ago, # ^ |   +7 Disappointing that you value the already invented algorithms over logical thinking!
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +5 if every problem is just logical thinking then you will actually not learn much.. applying multiple "already invented" algorithms or modifications of them is what problems should aim on in my opinion.. I appreciate ashishgup for the problems as it is not easy to come up with original problems but I hope next time he will amaze us even more.. all the best!!
•  » » » » 6 months ago, # ^ |   +26 To be fair, the tag-wise distribution of contests was: Logic Constructive Algorithm Greedy Logic/DP (both were applicable) Graph Theory/Bitmasks Strings/DP I prefer logical questions over coding-heavy questions, but I'll try to keep it in mind.
•  » » » » » 6 months ago, # ^ |   +19 Yeah. When I solved C, I pretty much thought of what lines you were trying to make the contest, so I was trying hard to find some DP solution for D, and it turned out to be simple logic based. @Ashishgup , anyway its good to see an Indian problem setter avoiding involvement of heavy DSA for E and F problems. Looking forward to solving some more great problems set by you :) Best of Luck for future contest! Its good to see that you took my comment in a positive spirit.@ushagal0000 A problem can also involve logical thinking with so "already invented" algorithms. Infact, if just knowing "already invented" algorithms could help solve all questions, then the majority of the world would be LGM. You always need a logical thinking even if the problem involves usage of "already invented" algorithm.
 » 6 months ago, # |   +24 Nice tasks + nice pretests = super contest. Thanks)
 » 6 months ago, # |   +30 I liked problem E. But I feel that problems B, C, D need some luck. You need to make a guess on what can be the solution then to verify it or maybe just submit it.
•  » » 6 months ago, # ^ |   +3 i spent some time try to proof that the B will always have a solution(for n>2 ), my roommate just submitted the solution immediately. both got AC :D
•  » » » 6 months ago, # ^ |   0 When I noticed my error in B was loop limit I fixed it and quickly submitted, but forgot to fix my prime range according to it and got runtime error. Being stingy about system resources not always good:P
•  » » 6 months ago, # ^ |   +1 I have actually verified my B. If you a take any divisor v of n(n+1)/2 such that 2 <= v <= sqrt(n(n+1)/2), you can create the two sets such that one of them contains this divisor and the other contains the rest of numbers. Because if v|a and v|b, therefore v|(a+b).
•  » » 6 months ago, # ^ |   +1 In B I have a nice proof:The sum of all values is n*(n+1)/2, you want to find a single element that divides the sum and is equal or smaller than n. This number can be (n+1)/2 rounded down clearly.It is possible to prove D too (even thogh I failed systest for mistaking a variable haha)
•  » » 6 months ago, # ^ |   +7 Superb contest. And I agree with this. Literally, when I was solving D. I found correct soln. Accounted for all corner case. And was just praying to get AC. At last, I got it. Although for B,C I made some proof. And then submitted. For all questions, I found correct soln. Then waited for 3-4 to 10-15 min. To verify it. And take care of corner test cases. Really enjoyed Solving Tasks. Thanks Ashishgup. Looking forward for the editorials.
 » 6 months ago, # |   +18 It seems that tests for E might be incomplete (or I misunderstood something); consider this testcase:61 10 11 2 22 10 32 20 33 1 44 10 4My solution, which passes tests, prints 52, but if I'm not wrong, the correct answer should be 43, like this:[1|10|1] [1|2|2] [2|20|3] [3|1|4] [4|10|4]Ashishgup, please take a look at this.
•  » » 6 months ago, # ^ |   +8 This testcase has been added to practice. Thank you!
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Just want to say that you adding this test to practice showed that my solution (that I just coded AFER the contest, so it does not matter much) is incorrect, thanks!And thanks antguz
•  » » » » 6 months ago, # ^ |   0 I actually noticed my first solution was wrong before submitting, but did it anyway, it was pretty surprising to see AC. Actually, a few submissions from the top of standings fail on that case too...
•  » » 6 months ago, # ^ |   0 Oh they become disconnected when removing the edge with the minimum value.
 » 6 months ago, # |   0 300iq _kun_ please delete my one of the exactly same codes submitted during the contest for problem C .
•  » » 6 months ago, # ^ |   +3 Ok, we will do it.
 » 6 months ago, # |   0 Strong pretests? Wow, it darn good
 » 6 months ago, # | ← Rev. 3 →   0 An Enjoyable Contest by an Indian Ashishgup. I am Happy to be back in track after many bad days
 » 6 months ago, # |   +13 rating changes !!
•  » » 6 months ago, # ^ |   0 i get +101Thanks for the great contest :)
 » 6 months ago, # |   0 Hi, Are long and long long not same in codeforces GNU G++17 7.3.0 compiler?
•  » » 6 months ago, # ^ |   0 long is 32 bits, long long is 64 bits.This is valid for G++11/14/17 also.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 #include #include int main(int, char **) { std::cout << std::numeric_limits< long >::max() << "\n" << std::numeric_limits< long long >::max() << "\n"; } Why are the max values of both same then?
•  » » » » 6 months ago, # ^ |   0 I ran this using custom invocation on GNU G++17 7.3.0 and didn't give the same value for both types.
•  » » » » » 6 months ago, # ^ |   0 Yes, that's my doubt. All other ide's at https://wandbox.org https://ide.geeksforgeeks.org https://www.codechef.com/ide and my macbook gave the ouput as 9223372036854775807 for both. I was unable to figure out the bug in 3rd question due to this. Why are they different here and not elsewhere?
•  » » 6 months ago, # ^ |   0 Long is the same as int in c++
•  » » 6 months ago, # ^ |   0 I believe that this depends heavily on the compiler. The standard for c++ guarantees that int has at least 16 bits (i.e. it goes from 215 to 215 - 1), long has at least 32 bits (from  - 231 to 231 - 1) and long long has at least 64 bits (from  - 263 to 263 - 1). Nevertheless, the individual compiler can assign more bits to a particular type.
 » 6 months ago, # |   +8 Thanks for the great contest)
 » 6 months ago, # |   0 Can anyone explain how to solve D with a proof? thanks in advance ....
•  » » 6 months ago, # ^ |   0 First of all, notice that the maximum value that you may get is sum(abs(a[i])) for 1<=i<=n. If the array consists of a combination of positive (>=0) and negative (<0) values, if you have v positive values, then v-1 of them can be subtracted from the negative values, and then subtract any negative value from the remaining positive value. By this, you get sum(abs(a[i]))If the array consists of only positive or only negative values, in this case, notice that if you subtracted any value from the other (v1-v2), min(abs(v1), abs(v2)) is better to be v1. For example, if the two values are (where all values are positive) 5,3; 5-3=2, but 3-5=-2. The difference here is that -2 can be used with the rest of positive values to get sum(abs(aa[i])) (assume aa is a after removing 3,5 and inserting -2). Also abs(v1) needs to be as minimum as possible, because in the subtraction process, abs(v1) is lost twice from sum(abs(a[i])) (in 3-5=-2, abs(3)+abs(5)-abs(2)=6=2*3). So the answer is sum(abs(a[i]))-2*min(abs(a[i])).
•  » » » 6 months ago, # ^ |   0 Thank you...
 » 6 months ago, # |   +8 Thank you for a very nice contest
 » 6 months ago, # | ← Rev. 2 →   +24 It seems that the test data for E is weak.Some contestants just sum up all weights in a connected component, then check whether there are four odd vertices, and if so, subtract the minimum weight of a non-loop edge. Such solution could survive System Test. However, this is incorrect, for the graph may be unconnected after that edge removed.Anyway, this is not a very common situation in Codeforces! lol
•  » » 6 months ago, # ^ |   +36 I am sorry for the weak test data. We tried to add cases of every type and also some manual cases, but failed to break a few incorrect submissions (due to different heuristics being used by different participants). One case was added after system test, and if you think that incorrect solutions still get AC and you have any breaking case/code link, do tell. We will add the case to practice for further submissions. (We cannot rejudge the contest codes)
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +26 I agree that it is rather difficult to generate strong and complete test data. Anyway, thanks for your hard work.
 » 6 months ago, # |   0 There are many ways to solve Problem B, for example: if n>2 set 1: (n+1)/2； set 2: others;because (int)((n+1)/2) can divide (1+n)*n/2.
 » 6 months ago, # | ← Rev. 2 →   +5 Can someone check the code for me?http://codeforces.com/contest/1038/submission/42591350Getting an error in Problem C in test case 58
•  » » 6 months ago, # ^ |   0 you should add ' and i
•  » » » 6 months ago, # ^ |   +5 My solution got accepted by making the changes you recommended.But, how does it make a difference? I didn't understand.
•  » » » » 6 months ago, # ^ |   0 i can't quite tell but your array can exceed the size limit and may have strange results
•  » » » » » 6 months ago, # ^ |   +5 If the array size limit exceeds, the strange results won't match the mx variable
•  » » » » » » 6 months ago, # ^ |   +8 there are coincidences in the world
 » 6 months ago, # |   0 how to solve div2a please? i solved only div2d because of too tricky problems not fair!!
 » 6 months ago, # | ← Rev. 2 →   +16 I noticed that winner (SBHeltion) has cheated, you can totally understand that these two code written by two different people :In A B C D he used spaces in for and +=1 instead of ++ but in problem E he used ++ and without spaces.And if you look defines A-B-C-D have , but E-F have not... suddenly he use N define instead of maxn