By SirShokoladina, history, 23 months ago, ,

• +62

 » 23 months ago, # |   0 I asked someone to explain my div1B solution to me in this commentAnd you actually did that, thanks :D.
 » 23 months ago, # |   +6 SirShokoladina please fix div2E. There is parsing error.
 » 23 months ago, # |   +17 A lot of things to learn...
 » 23 months ago, # |   +3 C shows up as "unable to parse markup" for me.
•  » » 23 months ago, # ^ |   +12 thanks for noticing! it should work now
 » 23 months ago, # |   +5 Can you please provide code to the solutions, especially Div 2D/1B... really hard to understand the solution for me. Thanks a lotAlso, Div 2E/1C problem is missing it's solution
•  » » 23 months ago, # ^ | ← Rev. 3 →   +6 Here is my code for second solution for div1B:https://pastebin.com/FpfJXVH0Here is the first solution for div1C:https://pastebin.com/2KemU4bNHere is div1E, but here z = 0 means that there were people on stations and z = 1 means there were no people.https://pastebin.com/5ZdKuRkM
 » 23 months ago, # | ← Rev. 2 →   +3 I don't understand div2 C part where it says that answer can be no more than n-x. Can somebody explain me little bit better?
•  » » 23 months ago, # ^ |   0 I think there is some inaccuracy. Consider cycle and every element in it: break it on intervals between elements equal to concerned element (include first boundary, exclude second). When element is single there is one such interval. Obviously that on every interval there is exists at least one bad replacement. So in every cycle at least k bad replacements, where k is max number equal elements in cycle. So if there is x equal elements in array then in every partition on cycles there is at least x bad replacements.
•  » » » 23 months ago, # ^ |   0 how is it obvious that there is one bad replacement on each interval, why cant all elements be good replacements for some particular interval of some cycle ?
•  » » » » 23 months ago, # ^ |   0 Because we start and end on same value. Try to move ahead with this thought.
•  » » » » » 23 months ago, # ^ |   0 Okay, that's pretty clear now, thanks !!
 » 23 months ago, # |   +41 Great Contest! With mind blowing problems. SirShokoladina Sir, you should conduct contests more often.
 » 23 months ago, # |   0 LOL I did some kind of precalc on div1B. 40296044. My solution has complexity . But I can't implement it without map which contains vectors so it is very slow. Then i noticed that it can be precalculated and instead of 43 * log with bad constant it gives clear 43.
 » 23 months ago, # |   0 I think for the second solution to C, you mean to say that X and Y are the minimal possible values satisfying that condition (but the solution works).
•  » » 23 months ago, # ^ |   0 Yes, fixed it.
 » 23 months ago, # |   +2 Overall, I thought the logistics of the contest could have been managed better. Some of the problem statements could have been worded better, there were a lot of clarification announcements, etc.That being said, I thought the problem quality was good, especially Div 1 C. If Div 1 BC were shifted down 1 problem (can't speak towards D or E), and another Div 1 B made, I think the problem scaling would have been perfect.
 » 23 months ago, # | ← Rev. 2 →   +15 Can't understand the second solution for Div1.B. The solution says:"In such way every satisfying this criteria parallelepiped (not considering the orientation) with three different side lengths was counted 6 times."Let's consider the large parallelepiped to be 4x6x10, the small parallelepiped 2x3x5 will only be counted once. Why the solution says that it is counted 6 times?(Actually, can't understand the first solution either... What does "mask" mean in the solution?)
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 we count it 6 times — as 2x3x5, as 2x5x3, as 3x2x5, as 3x5x2, as 5x2x3 and as 5x3x2mask of length 3 in a subset of set {1, 2, 3} written as a 3-digit binary number. so 0 = 000 = {}, 1 = 001 = {1}, 2 = 010 = {2}, 3 = 011 = {1, 2}, 4 = 100 = {3}, 5 = 101 = {1, 3}, 6 = 110 = {2, 3}, 7 = 111 = {1, 2, 3},
•  » » » 23 months ago, # ^ | ← Rev. 2 →   +1 But the direction of the large parallelepiped is fixed, and 3 is not a divisor of 4, so why is 3x2x5 counted?
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   0 Because we use the IEP on rotations (permutations), so both 2x3x5 and 2x5x3 are rotated in all directions and if at least one orientation satisfies then it is counted once, otherwise it is not counted.
 » 23 months ago, # |   0 so my understanding of div2D was correct but problem statement and number of submissions prevented me,huh,sad
 » 23 months ago, # |   0 can anyone help fix my mistake for div2 B?Submission Link
•  » » 23 months ago, # ^ |   0 x > curh and y <= curh it will not update curh, in fact, curh = y.
•  » » » 23 months ago, # ^ |   0 got it, thank you
»
23 months ago, # |
-21

# ?detaR tI sI

 » 23 months ago, # |   +21 Why did my code of div1C which used "exit(0);" get "Idleness Limit Exceeded" in pretest 12?
•  » » 23 months ago, # ^ | ← Rev. 2 →   +94 you noob
•  » » » 22 months ago, # ^ |   -8 kappa
•  » » 23 months ago, # ^ | ← Rev. 3 →   0 Nice doubt, don't forget to tell once you get the reason.
•  » » 23 months ago, # ^ |   +8 maybe you use "exit(0)" before you actually guess the correct numbers?
•  » » 23 months ago, # ^ |   +16 Oh I found a precision error in my code. But when I changed "exit" into "return" it got accepted.
•  » » » 23 months ago, # ^ |   0 can you show me your code?
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   +8 exit：http://codeforces.com/contest/1007/submission/40288030return：http://codeforces.com/contest/1007/submission/40303376
•  » » » » » 23 months ago, # ^ |   0 seems like the codes are really equivalent... I don't know, maybe you have ub.
 » 23 months ago, # |   0 Can Someone Please tell me a more intuitive way to understand the solution of div2 C (div1 A) or different easier approach if possible???
•  » » 23 months ago, # ^ |   +1 The problem can be done by using two pointers. Lets sort the given array and initialize count and both pointer to 0. say pointers be i and j. starting from index 0, take next biggest element(by changing j) and when you find that, increase i, j and count. Here we are calculating the possible number of pairs in which smaller can be replaced by bigger number. Here is snipped for what I did: sort(a,a+n); ll cnt = 0; ll p1=0,p2=0; while(p1
•  » » » 23 months ago, # ^ |   0 got your point, Thanks for explaining. :)
 » 23 months ago, # |   +3 Can someone please elaborate on the Div1B Second solution? (The Inclusion exclusion one) ...?!It is not very clear to me how the "ans2" part is calculated by the author's solution...If you had a different combinatorial solution please share that as well ..
•  » » 23 months ago, # ^ |   +8 ans2 supposes that the first two lengths of the parallelepiped coincide. That means that this length should divide two chosen dimensions of the big parallelepiped. thus we use g[x[0] | x[1]]
•  » » 23 months ago, # ^ | ← Rev. 2 →   +5 Look at my other comment lower, maybe it will help.
•  » » » 23 months ago, # ^ |   0 thankyou , the whole approach is still exotic to me as I have never seen something like this before, but get your solution..
 » 23 months ago, # |   0 It seems that SirShokoladina forgot to link the editorial to the problems in Div2 (contest 1008). In any of the five problems we can't see the link of editorial.
•  » » 23 months ago, # ^ |   0 I don't know how to link them. I guess Codeforces this automatically.
•  » » » 23 months ago, # ^ |   0 I'm sorry... I don't know that before.
•  » » » 23 months ago, # ^ |   0 You can do that by clicking clip image at the top of the blog
 » 23 months ago, # | ← Rev. 3 →   +14 Can anyone explain div2d in understandable way?
•  » » 23 months ago, # ^ |   +5 I can elaborate on the second solution. First, google what inclusion-exclusion principle is. I'll explain its meaning. Assume you have a bunch of sets and want to know the size of their union. If for every set of this sets (for example "1st 2nd and 4th set" or "3rd and 5th set") you know the size of their intersection then you can count the size of their union.We have six orientations. Each of them gives us a set of parallelepipeds that we can pave the big one with. One of such sets is "1st side divides the 2nd side of the big, 2nd side divides the 1st side of the big and 3rd side divides the 3rd" side of the big", let's mark it 213. Now how can we find the size of intersection of several such sets? If we had two permutations 132 and 231 then a parallelepiped is inside the intersection of their sets if it satisfies both orientations. So its 1st side must divide both 1st and 2nd sides of the big, 2nd divides the 3rd side and 3rd divides also both 1st and 2nd. Then there are #d(gcd(A, B)) * #d(C) * #d(gcd(A, B)) such parallelepipeds (where #d is number of divisors). So we know the size of every intersection, thus we know the size of the union, which is the number of parallelepipeds that we can orientate somehow so it can pave the big. But now 2x3x5 and 3x2x5 are both counted. That's why we need to count something more, read the tutorial and I will continue if you don't understand.
•  » » » 23 months ago, # ^ | ← Rev. 2 →   +1 I understand to your part. Can you elaborate more? I mean, I know the inc-exc principle (union of a,b,c is a+b+c-ab-bc-ca+abc etc.) but I dont understand the editorial having read it 5 times already xDMaybe its just simple language but yours seem much more clear. Cant understand a single word from both solutions :P im bad at math lol Also, what do u mean about 2x3x5 and 3x2x5 being counted multiple times sir
•  » » » 23 months ago, # ^ | ← Rev. 3 →   0 So for one query we perform following algorithm: use exc-inc principle for all 6 permutations (1,2,3) and count intersections of each subset of sets so we can obtain the union of this permutations which is our answear am i right? Second question is what does exactly p(m) from the end of the editorial mean, i dont get it ;(
•  » » » » 23 months ago, # ^ |   +4 You were right in the beginning, but that is not exactly our answer. This is the answer, but when 1x2x3 is counted 6 times (as 1x2x3, 1x3x2, 2x1x3, 2x3x1, 3x1x2 and 3x2x1), 1x1x2 is counted three times (1x1x2, 1x2x1 and 2x1x1) and 1x1x1 is counted once.So the second number we count will be the same, but considering only parallelepipeds XxXxY, so two first sides coincide. Assume we fixed a set of sets and found which sides each side of the small parallelepiped must divide. In my example it was (A, B), (C), (A, B). Now as we know that first two sides are equal, we must unite the first two sets, so it will become: (A, B, C), (A, B, C), (A, B). So the number of such parallelepipeds will be #(gcd(A, B, C)) * #(gcd(A, B, C)) * #(gcd(A, B)).In the second number 1x2x3 was not counted (as 1 != 2), 1x1x2 was counted once (1x2x1 and 2x1x1 are not counted as 1 != 2) and 1x1x1 was counted also once.We multiply the second number by three and add it to the first. Now 1x2x3 is counted 6 times, 1x1x2 is counted 6 times and 1x1x1 is counted 4 times. Now we add #d(gcd(A, B, C)) * 2 and everything is counted 6 times. Then divide by 6 and get the answer.
•  » » » » » 23 months ago, # ^ |   0 So we do count the second number exactly the same as the first one but on each intersection we consider first two sides to be equal? We use inc-exc principle once again right?
•  » » » » » » 23 months ago, # ^ |   +3 Right.
•  » » » » » » » 23 months ago, # ^ |   0 And what did p(m) meant on the end od the tutorial on this task? (In time comlexity).
•  » » » » » » » » 23 months ago, # ^ |   +3 https://en.m.wikipedia.org/wiki/Partition_(number_theory) in case of m=3, p(m)=3: 1+1+1 (three unequal lengths), 2+1 (two equal lengths and one more), 3 (the equal lengths)
•  » » » » » » » » » 23 months ago, # ^ |   0 Last question.In counting second number we can assume that first and second are the same because of symmetry, right?
•  » » » » » » » » » 23 months ago, # ^ |   0 yes
•  » » » » » » » » » 23 months ago, # ^ |   +16 Thanks for help both of you guys. I appreciate it.
 » 23 months ago, # |   0 For div2C does cycle decomposition work if the permutation contains repeated elements? I mean for the proof it is assumed that there is a cycle decomposition?
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 Permutation can't contain equal elements
 » 23 months ago, # | ← Rev. 2 →   -8 Hi, can anyone please help me with my div2C submission, it is getting error on test case 8 #include using namespace std; int main(){ int n; cin>>n; std::vector v(n); for(int i=0; i>v[i]; sort(v.begin(),v.end()); int k=0; for(k; kv[0]) break; std::vector num(v.begin()+k,v.end()); int count=0; for (int i = 0; i < num.size(); ++i) { if(num[i]>v[i]) count++; //cout<