Блог пользователя NBAH

Автор NBAH, история, 8 месяцев назад, ,

Всем привет!

26 ноября в 19:05 MSK состоится рейтинговый раунд Codeforces #448 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.

Автором всех 5 задач являюсь я. Это мой второй раунд на Codeforces! Советую участникам ознакомиться с условиями всех задач. Надеюсь каждый найдет себе задачу по вкусу.

Хочется выразить благодарность координатору раунда gritukan за помощь в подготовке контеста и igdor99 за помощь в разработке задач, а также MikeMirzayanov за замечательные платформы Codeforces и Polygon. Ну и, конечно, Tommyr7, Arpa, gainullin.ildar за прорешивание раунда.

Разбалловка: 500-1000-1750-2000-2250

Удачи и высокого рейтинга всем!

UPD: Соревнование завершено! Скоро будет опубликован разбор.

UPD: Разбор

Поздравляем победителей!!!

Div1

Div2

•
• +405
•

 » 8 месяцев назад, # | ← Rev. 2 →   +16 Why this post is not on the main codeforces page? UDP: now it appears :P
•  » » 8 месяцев назад, # ^ |   0 I think NBAH posted it on his blog by mistake. It should be fixed soon.
•  » » » 8 месяцев назад, # ^ |   +74 I think Contest setters post it on their blogs, just that Mike/Coordinators pin it up on homepage..
•  » » » » 8 месяцев назад, # ^ |   +4 Yes, it's true
•  » » » » » 7 месяцев назад, # ^ |   +5
 » 8 месяцев назад, # | ← Rev. 2 →   +36 I think you should update "other testers" soon to show your respect and thank to them.
•  » » 8 месяцев назад, # ^ |   0 You were finally heard.
 » 8 месяцев назад, # | ← Rev. 2 →   +13 Too late for chinese! It will take place at 00:05(UTC+8). So I can't take part in this contest. But I also hope everyone high rating!
•  » » 8 месяцев назад, # ^ |   0 add oil next time
 » 8 месяцев назад, # |   0 why time is changed. in India it is 9.40 pm
 » 8 месяцев назад, # |   +285 short sad story
•  » » 8 месяцев назад, # ^ |   0 hahahha savage :p
•  » » 8 месяцев назад, # ^ |   0 23333
 » 8 месяцев назад, # |   0 So many rated contests, thanks to last 2 week contests I was upgraded my RATING very much!Hope everyone will get high rating and wish codeforces polygon luck!
 » 8 месяцев назад, # |   +6 glhf
 » 8 месяцев назад, # | ← Rev. 3 →   -26 You also like this sound of dislikes
•  » » 8 месяцев назад, # ^ |   +2 Good luck!
•  » » 8 месяцев назад, # ^ |   0 Good luck!It helped to my friend Just_Solve_The_Problem on his last comment ... )
 » 8 месяцев назад, # | ← Rev. 2 →   -40 isitrated!!?!?!?!???!
 » 8 месяцев назад, # |   +18 High ratings to everybody! _______What a sad story..T_T
 » 8 месяцев назад, # |   +2 I hope no large queue like the last educational round , I should't be wating 15 min+ to know whether my solution passes pretests .
•  » » 8 месяцев назад, # ^ |   0 yes that sucks. 1-3 minutes is ok but 15-20 is too much
 » 8 месяцев назад, # | ← Rev. 2 →   +11 Wish Everyone will get high scores! NBAH's previous contest Codeforces Round #367 (Div. 2) was wonderfull and gave high ratings at the end. I hope this one will be more than wonderfull for everyone. Good Luck and High Ratings.
 » 8 месяцев назад, # |   0 Good luck!!!
 » 8 месяцев назад, # |   -10 IS this contest rated ?
 » 8 месяцев назад, # |   -31 is this contest rated ?
•  » » 8 месяцев назад, # ^ |   +3 let's hope so.
•  » » 8 месяцев назад, # ^ |   +4
•  » » » 8 месяцев назад, # ^ |   0 hhhhh
 » 8 месяцев назад, # | ← Rev. 2 →   -17 Wish you can get high rating!
 » 8 месяцев назад, # |   0 Thanks for scoring ! This round is now enough special to remember it a long time :)
 » 8 месяцев назад, # |   +12 Отчисление-отчислением, а контест — по расписанию
 » 8 месяцев назад, # |   +16 I have noticed that Arpa is mentioned/thanked in every blog post. Great job man.
 » 8 месяцев назад, # |   +12 1750 points for problem C... Seemed like a challenging contest. Still wish for the best for everyone ;)
 » 8 месяцев назад, # |   0 GL & HF
 » 8 месяцев назад, # |   0 Wish you can get more and more score.
•  » » 8 месяцев назад, # ^ |   0 Wish you can get high rating!
 » 8 месяцев назад, # |   0 good luck and have fun every one :D
 » 8 месяцев назад, # | ← Rev. 2 →   +17 The best thing about the blog is — not using this line As usual, the scoring will be announced shortly before the start of the contest.
 » 8 месяцев назад, # |   0 Best of luck to all!!
 » 8 месяцев назад, # |   -26 Is it rated?
•  » » 8 месяцев назад, # ^ | ← Rev. 2 →   +9 It's asked You had better ask "Is it DATED?"
•  » » » 8 месяцев назад, # ^ | ← Rev. 2 →   -13 Is it dated?
•  » » 8 месяцев назад, # ^ | ← Rev. 10 →   +18 Did you see NBAH's wish "_High ratings to everybody!_" in the last line of the announcement.**???**if(yes){Why couldn't you realize that this contest is rated.}else{Read again!}
•  » » » 8 месяцев назад, # ^ |   0 May be bcoz he don't know about "if else" statement used in ur code...
 » 8 месяцев назад, # |   0 ПУЗЫРЬ!!! Это ты? :)
 » 8 месяцев назад, # |   0 some problem with submission here in live contest
 » 8 месяцев назад, # |   +2 WTH , NOt able to hack
 » 8 месяцев назад, # |   +5 lol
 » 8 месяцев назад, # |   +9 No hacking, problems are too hard. Great contest...
 » 8 месяцев назад, # |   +2 As predicted, problem C is much more difficult than usually.
•  » » 8 месяцев назад, # ^ |   +18 B as well.
 » 8 месяцев назад, # |   +4 Go no rating...
 » 8 месяцев назад, # |   +7 Good problem set.Happy_minus_Rating
 » 8 месяцев назад, # |   0 Is it Div-1 contest ?
 » 8 месяцев назад, # |   +18 Is it Div-1 contest ?
•  » » 8 месяцев назад, # ^ |   +78 typical Div 1.5
 » 8 месяцев назад, # |   +28 The first A-B-C problems should be B-C-D.
 » 8 месяцев назад, # |   +3 что-то второй уже раунд немного тяжеловат для див2
 » 8 месяцев назад, # |   +7 "High ratings to everybody!"Problems are way harder than usual.
•  » » 8 месяцев назад, # ^ |   +12 I would agree. The problems were way too difficult, especially B and C. Goodbye rating :(
 » 8 месяцев назад, # | ← Rev. 2 →   0 How to solve D? I thought of fixing first position where a[i] < c[i] < b[i] but c[i] can be equal to b[i] and become less later(for example ab bc answer is 1(ba)).
•  » » 8 месяцев назад, # ^ |   0 DP[position in permutation][is current permutation already grater than a flag (0 or 1)][is current permutation already less than b flag (0 or 1)].
•  » » 8 месяцев назад, # ^ | ← Rev. 4 →   0 Consider a function f(stringx, 26 - numbers) which returns number of strings s constructed with characters which is given in the input, that s < xf(x, 26numbers) can be solved using the first position that you said and the answer is f(b, (a - characters)) - f(a, (a - characters)) - 1
 » 8 месяцев назад, # |   -58 the contest was very bad it was like div 1 please dont ever write a contest and please make it unrated because it was bullshit
•  » » 8 месяцев назад, # ^ | ← Rev. 2 →   -40 because of this him my rank will decrease !!
•  » » 8 месяцев назад, # ^ |   0 I'm agree with you
 » 8 месяцев назад, # |   0 Pretest 9 for C?
 » 8 месяцев назад, # | ← Rev. 2 →   0 Why my code for E is so slow? http://codeforces.com/contest/895/submission/32688252
•  » » 8 месяцев назад, # ^ |   0 I think it is because you are always propagating and you only have to do it when it is necessary(i.e. lazy[nodo] != 0)
•  » » » 8 месяцев назад, # ^ |   0 Thank You, I will check this.
 » 8 месяцев назад, # |   +1 what is the 8th pretest for b ? What is wrong in this ? https://ideone.com/dIQKbm
•  » » 8 месяцев назад, # ^ |   +1 You need to think about the case k = 0
•  » » 8 месяцев назад, # ^ |   0 I was also stuck on the 8th pretest. It has k == 0, which may lead to WA for some programs if you don't take care of the case.
•  » » 8 месяцев назад, # ^ |   0 Even I got wrong answer on 8th pretest. I just handled the special case for k = 0 and the pretests passed
•  » » 8 месяцев назад, # ^ |   0 and u have to handle that a[i] <= a[j]
 » 8 месяцев назад, # | ← Rev. 2 →   -52
•  » » 8 месяцев назад, # ^ |   +13 You need to choose subarray not subsequence.
•  » » 8 месяцев назад, # ^ |   0 I used 0-1-knapsack for problem "A"..But still WA at test case 8....
•  » » » 8 месяцев назад, # ^ | ← Rev. 2 →   0 Check this comment:http://codeforces.com/blog/entry/56005?#comment-397517
•  » » 8 месяцев назад, # ^ | ← Rev. 5 →   +17 Because segments have to be continuous
•  » » 8 месяцев назад, # ^ |   +1 It said "continuous" pieces......I didn't catch that "continuous" first and was hacked at 1:30 ..........
•  » » 8 месяцев назад, # ^ |   0 Why 2^N? I think N^2.
•  » » » 8 месяцев назад, # ^ |   0 yuShaf sets
 » 8 месяцев назад, # |   0 Is solution of E based on sqrt decomposition?
•  » » 8 месяцев назад, # ^ | ← Rev. 2 →   +5 In E, notice how the update affects any particular value. Assume we store the expected value at each index at current time. Now we have to deal with an update. Consider any value in the left subarray. Let size of left and right subarrays be S1 and S2 respectively.final_value = (S1-1)/S1 * previous_value + (sum of values in right subarray)/(S1*S2) Similar argument can be used for all values in the right subarray as well.Simulate these operations using a segment tree and lazy propagation. Code
•  » » » 8 месяцев назад, # ^ |   0 what about non independence of values?
•  » » » » 8 месяцев назад, # ^ |   +11 What do you mean by non-independence? I am using linearity of expectation which does not require any such condition.
•  » » » » » 8 месяцев назад, # ^ |   0 I am fool, i forgot about independence of E... I thought E(x+y)!=E(x)+E(y) if x and y dependent of each other.
•  » » » » 8 месяцев назад, # ^ |   0 It's expected value not variance.
 » 8 месяцев назад, # |   0 How did people solve C? Unable to access other submissions as of now.
•  » » 8 месяцев назад, # ^ | ← Rev. 2 →   +14 The number is perfect square iff all prime degrees are even. So you can do dp with bitmask since there is only 19 primes until 70.
•  » » » 8 месяцев назад, # ^ |   0 Didn't know this fact, thanks)
•  » » » 8 месяцев назад, # ^ |   +3 I figured as much. Could you give a more detailed description of your dp (states and transition)?
•  » » 8 месяцев назад, # ^ | ← Rev. 3 →   +4 edit:wait nm this is too complicated lolIf some number is prime and >35, then it's only prime is itself.Otherwise, it can be decomposed into the first 11 primes (up to 31). Build a bitmask for each number where mask[i] = the parity of number of times the i'th prime divides the number.Now do dp(first i numbers, xor value of j) dp (it's like knapsack). Use the sliding window thing to save memory. This takes care of first 11 primes. Take ans = dp(n,0)For the rest of the primes, they need to occur an even number of times in a subset. So if there are count(p) occurrences of prime p, p>=37, then you can do this 2^(count(p)-1) ways (it's p choose 0 + p choose 2 + ...). So just multiply this together for each prime p, 37<=p<70, and multiply by res and subtract 1 for the empty case.
•  » » » 8 месяцев назад, # ^ |   0 I did the exact same fuckin thing, still couldn't pass the 14th test case :(
•  » » » » 8 месяцев назад, # ^ |   0 I handled squares and non-squares differently. I even know where my bug is :( but too slow.
 » 8 месяцев назад, # |   -41 this contest was awful! so sad!
•  » » 8 месяцев назад, # ^ |   +27 Nope! Great problems. I've never failed at B so hard tbh... but C was a lot of fun, only if I could finish my dp in time. Great problems.
•  » » » 8 месяцев назад, # ^ |   0 What is an idea behind your DP approach?
•  » » » 8 месяцев назад, # ^ |   +1 What were your dp states might I ask?
•  » » » » 8 месяцев назад, # ^ | ← Rev. 2 →   0 i'll give you my incomplete code https://ideone.com/BP05OfThe idea is bitmask dp and knowing that choosing odd and even number of items from a collection of size n is just 2^n-1Please look for "solve", which is the entry point. I know my template is big :|
•  » » » » 8 месяцев назад, # ^ |   0 Explanation from AdiZer0 : The number is perfect square if all prime degrees are even. So you can do dp with bitmask since there is only 19 primes until 70.
•  » » » » » 8 месяцев назад, # ^ |   0 Correct. We want dp[n][mask=0]
 » 8 месяцев назад, # | ← Rev. 2 →   0 Hack for the first problem: 5 72 72 73 74 69 Ans: 66
•  » » 8 месяцев назад, # ^ |   0 Sad! I forgot that "sectors should be continuous" and submitted something useless :(
 » 8 месяцев назад, # |   +4 Somebody please explain div2 A ,as it had the worst explanation ever :/
•  » » 8 месяцев назад, # ^ |   0 Select a continuous subsegment such that the difference between the sum of the selected slices and the sum of the unselected slices is as small as possible.
•  » » » 8 месяцев назад, # ^ |   +2 He Could've wrote subsegment instead of sectors, too misleading
•  » » » 8 месяцев назад, # ^ |   0 Can you explain more with example specially if one of sector is not selected then what is case?
•  » » 8 месяцев назад, # ^ |   0 The problem gives you N pieces of pizza, with sizes in array 'a'. The sum of all these sizes add up to 360. Now, the problem is asking for the minimum difference between 2 section if we split the pizza into 2 contiguous sections. We can start from position 1 and iterate through, keep track of the sum before called 'SUM'. Since we know the total sum is 360, we can find the sum of the other piece by doing 360 — SUM. We then take ans = min(ans, abs(SUM — (360 — SUM)). The pizza is circular, so we can start from all possible starting positions (1...n) and do the same thing. The answer is then the minimum over all starting positions.
•  » » » 8 месяцев назад, # ^ |   0 There is no any case for this-> if one of sector is not selected ?
•  » » » » 8 месяцев назад, # ^ |   0 If one of the sectors is not selected, then we know the sum of one sector is 0 (because not selected), and the other one must be 360. So, the highest answer possible would be 360. We can set our answer to 360 initially to cover this case.
•  » » » » » 8 месяцев назад, # ^ |   0 Thanks For Help
 » 8 месяцев назад, # |   +4 Problems were harder than usual ( specially A and B )
 » 8 месяцев назад, # | ← Rev. 2 →   +3 How to solve div 2 problem A and B?
•  » » 8 месяцев назад, # ^ |   0 In problem A you can use dp, or just calculate the minimum sum, by(pseudo) cyclic shift. More in my code: Click
 » 8 месяцев назад, # |   0 Когда разбор ?
 » 8 месяцев назад, # |   +22 Very interesting tasks, I enjoy a lot of solving this problems !
•  » » 8 месяцев назад, # ^ |   0 How to solve C?
•  » » » 8 месяцев назад, # ^ | ← Rev. 2 →   +5 Note that there are atmost 19 primes less or equal to 70. And do something like dp[current_number][mask of primes you have to get rid of].
•  » » » » 8 месяцев назад, # ^ | ← Rev. 5 →   0 the time complexity is 2^19 * 100000 = 5e10. Can it fit the time limit? UPDATED: we can actually do in 2^19 * 70.
•  » » » » » 8 месяцев назад, # ^ |   0 No. But you can notice that there are atmost 70 distinct numbers and reduce the complexity to 219·70.
•  » » » » » 8 месяцев назад, # ^ | ← Rev. 2 →   0 If you have a number repeated k times in input, then parity is 0 for it's prime factors if the number is chosen even number of times, and parity is odd otherwise.
•  » » » » 8 месяцев назад, # ^ |   0 Please explain a it more about the dp formulation.
•  » » » » » 8 месяцев назад, # ^ |   +1 Imagine you grouped all numbers by their values (all except 1, we shall consider it separately).Let mask[i] be a mask where ones denote primes that occur odd number of times in the factorization of i.The main idea is that a number is a perfect square if all the degrees of its primes are even. So now denote dp[group][mask] as the number of ways to obtain such a mask of odd primes if we use numbers from groups 2 to group.To make a transition note that if we take an even number of elements from group + 1, the mask doesn’t change. Otherwise the last taken element will change the parity of some primes. Hence out current mask gets xorred with mask[group + 1].The only observation left is that the number of ways to take either an odd or an even amount of numbers if there are n of them is equal to 2n - 1.
•  » » » 8 месяцев назад, # ^ | ← Rev. 2 →   0 For each integer in interval [1,70] you can save mask of prime divisiors ( 19 prime divisiors until 70). After it you can iterate over numbers from 1 to 70 and calculate next DP state : DP [ i ] [ mask ] = amount of subsets with numbers ( 1...i) and current mask of of prime divisiors.
•  » » » » 8 месяцев назад, # ^ |   +1 Can you elaborate it a bit more?
•  » » » 8 месяцев назад, # ^ | ← Rev. 3 →   +3 Let fi =  how many numbers i there are in array. Note that there are 19 primes up to 70. Also, note that in square number number of occurences of every prime must be even. Considering all of that dodpi, parityMask =  how many subsets there are containing only numbers 1 ≤ x ≤ i such that parity of number of occurences of i-th prime is denoted by i-th bit in parityMask. Obviously, dp0, 00...00 = 1. Figure out the remaining part of solution yourself. Answer to the problem will be dp70, 00...00.
•  » » » » 8 месяцев назад, # ^ |   +1 Can you give some hints for the rest of the solution?
 » 8 месяцев назад, # |   0 Do you think B will pass If I used map instead of index compression? I had map which tells me this: if map[a] = b, it means that b numbers have exactly a numbers strictly smaller than them, divisible by x.
 » 8 месяцев назад, # |   0 Do you think my solution for B will pass time limit, I used map instead of index compression?
•  » » 8 месяцев назад, # ^ |   0 i also used map.. but i used map. i'm not sure it will pass or not :(
•  » » » 8 месяцев назад, # ^ |   +1 Well, it works in logN. So I think you both do not need to worry about TL
•  » » » 8 месяцев назад, # ^ |   0 My mistake, I also used long long.
•  » » 8 месяцев назад, # ^ |   +1 got ac bro :D
•  » » » 8 месяцев назад, # ^ |   +1 me too :D
 » 8 месяцев назад, # |   0 Gah problem B apparently had so many edge cases, I kept getting stuck at the later tests
 » 8 месяцев назад, # |   +1 What's the hack for B?
•  » » 8 месяцев назад, # ^ |   +2 Handle k = 0 and duplicates in the array.
•  » » » 8 месяцев назад, # ^ |   0 I believe both of them were already there in the sample cases!
•  » » » » 8 месяцев назад, # ^ | ← Rev. 2 →   +1 I meant duplicates when k = 0, for example the case8 3 01 1 1 3 3 3 3 3
•  » » » » » 8 месяцев назад, # ^ |   +2 What's the answer?
•  » » » » » » 8 месяцев назад, # ^ |   0 Ans = 9 as you can create 9 pairs using the three 1s.
•  » » » » » 8 месяцев назад, # ^ |   0 I suppose case like 3 4 0 9 9 10 is better.
•  » » » » » » 8 месяцев назад, # ^ |   0 is the answer 7?
•  » » » » » » » 8 месяцев назад, # ^ |   0 Yes, it's 7 with indexes pairs: 1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 3-3.
•  » » 8 месяцев назад, # ^ | ← Rev. 2 →   0 670 20 50 50 80 90
•  » » » 8 месяцев назад, # ^ |   +1 not A. I am talking about B.
•  » » » » 8 месяцев назад, # ^ |   0 Oh sorry.
 » 8 месяцев назад, # |   0 When you get hacked by a runtime error and can't fix it for a whole hour...
 » 8 месяцев назад, # |   +9 PEOPLE ON CODEFORCES ARE GOOD AT SARCASM
 » 8 месяцев назад, # |   +7 Very hard contest but problems were very interesting.
 » 8 месяцев назад, # |   0 What's the answer of B:- 5 3 1 1 2 3 4 5
•  » » 8 месяцев назад, # ^ |   0 9
•  » » » 8 месяцев назад, # ^ |   0 Cam i ask how the answer is 9?
•  » » » » 8 месяцев назад, # ^ |   0 Good pairs are: (1,3),(1,4),(1,5),(2,3),(2,4),(2,5), (3,3), (3,4), (3,5)
•  » » » » » 8 месяцев назад, # ^ |   0 Thank u, i get it.
 » 8 месяцев назад, # | ← Rev. 2 →   -23 any idea about this code bug(bug'S)???-problem B- #include #define F first #define S second using namespace std; const int maxn=1e5+7; int a[maxn];//,r[maxn],l[maxn]; mapmp,cnt; pairb[maxn]; vector >vec; int32_t main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n,x,k;cin>>n>>x>>k; for(int i=1;i<=n;i++)cin>>a[i],cnt[a[i]]++; sort(a,a+n); int ans=0; for(int i=1;i<=n;i++){ if(a[i]==a[i-1])vec.back().S++; else vec.push_back({a[i],1}); } for(int i=1;i
•  » » 8 месяцев назад, # ^ |   +4 5 3 1\n 1 2 3 4 5 ans is 9.your code prints 31.
 » 8 месяцев назад, # |   +18 excellent problem set!
 » 8 месяцев назад, # |   0 Is there a way to solve B without iterating on all possible pairs?
 » 8 месяцев назад, # |   +4 Div1.7-1.8
 » 8 месяцев назад, # |   +3 Can anyone help explain why my solution to B times out on case 14? Thanks in advance!32692235
•  » » 8 месяцев назад, # ^ |   0 You have a double for loop from 1 to n, so the code runs in O(N^2) time. Since n = 10^5, you need O(NlogN) or similar. (In general, less than 10^8 or 10^9 operations is safe)
•  » » » 8 месяцев назад, # ^ |   0 May I ask where I have a double for loop? I thought my time complexity was O(NlogN) due to multiset. I may have put a double for loop by accident somewhere though.
•  » » » » 8 месяцев назад, # ^ |   0 Oh, sorry I read your code wrong. Idk
•  » » » » » 8 месяцев назад, # ^ |   +1 It's no problem, thanks for the help!
•  » » 8 месяцев назад, # ^ |   +4 Afaik distance works in o(n) with std::set.
•  » » 8 месяцев назад, # ^ |   +4 std::distance works in O (N) . So your code works in O (N^2).P.S. std::distance is same as using 'it++' several times.
•  » » » 8 месяцев назад, # ^ |   0 oh I didn't realize that. That's unfortunate for me. Thanks for the help!
•  » » » » 8 месяцев назад, # ^ |   0 Yep, std::distance is too costly for a multiset. If you use a vector, sort the values, and use lower_bound and upper_bound, getting the indices of iterators is O(1), rather than O(n) for the multiset!
 » 8 месяцев назад, # |   0 what is pretest 8 in prob A. solved nothing today. I calculated two segments with the min difference between them like partition problem but that is apparently not the case.
•  » » 8 месяцев назад, # ^ |   0 I got WA in pretest 8 because I was taking a subsequence (not consecutive values).
•  » » » 8 месяцев назад, # ^ |   0 Div 2 used pretest 8 thunderbolt, it was super effective. totodile fainted. send totodile and the attached energies to discard pile.
•  » » 8 месяцев назад, # ^ |   0 Check this comment :http://codeforces.com/blog/entry/56005?#comment-397517
•  » » » 8 месяцев назад, # ^ |   0 was doing subsequences instead of taking continuous element :'(.
 » 8 месяцев назад, # | ← Rev. 2 →   -23 is it still rated?
 » 8 месяцев назад, # |   +10 How does this contest fit into the pizza of life?
 » 8 месяцев назад, # |   +34 In problem B statement, did you guys notice that previously it was written find the number of different UNordered pairs of indexes (i, j) which killed me. After the contest, it shows ordered. In the beginning, I realised that the solution would be with lower/upper bounds, but that very statement confused me and pushed me to thinking in terms of self-balancing trees & adding elements from end towards start, which I spent a lot of time and coded. After that in the test case 3, realised that it's not like that :(
•  » » 8 месяцев назад, # ^ |   +16 Why don't announce this change? NBAH
•  » » 8 месяцев назад, # ^ | ← Rev. 2 →   +13 That's a huge error, they have to address it.
•  » » 8 месяцев назад, # ^ |   +13 Spent the whole contest in this problem ...
•  » » 8 месяцев назад, # ^ | ← Rev. 4 →   +12 It should've been announced.Even I solved the earlier version until i reread it in the last few minutes.
•  » » 8 месяцев назад, # ^ |   0 Solving for the number of unordered pairs is no different from ordered pairs since if (i,j) fulfills the condition Ai <= Aj then (j,i) doesn't, unless of course i is equal to j
•  » » » 8 месяцев назад, # ^ |   +11 No! For unordered pair, (i, j) = (j, i), however, for ordered pairs, (i, j) != (j, i). (of course for distinct i, j's).
•  » » 8 месяцев назад, # ^ |   0 shyamumaury96 bhai urated krwa de !
 » 8 месяцев назад, # |   0 Problem B: Is this Spoiler3nlogncomplexity optimal?
•  » » 8 месяцев назад, # ^ |   0 Yes, That should pass.
•  » » » 8 месяцев назад, # ^ |   0 Yeah, I know it'll pass. I mean is it the best complexity we can reach?
 » 8 месяцев назад, # | ← Rev. 2 →   0 What is test 47 on B?EDIT: never mind, i think i mishandled k = 0 so the lower bound could be > a[i]
 » 8 месяцев назад, # |   0 What is the idea of problem C?
•  » » 8 месяцев назад, # ^ |   +6 If we use naive bitmask dp for each prime, it is O (N)*2^19 (because there are 19 primes between 1 and 70) which results time exceed. The idea is if the number is a prime which exceed 35, it must be grouped with a same number. So it can be pre-processed. Since there are 11 primes between 1 and 35, this solution is O (N)*2^11 which gives AC. P.S.Be careful of using % while implmenting it -it gives TLE
•  » » » 8 месяцев назад, # ^ |   0 GGOSinon How to do bitmask transitions using iterative DP ??? I know only for the Recursive One and thus could not solve it in time.I thought the same :(
•  » » » » 8 месяцев назад, # ^ |   0 Let d [i][j] as a number of way to make state j by using number a[1]~a[i].Let b [i] as a bitmask form of a[i]. We can divide the case : use the b [i] or not. So the recursive formula is d[i+1][j]=d [i][j^b [i]]+d[i][j] ('^' is xor operator) You can implement it by just iterating i and j using 2 'for's to 0~n-1, 0~(2^19)-1. (Initial value is d [0][0]=1, Answer is d [n][0])
•  » » » 8 месяцев назад, # ^ | ← Rev. 4 →   +6 You can also correct this issue by noting that there are at most 70 distinct values in the array you are given, so you just use a frequency array for each of the numbers between 1 and 70 and noting that the number of ways to choose an odd number of numbers out of a set of K numbers is always 2K - 1 for K > 0.
•  » » » » 8 месяцев назад, # ^ |   +5 ntfoim 70 distinct value of what ???
 » 8 месяцев назад, # |   -6 Many people will get rating rise just for solving A :v
•  » » 8 месяцев назад, # ^ |   -7 And that's another reason why this contest was awful.
•  » » » 8 месяцев назад, # ^ |   0 Well, since I'll probably get a rating rise, I'm not gonna say this is awful :)
•  » » » » 8 месяцев назад, # ^ | ← Rev. 2 →   +2 I only solved A and my rating will go up but that was an awful contest.
•  » » » » » 8 месяцев назад, # ^ |   0 I only solved A and my rating went down so this was an awful contest! :)
•  » » 8 месяцев назад, # ^ |   +17 I think they wanted to justify their statement "High ratings to everybody!" :P
 » 8 месяцев назад, # |   0 A contest where the one can be proud of solving A & B
 » 8 месяцев назад, # |   +5 Good Questions , i really enjoyed it..hope others too ;-)
 » 8 месяцев назад, # |   -11 Bitmasks + some knowledge of Combinatorics is Div.2 C now? What's the world coming to?
 » 8 месяцев назад, # |   -9 is it rated?
 » 8 месяцев назад, # |   0 For Problem A in Test case 50: 741 38 41 31 22 41 146 Output: 14 Is it correct? and how Explain pleaseThanks :)
•  » » 8 месяцев назад, # ^ |   +3 take the first 41 with the last 146, their sum is 187, the remaining is 360-187 = 173, therefore the difference between the 2 shares is 187-173 = 14
•  » » » 8 месяцев назад, # ^ |   0 But if i take series 1: 41 41 41 38 22series 2:146 31than the difference between series1 and series2 is 6
•  » » » » 8 месяцев назад, # ^ |   0 you must take some numbers which are adjacent to each other, note that in this problem first and last numbers are adjacent too
•  » » » » » 8 месяцев назад, # ^ |   +3 Thanks :)
 » 8 месяцев назад, # | ← Rev. 2 →   0 can someone please explain for the pizza separation ques why the ans for the below sample test is 120 !! 5 30 60 180 60 30 what should be the ans for this ?? ans can be zero when the 1 continuous sector contains 60 +30 +30+ 60 = 180 (starting from the 2 last 30 to the first 30 in anticlockwise order) and the 2 continuous sector contains only 180 so 180-180=0 (minimal possible difference) But my code fails for this system test case ,it is showing the ans 120 but i think minimal diff 0 can be achieved .. plzz anyone tell me i cant find where i am wrong in logic or thinking ("ANY HELP WILL BE APPRECIATED")
•  » » 8 месяцев назад, # ^ |   0 Your code gives 120 . The expected answer is 0 .
•  » » » 8 месяцев назад, # ^ |   0 yes ok thnkss i understand where i am doing wrong i will code it again i am new here thnkss for ur time :)
•  » » 8 месяцев назад, # ^ |   0 Your submission 32688201 checks:A) Situations "FFFFSSSSSSS" for any numbers of Fs and Ss.B) Situations "FSSSSSSFFFF" for any numbers of Ss and Fs only at the tail.Your code can't correctly process something like "FFFSSSSFF".
•  » » » 8 месяцев назад, # ^ |   0 yes in between nos are not checked between the head and tail i have to rectify this
 » 8 месяцев назад, # |   +46 Good contest, Very good contest, the problems where good and where fun to solve, thank you NBAH for this good contest. But please keep in mind that the problems where too hard for a div2 contest
 » 8 месяцев назад, # |   0 Can anyone explain why my solution to B gets WA on case 21? 32682296 Thanks.
•  » » 8 месяцев назад, # ^ |   0 Input:5 3 0 2 4 5 7 9Your answer: 4Correct answer: 5. (1, 1), (2, 2), (3, 3), (4, 4), (2, 3)
 » 8 месяцев назад, # |   0 why here UndefinedBehavior http://codeforces.com/contest/895/submission/32691004 ? but here everything is normal http://codeforces.com/contest/895/submission/32693522 . changed only this auto x=lower_bound(a.begin(),a.end(),lp); auto y=upper_bound(a.begin(),a.end(),rp); ans=ans+y-x;  auto x=lower_bound(a.begin(),a.end(),lp); auto y=upper_bound(a.begin(),a.end(),rp); ll p=(ll)(y-x); ans+=p; he in int started to count all?
•  » » 8 месяцев назад, # ^ |   +3 Note that y could be equal to a.end().std::vector::end() is a special kind of iterator.I think it is not specified what happens if you add an integer to it (as you do in ans+y part of 32691004).Regardless, I would use parentheses to avoid unnecessary integer-iterator addition (as well as the subsequent subtraction): ans=ans+(y-x);
 » 8 месяцев назад, # |   0 Albeit I didn't manage to solve D in time, the contest was really cool. The only thing to bother me was the unclear statement of B. Keep it up :D
•  » » 8 месяцев назад, # ^ |   0 I was thinking I was the only one who have read B many times until really understand what to do in this problem
 » 8 месяцев назад, # | ← Rev. 3 →   0 Писать автору задач не решился(я ведь просто нубас с 1.2к), поэтому спрошу тут. Разве важен в задаче А порядок кусков пиццы? К примеру инпут 5 90 89 88 87 6. 90+89 образуют ближайший к 180-и угол из возможных, ответ (180-179*)2, то бишь 2. Окей, все понятно, но вот такой инпут: 5 90 87 88 89 6. Тут уже поинтереснее, хотя куски такие же. Если порядок имеет значение, то ответ 6: abs(180-(6+90+87))*2. Но если порядок значения не имеет, то ответ тот же 2. Для интереса проверил несколько скриптов гуру с 1-й странице, все решают линейно, с тем же порядком. Так и должно быть? Если порядок не имеет значения, то все эти решения улетят в пропасть, нужно будет решать по-другому(рекурсивно, например, обходя неюзанные куски, пока сумма <180).
•  » » 8 месяцев назад, # ^ |   0 Сектора должны быть непрерывны, то есть порядок важен.
 » 8 месяцев назад, # |   +10 Wow !! This was one of the best contests I have ever participated in <3. All the problems were very , very nice ! I really enjoyed the round as well as the problems. Take my heartiest love NBAH <3 <3 Hope we will get such awesome problems from you in the future. Keep up the good work man :)And many many thanks for such nice round and all your efforts in it :)
 » 8 месяцев назад, # |   +12 I have trained for 5 days and became specialist. I am looking forward to next contest
•  » » 8 месяцев назад, # ^ |   0 from where did u read any special site
•  » » » 8 месяцев назад, # ^ |   0 acmp.ru and solved problems as more as I can
•  » » » » 8 месяцев назад, # ^ |   0 but bro it is in diff language and i cant understand it
•  » » » » » 8 месяцев назад, # ^ |   0 there are many sites in English.
 » 8 месяцев назад, # |   +2 http://codeforces.com/contest/895/submission/32679304 is judged an error, but works in my compiler?
•  » » 8 месяцев назад, # ^ |   +5 the last line in your while loop should be if(i==n) i=0 not i==0
•  » » » 8 месяцев назад, # ^ |   0 ty
 » 8 месяцев назад, # | ← Rev. 3 →   +5 [update: ACCEPTED] Where is my wrong approach for problem B 32694817
 » 8 месяцев назад, # | ← Rev. 2 →   0 Contest : Omae wa mou shindeiru.Me : Nani?
 » 8 месяцев назад, # |   0 delete2/32687180, coutinho/32687203, OutSpace/32688038, blindspot/32689194LOL, this is 4 photo machines. I was canceled for using the ideone for C. And these 4 people have found, then they copy my code. My fail but I hate their, LOL
 » 8 месяцев назад, # |   +1 Can someone please suggest some cases(possibly small n so that I can debug) for my code (Problem C) http://codeforces.com/contest/895/submission/32711673It is giving correct answer till n=1000 (in System cases) but I don't know why it is giving WA for n around 10e5
•  » » 8 месяцев назад, # ^ | ← Rev. 2 →   0 You missed a prime number, you only have 19, and there are 20 in total. Edit: nevermind.
•  » » » 8 месяцев назад, # ^ |   0 We have 19 primes before 70 https://primes.utm.edu/lists/small/100000.txtPlease tell me which one I am missing if I am wrong
•  » » » » 8 месяцев назад, # ^ |   0 My mistake, my code said 20 because it counted up to 75.
•  » » 8 месяцев назад, # ^ |   0 pw2 array size should be 1e5 not 70.
•  » » » 8 месяцев назад, # ^ | ← Rev. 2 →   0 Thanks :)
 » 8 месяцев назад, # |   0 How to slove B? QAQ
 » 8 месяцев назад, # | ← Rev. 6 →   0 Can anyone tell me what's wrong with this code? #include #include using namespace std; int main() { long long n; cin>>n; vector a(2*n); for(int i = 0 ; i < n; i++) { cin>>a[i]; a[i+n] = a[i]; } int mindiff = 360; for(int i = 0; i < 2*n; i++) { int curr = 0; for(int k = i; i < 2*n && curr < 180; k++) { curr+=a[k]; mindiff = min(mindiff, 2*abs(180-curr)); } } cout<
•  » » 8 месяцев назад, # ^ | ← Rev. 2 →   0 Line 16 should be k < 2*n instead of i < 2*n
•  » » » 8 месяцев назад, # ^ |   0 Thanks haleyk100198 my bad :(
 » 8 месяцев назад, # |   +2 THIS IS VERY IMPORTANT !!! I submitted my solution for problem A during the contest and it passed the pretests then I got RTE on test 49 during system test phase, after the contest I resubmitted the exact same code and I got ACCEPTED !!!!submission during contest : http://codeforces.com/contest/895/submission/32683171 submission after the contest : http://codeforces.com/contest/895/submission/32733925PLEASE nbah CHECK THIS PROBLEM ! THANKS.
•  » » 8 месяцев назад, # ^ |   +5 I belive that you accessed invalid position on the array as you used `for (int j=i; j
 » 8 месяцев назад, # |   +3 One of the most informative rounds ever. Thanks for your efforts!
 » 8 месяцев назад, # |   0 Can anyone explain Meet in the middle solution for C?
 » 8 месяцев назад, # |   +3 What's the idea behind this submission 32677264 for problem C?
 » 8 месяцев назад, # |   0 What is a smaller form of test case 13 for C? My program keeps outputting 1000000006 and I don't know why. A lot of other people also have the same wrong output.
•  » » 7 месяцев назад, # ^ |   +1 Maybe you need to change int to long long?you cannot make x = a*b%MOD using integers for a and b because they will overflow and you will take the MOD from the result of this overflow
•  » » » 7 месяцев назад, # ^ |   0 Thanks so much! That was the error, apparently. So the -1 output was just a coincidence. :P
 » 7 месяцев назад, # |   +3
 » 7 месяцев назад, # |   0 There's a small bug in the winners.The rank9 of div1 is the same as the rank1 of div2.
 » 7 месяцев назад, # |   0 Why is problem A wrong? test case 8 says answer is 40 while the true answer is 0. Come on guys no one wants to correct it??? :(
•  » » 7 месяцев назад, # ^ |   +3 Considering that there are more than 3000 people who have solved the problem, it's more likely that you're wrong. :) Did you split the pizza into two continuous sectors?
•  » » » 7 месяцев назад, # ^ |   0 You're right. I didn't know it should be continuous:( I thought too complicated. Thank you