### Vovuh's blog

By Vovuh, history, 4 months ago, ,

1183A - Nearest Interesting Number

Idea: MikeMirzayanov

Tutorial
Solution

1183B - Equalize Prices

Idea: MikeMirzayanov

Tutorial
Solution

1183C - Computer Game

Idea: MikeMirzayanov and Vovuh and BledDest

Tutorial
Solution

1183D - Candy Box (easy version)

Idea: MikeMirzayanov

Tutorial
Solution

1183E - Subsequences (easy version)

Idea: MikeMirzayanov

Tutorial
Solution

1183F - Topforces Strikes Back

Idea: Vovuh

Tutorial
Solution

1183G - Candy Box (hard version)

Idea: MikeMirzayanov

Tutorial
Solution

1183H - Subsequences (hard version)

Idea: MikeMirzayanov

Tutorial
Solution

• +64

 » 4 months ago, # | ← Rev. 2 →   +9 Can somebody explain how we solve B with Binary Search?
•  » » 4 months ago, # ^ |   0 Here it is bro- https://codeforces.com/contest/1183/submission/56148789
•  » » » 4 months ago, # ^ |   0 i don't understand the idea bs, could you explain
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 See our search space is (maxElement-k to maxElement+k). Our answer lies between this interval. Now we binary search using the condition (minElement-mid)<=k) If our minElement satisfies this condition then all elements will surely do so we check for only minElement. and then we take max of all possible values.
•  » » » » » 4 months ago, # ^ |   0 Thanks
•  » » 4 months ago, # ^ |   0 Set low = min(A) + k and high = max(A) + k, and use binary search to find out the result in this range.
 » 4 months ago, # |   0 For problem B, initially I wrote binary search solution for answer. But, it seems it is giving $-1$ for some valid case too.Can someone please help me identify the mistake in my submission ?
•  » » 4 months ago, # ^ |   0 I wrote almost the same solution but I got WA on test 3 :(https://codeforces.com/contest/1183/submission/56084413
•  » » 4 months ago, # ^ |   0 Ok, I get it. Even if for a certain value, we cannot satisfy the conditions, It does not mean that the answer should be less than the value, the answer can be more than the current value too.For eg, Your array is 2 2 5 10 and let K be 4, the lower bound is 0 and the upper bound cannot be greater than (min+K). So you first check for (0+6)/2 = 3 (as mid). You see that condition is not satisfied as (10-3)>4, so you conclude that answer should be less than 3, which is not true, since the value 6 satisfies all the condtions. So, I think that Binary Searching the Answer cannot work for this problem.
•  » » » 4 months ago, # ^ | ← Rev. 3 →   +3 I have done with binary search only. You just need to look what to do if OK==false in the solution. https://codeforces.com/contest/1183/submission/56092348
•  » » » » 4 months ago, # ^ |   0 Link is not working :(
•  » » » » » 4 months ago, # ^ |   0 Now check it.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 you should initialize lo to the least valid value, but you're initializing it wrong. you should rather initialize to : max(a[n — 1] — k, 1) but only after checking if that value is indeed a valid candidate for an answer. (which is easy you can iterate through the array and check that) my solution
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 you should initialize lo to the least valid value, but you're initializing it wrong (0 isn't a valid answer). you should rather initialize to : max(a[n — 1] — k, 1) but only after checking if that value is indeed a valid candidate for an answer. (which is easy you can iterate through the array and check that) my solution
 » 4 months ago, # |   0 1183C - Компьютерная игра Can somebody explain why we need to do (-c+1)/(a-b) instead of (-c)/(a-b)? Thanks
•  » » 4 months ago, # ^ |   +4 Because you have to add some differences to obtain the charge at least $1$. See the following example: $-c$ = 4, $diff = 2$. Then your formula will say $2$ and after two additions we will obtain $c=0$ and this is bad for us.
•  » » » 4 months ago, # ^ |   0 Thnaks a lot, I did not consider that
 » 4 months ago, # |   +14 Vovuh's contests : Always fast and high quality
 » 4 months ago, # |   0 In problem H, I wonder if we don't get min of 10^12, what will happen then ?
•  » » 4 months ago, # ^ |   +4 Theoretically, the number of subsequences of the string of length $n$ is $2^n$. This value is the upper bound but there can be strings that contain more than $2^{63}-1$ subsequences and if you not take the minimum with $10^{12}$ then your dynamic programming will overflow the 64-bit datatype. I takes $10^{12}$ because you never need more subsequences than $10^{12}$.
•  » » » 4 months ago, # ^ |   0 Thanks
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 what is the time complexity of solution of problem E ?
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 $O(n^2k)$ since it's a BFS that visits $k$ vertices, and processing each vertex takes $O(n^2)$ time (generating/checking $n$ strings, taking $O(n)$ time each).(Edited to fix runtime, thanks Roach00.)
•  » » » » » 4 months ago, # ^ |   +4 but what about unnecesary generated subsequences apart from visiting k vertices and O(n) in deleting character from string for each vertex string
•  » » » » » » 4 months ago, # ^ |   0 You're right, it's $O(n^2 k)$ in the worst case where there are lots of duplicates and we only get one new string of each length.
•  » » » » » » » 4 months ago, # ^ |   0 we could reduce the time complexity of search,insertion and deletion to log(n),if we use suitable data structure.but that could be hell of implementation.
•  » » » » » 4 months ago, # ^ |   0 wc, Thanks to you too :)
•  » » » 4 months ago, # ^ |   +1 Can anyone explain how to come up with the upper_bound(1e12) for any given string?
•  » » » » 7 weeks ago, # ^ |   0 it's in the problem. ~~~~ 1<= k <= 10e12 ~~~~
 » 4 months ago, # |   +5 It's great to see these problems which have two versions! It helps me have a deeper understanding of the problem~
 » 4 months ago, # |   +1 what is the mistake in my idea in problem D my code here
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 Hey just check out this case:No. of type 1 candy = 5No. of type 2 candy = 5No. of type 3 candy = 5No. of type 4 candy = 5No. of type 5 candy = 4ans after soring would be 5,5,5,5,4. and just before you would be adding the last type of candy. State of map s would be : 5:4 4:1 3:1 2:1& now you should increment at 1 but instead, you increment at (4-2+1) i.e 3.A better approach would be to store the last number of candies added and then decide what to do in the next loop. If stuck you may check out: https://codeforces.com/contest/1183/submission/56115382
•  » » 4 months ago, # ^ |   0 Have a look at this, i have tried to write it in the most simplest manner I could think of :: https://codeforces.com/contest/1183/submission/56165836
•  » » » 4 months ago, # ^ |   0 thank you all
 » 4 months ago, # |   0 tnx for fast tutorial and good explanation but lots of questions was mikemirzayanov's
 » 4 months ago, # |   +5 Really liked the trick you applied to F . Nice contest and especially problem F.
 » 4 months ago, # | ← Rev. 2 →   0 Hello, Could you help me with H (hard version)? It says wrong answer on test 43. I have no idea what is wrong with it. Thanks in advance. http://codeforces.com/contest/1183/submission/56165101Edit: Anyways, I solved it after long hours of hard work.
 » 4 months ago, # |   +8 I solved H with slightly different approach where dp[i][j]=#of subsequences of length j on prefix [1..i]. Let character on position i be A, then the transition looks like: dp[i][j]=dp[i-1][j]+dp[i-1][j-1]-dp[last[A]-1][j-1]. It is correct, however it may overflow sometimes. What I did was first adding dp[i][j]+=dp[i-1][j], and if now dp[i][j]>1e18 i skip the second part of addition. It passed the tests, but im almost sure that this is not correct. If we substract this value of dp somewhere later it is not preceise, so later dp states may be not exactly correct. So here come my questions: 1. Am i right that it is not correct? 2. Is this really hard to construct counter-test?
 » 4 months ago, # |   0 In problem C, why should we round up (-c+1/(a-b))? Why can't we use the value directly?
 » 4 months ago, # | ← Rev. 2 →   +2 Can someone pls explain to me the solution of Problem H
 » 4 months ago, # |   0 Can anyone explains the 3. Computer tutorial formula for turns i.e. turns = ceil(-c+1/(diff)). How this formula is derived?
•  » » 4 months ago, # ^ |   0 Alright. Let the number of just play turns be $x$, and let the number of play and charge turns be $y$.The problem statement suggests that total number of turns should be $n$, hence $x+y=n$.It also suggests that the battery that these moves consume altogether should be strictly less than the initial charge. Just play moves consume $a*x$ amount of battery, whereas play and charge moves consume $b*y$ amount of battery, hence $a*x+b*y •  » » » 4 months ago, # ^ | 0 Thanks for your explaination. I got expression as y<(-c)/(a-b) as per your explaination above. But in code why are we taking ceil operation and adding 1 int he numerator. How its giving the correct answer •  » » » » 4 months ago, # ^ | 0 This comment explains it better.  » 4 months ago, # | 0 Can someone please explain why my submission won't work for Candy hard where submission id is https://codeforces.com/contest/1183/submission/56124846?  » 4 months ago, # | +3 Can someone please explain the validity of the solution given here for F? •  » » 3 months ago, # ^ | 0 My solution to F is: Sort the array (arr). Remove duplicate elements. Iterate for all i find maximum index j < i such that arr[i]%arr[j]!=0 and then find maximum index k < j such that arr[j]%arr[k]!=0 && arr[i]%arr[k]!=0, maximize the answer by arr[i]+arr[j]+arr[k].Let prove this solution by contradiction: Suppose, for index i there are indexs j0, k0 (k < j0 < k0 < i) can be selected such that arr[j0]+arr[k0] > arr[j]+arr[k] and i, j0, k0 satisfies all the conditions, if this is possible then our soluton is wrong. But if we look carefully this is not possible. j0 was not selected as k so we are sure arr[j]%arr[j0] = 0, same k0 was not selected as k because arr[j]%arr[k0] == 0, So arr[j0] and arr[k0] are divisors of arr[j] and obviously smaller than arr[j]. And we know than some smaller divisor of a number n is <= n/2 so arr[j0] + arr[k0] <= arr[j]. So above condition arr[j0]+arr[k0] > arr[j]+arr[k] is not possible.  » 4 months ago, # | 0 someone explain where my solution fails for Problem C? MY Solution •  » » 4 months ago, # ^ | 0 You are using ints, rather than longs. This overflows when you multiply n and b. I replaced your declarations of variables k, n, a, b with longs and it passes the first case you failed. •  » » » 4 months ago, # ^ | 0 thanks,I got it and I should check K  » 4 months ago, # | +4 How to solve F by iterating over all possible triplets? •  » » 4 months ago, # ^ | 0 Hey, you can just check out my submission: https://codeforces.com/contest/1183/submission/56166652All you have to do is break out of the loop whenever appropriate.  » 4 months ago, # | 0 Can anyone help me with the problem C why are we adding diff to k (k + diff — 1) / diff •  » » 4 months ago, # ^ | 0 ceil(a/b) = (a+b-1)/b •  » » 4 months ago, # ^ | 0 For C just use the binary search approach simple and efficient. •  » » » 4 months ago, # ^ | 0 I looked at your submission. Really clever implementation. •  » » » » 4 months ago, # ^ | 0 Thanks:)  » 4 months ago, # | 0 can someone explain the 2nd testcase of problem D i didnt quite understand how they took the maximum possible size thanks.  » 4 months ago, # | 0 Vovuh Content copied from my previous comment..(no one replied). {May be I am wrong}... I tried D using max-heap but at the 19th case the response was TLE .. but as you guys have used sort() method [complexity will be nlogn]. So, as Mine...https://codeforces.com/contest/1183/submission/56128383any suggestion where am I wrong??? •  » » 4 months ago, # ^ | 0 .. whether max heap is a good way to solve it .. pseudocode: heap=maxheap(contains the frequency of distinct nos) start=maxheap[0] //max value while(heap not empty): val=heap(remove max value from heap) if((val-start)>=0): if(start>=0): count=count+start start=start-1 else: break else: if(start>=0): start=min(val,start) count=count+start start=start-1 else: break So, for me its O(nlogn) ... n for removing the elements and log(n) for maintaining the heap...??? am I correct?? ...   » 4 months ago, # | +5 For 1183F - Возвращение Topforces, I tried all of the possible options for 30 biggest unique elements and failed in system testing (56093272). After the contest, I changed 30 to 40 and got accepted (56189352). Can anybody come with a counter test for my solution? The main idea is if$x \neq y \land x | y \rightarrow x \times 2 \leq y$. •  » » 4 months ago, # ^ | ← Rev. 3 → +8 This solution will fail at the test case where a lot of divisors of maximum should be omitted in greedy solution. So we can take a number$x$with maximum number of divisors, omit one from$\{x/2, x/3, x/5\}$and add two minimum numbers that are not divisors of$x$. This gives us a test with$n = 149$, where the least number is used in optimal answer. Test1 149 13 17 14 15 16 18 20 21 22 24 27 28 30 33 35 36 40 42 44 45 48 54 55 56 60 63 66 70 72 77 80 84 88 90 99 105 108 110 112 120 126 132 135 140 144 154 165 168 176 180 189 198 210 216 220 231 240 252 264 270 280 297 308 315 330 336 360 378 385 396 420 432 440 462 495 504 528 540 560 594 616 630 660 693 720 756 770 792 840 880 924 945 990 1008 1080 1155 1188 1232 1260 1320 1386 1485 1512 1540 1584 1680 1848 1890 1980 2079 2160 2310 2376 2520 2640 2772 2970 3024 3080 3465 3696 3780 3960 4158 4620 4752 5040 5544 5940 6160 6930 7560 7920 8316 9240 10395 11088 11880 13860 15120 16632 18480 20790 23760 27720 41580 55440 83160 166320  Generatorb = 166320 d = [13, 17] + [x for x in range(13, b+1) if b % x == 0 and b // 5 != x] print(1, len(d), ' '.join(str(x) for x in d), sep='\n') Probably this or something similar should be added to this problem testset, Vovuh •  » » » 4 months ago, # ^ | +5 Thank you, I will add this test now!  » 4 months ago, # | 0 Can someone explain me the Problem D ? •  » » 4 months ago, # ^ | 0 In this problem, you are provided with total different types of candies (n)and then the type of a particular candy in a seriesfor eg- 8 1 4 8 4 5 6 3 88 is the total number of different types of candiesand the sequence in which they are present isfirstly a candy of type 1 then a candy of type 4 then a candy of type 8 again a candy of type 4total number of candy of type 1 is = 1 total number of candy of type 2 is = 0 total number of candy of type 3 is = 1 total number of candy of type 1 is = 1 total number of candy of type 4 is = 2 total number of candy of type 5 is = 1 and soonYou have to find out the gift •  » » 4 months ago, # ^ | 0 Have a look at this, https://codeforces.com/contest/1183/submission/56165836 In this we try to first see the frequencies of all candies, and sort then in descending order. We all candies with highest frequency(say f for now) to our gift and the next optimal step would be to add f-1 candies of the next candy type(if available, else add all candies if its freq is less than f-1). We always try to add the number next candy type, based on how many candies of the previous type we added. Optimally we always try to add (prev_added_candies — 1) candies if available, int current step.  » 4 months ago, # | +3 can anyone please explain tutorial for H. I don't understand how does it work. •  » » 4 months ago, # ^ | ← Rev. 3 → 0 I too am unable to understand the very first few lines."Initially all values are zeros except$dp_{i,1}=1$for each$i$from$0$to$n−1$."Why is this the case? Won't it count two different occurrences of the same character as two instead of one ( we need distinct subsequences right? )UPD: (Adding example)If the given string is "abca", then$dp[0][0]=1$and$dp[3][0]=1$, but I thought we must count it as 1 times "a" is there not twice. How is that being taken care of? •  » » » 4 months ago, # ^ | ← Rev. 2 → +3 You will not consider the first 'a' when you'll calculate the number of subsequences of length one. The same with other lengths, two dynamic programming states$dp_{i_1, j}$and$dp_{i_2, j}$can be non-zero and$s_{i_1} = s_{i_2}$but you will not consider the first state in the answer. •  » » » » 4 months ago, # ^ | ← Rev. 2 → 0 Oh okay. So correct me if I am wrong, we are making dp such that each subsequence$t$that ends with say some character$X$, will be counted at the maximum position$i$such that$i \ge len(t)$and$s[i]$is$X$. ($s$is original string ). •  » » » » » 4 months ago, # ^ | +3 Yes, this is true. •  » » » » » » 4 months ago, # ^ | +5 Thanks a lot! Finally understood and implemented. •  » » » » » » » 4 months ago, # ^ | 0 Hey, can u please explain the solution in a detailed manner, I am not able to understand why are we doing the steps mentioned. Thanks in advance! •  » » » » » » » » 4 months ago, # ^ | 0 Maybe you should try to explain what exactly you did not understand, instead of asking someone to tell you the whole thing, especially when there is editorial where someone has tried to do what you exactly want.Now, I will try to explain a simple example to you, to make sense of the dp ( not go through the whole process ). Maybe that will clear everything.Consider given string$s = aba$. I will just tell you how to understand the$dp$.Firstly, let's note ourselves, what are the subsequences. We have {$aba,ba,aa,ab,a,b$}Out of these,$a$is counted at index$0$and$2$,$b$is counted at index$1$,$ab$is counted at index$1$,$aa$is counted at index$2$,$ba$is counted at index$2$,$aba$is counted at index$2$. Since$a$is counted twice, I was confused, but finally while calculating total counts, we are only considering$last[n-1][ch]$for each character$ch$= [$a$to$z$], thus in case of$a$only the one at index$2$is counted at the end. The one at index$0$, however, is also important, because only using it you can count the strings$aba$or$aa$. •  » » » » » » » » » 4 months ago, # ^ | 0 Thanks Samarth! » 4 months ago, # | 0 # Problem B : Equalize Prices i have just checked if (min+k >= max-k) then print min+k ; else print -1; still wrong answer on test case 3.Can somebody please explain. •  » » 4 months ago, # ^ | 0 •  » » » 4 months ago, # ^ | 0 What if$n=1$? You forgot to set the maximum value in your if statement (in if (i == 0)). •  » » » 4 months ago, # ^ | 0 think of it as an intersection problem that's how i solved it find the intersection segment l,r for all the given elements and print r if for some element there's no intersection with previous element output -1 https://codeforces.com/contest/1183/submission/56232830  » 4 months ago, # | ← Rev. 2 → 0 thanks for all your help ....., now deleting this comment •  » » 4 months ago, # ^ | 0 teshar roy on youtue for videos hacker earth for graphs and math and all the basics expect for dynamic programming learn it from geeks for geeks any one who did it did it alone so cheer up and go solve a lot of problems and participate in lots of contests that'a the most important thing hope to do well enjoy .  » 4 months ago, # | ← Rev. 2 → 0 Simple solution for H:Let$dp[n][k]$be the number of distinct subsequences of length$k$using only the first$n$characters of$s$. Then dp[n][k] = dp[n-1][k] + dp[n-1][k-1] - dp[l-1][k-1] where$l = lst_{n-1,s[n]}$.Now greedily add substrings to$S$. Note that two subsequences of different length must be different. (We first use the$dp[n][n]$subsequences, then$dp[n][n-1]$, etc)  » 4 months ago, # | 0 Can someone explain the Dynamic Programming approach for Problem E — Subsequences (easy version).  » 4 months ago, # | ← Rev. 4 → 0 I solved problem D with O(N) solution. I like when you guys hide the solution of the problems in the way you did in this tutorial. So when i go to read the solution of the problem A i don't end up reading the solution of problem B and a lot of times i don't want to do it.  » 4 months ago, # | 0 56141485 Can someone please tell what am I doing wrong. When I run the code on my system with the test case : 1 10 100 100 100 100 100 100 100 100 100 100I get the answer as 10, but on running in custom invocation answer comes out as 27.  » 4 months ago, # | 0 Vovuh Why do n/2, n/3, n/5 never divide each other completely? Can this be proved? Thanks :) •  » » 4 months ago, # ^ | 0 cause n / 2 has more 3 factors than n / 2 and n / 3 has more 2 factors than n / 2. :)  » 4 months ago, # | 0 In problem F editorial Let's imagine that the maximum element is divisible by 2, 3 and 5 and there are three following numbers in the array: maximum divided by 2, by 3 and by 5. Then their sum is greater than the maximum (and may be greater than the answer we have!) because 12+13+15>1. can someone give an example of such case... Thanks in advance •  » » 4 months ago, # ^ | 0 Consider one of test cases in problem sample: 4 30 15 10 6 Obviously,$n < n/2 + n/3 + n/5$is$30 < 15 + 10 + 6\$ here
 » 4 months ago, # |   0 Can anybody explain the complexity for Problem F (brute force) solution ,it would be really helpful?
 » 4 months ago, # |   +8 For problem F,https://codeforces.com/contest/1183/submission/56308081My submission is just a N^2 complexity solution, why can I get it passed?
 » 4 months ago, # |   0 For Problem D, Candy Box(easy version) can someone help me identify the error in my code?https://codeforces.com/contest/1183/submission/56358474Thank you!
»
4 months ago, # |
0

1183(c) Can anyone tell me why its not working??

# include<stdio.h>

int main() { long n,k,a,b,q,c,turns,diff; scanf("%ld",&q); while(q--) { scanf("%ld%ld%ld%ld",&k,&n,&a,&b); c=k-(a*n); diff=a-b; if(c>0) printf("%ld\n",n); else { turns=(-c+1)/diff; if(turns>n) printf("-1\n"); else printf("%ld\n",n-turns); } } }

 » 4 months ago, # |   0 pls explain why in C 16 7 5 2 is giving ans=0 nd 15 5 4 3 is giving ans=-1 also 20 5 7 3 is giving 1 instead of 2??pls reply 
 » 3 months ago, # |   0 In the problem C, i am not able to get where in the problem statement its written that when vola plays the turn "play and charge", the charge of the battery increases by diff=a-b. It's written in the editorial as well. Kindly help me with the problem statement of the problem. Thanks in advance
 » 3 months ago, # | ← Rev. 2 →   0 Could anyone tell me why am I getting a wrong answer with problem D on the 3rd test?https://codeforces.com/contest/1183/submission/56678366
 » 3 months ago, # |   0 Could anybody explain me please, why I have TLE on test 3 in problem F ? https://codeforces.com/contest/1183/submission/56682439 I have no ideas :( I use C#.
 » 3 months ago, # |   0 For all those who can't understand solution for H can try this problem first https://www.spoj.com/problems/DSUBSEQ/
 » 3 months ago, # |   0 What is the time complexity for solution of E?? .... they used set count which is O(n) (even more with strings)...but using map is slower than this !!
 » 3 months ago, # |   0 Can someone explain why Problem H solution works ? I don't understand why we are constructing these matrices and what is the logic to using them.
 » 7 weeks ago, # |   0 For Question A. Max step should be 7. Number = 997 steps taken will be 7 But the editorial says it's 5.
 » 7 weeks ago, # |   0 Thanks for these Good Editorial !