NBAH's blog

Codeforces Round #448(Div.2)
By NBAH, history, 7 years ago, translation, In English

Hi everyone!

Codeforces Round #448 (Div.2) takes place on 26th of November at 19:05 MSK. As usual, Div.1 participants can join out of competition.

This is my second round on Codeforces! I advise you to read all of the 5 problems. Hope everyone will find something interesting.

I'd like to thank vintage_Vlad_Makeev for coordination, igdor99 for helping me in developing problems. And, surely, thanks to Tommyr7, Arpa, 300iq for testing this round.

Of course, many thanks to MikeMirzayanov for great Codeforces and Polygon platforms.

Scoring: 500-1000-1750-2000-2250

High ratings to everybody!

UPD: Contest is finished. Editorial will be posted soon.

UPD: Editorial

Congratulations to the winners!!!

Div1

  1. uwi

  2. Benq

  3. irkstepanov

  4. dreamoon_love_AA

  5. JustasK

  6. eddy1021

  7. yancouto

  8. chemthan

  9. Nephren_Ruq_Insania

  10. KrK

Div2

  1. Nephren_Ruq_Insania

  2. Mahan_sh

  3. lsrothy

  4. ngfam

  5. georgerapeanu

  6. ZalBinHassan

  7. mtkaya

  8. Bodo

  9. szhouan

  10. fchirica

  • Vote: I like it
  • +405
  • Vote: I do not like it

Comments Comments (216)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Why this post is not on the main codeforces page? UDP: now it appears :P

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +36 Vote: I do not like it

I think you should update "other testers" soon to show your respect and thank to them.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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!

→ Reply
»
7 years ago, # |
  Vote: I like it +285 Vote: I do not like it

short sad story

→ Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

glhf

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it -26 Vote: I do not like it

You also like this sound of dislikes

→ Reply
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

High ratings to everybody! _______What a sad story..T_T

→ Reply
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I hope no large queue like the last educational round , I should't be wating 15 min+ to know whether my solution passes pretests .

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck!!!

→ Reply
»
7 years ago, # |
  Vote: I like it -31 Vote: I do not like it

is this contest rated ?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -17 Vote: I do not like it

Wish you can get high rating!

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for scoring ! This round is now enough special to remember it a long time :)

→ Reply
»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I have noticed that Arpa is mentioned/thanked in every blog post. Great job man.

→ Reply
»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

1750 points for problem C... Seemed like a challenging contest. Still wish for the best for everyone ;)

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

GL & HF

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish you can get more and more score.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wish you can get high rating!

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck and have fun every one :D

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of luck to all!!

→ Reply
»
7 years ago, # |
  Vote: I like it -26 Vote: I do not like it

Is it rated?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    It's asked You had better ask "Is it DATED?"

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 10   Vote: I like it +18 Vote: I do not like it

    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!

    }

    → Reply
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

WTH , NOt able to hack

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

lol

→ Reply
»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

No hacking, problems are too hard. Great contest...

→ Reply
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

As predicted, problem C is much more difficult than usually.

→ Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Go no rating...

→ Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Good problem set.

Happy_minus_Rating

→ Reply
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Is it Div-1 contest ?

→ Reply
»
7 years ago, # |
  Vote: I like it +28 Vote: I do not like it

The first A-B-C problems should be B-C-D.

→ Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

"High ratings to everybody!"

Problems are way harder than usual.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I would agree. The problems were way too difficult, especially B and C. Goodbye rating :(

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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)).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)].

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      How to calculate dp[position in permutation][1 (current permutation is already greater then a )][1(current permutation already less then b)] ???? If we somehow know the remaining count of each letter then this equal number of permutations of remaining letters, but we don't know the remaining count of each other, So how to calculate this??

      Thanks in advance!

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Consider a function f(stringx, 26 - numbers) which returns number of strings s constructed with characters which is given in the input, that s < x

    f(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

    → Reply
»
7 years ago, # |
  Vote: I like it -58 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretest 9 for C?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why my code for E is so slow? http://mirror.codeforces.com/contest/895/submission/32688252

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

what is the 8th pretest for b ? What is wrong in this ? https://ideone.com/dIQKbm

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You need to think about the case k = 0

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even I got wrong answer on 8th pretest. I just handled the special case for k = 0 and the pretests passed

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -52 Vote: I do not like it

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is solution of E based on sqrt decomposition?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what about non independence of values?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        What do you mean by non-independence? I am using linearity of expectation which does not require any such condition.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's expected value not variance.

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How did people solve C? Unable to access other submissions as of now.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +14 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Didn't know this fact, thanks)

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I figured as much. Could you give a more detailed description of your dp (states and transition)?

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it

    edit:wait nm this is too complicated lol

    If 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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did the exact same fuckin thing, still couldn't pass the 14th test case :(

      → Reply
»
7 years ago, # |
  Vote: I like it -41 Vote: I do not like it

this contest was awful! so sad!

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is an idea behind your DP approach?

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      What were your dp states might I ask?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        i'll give you my incomplete code https://ideone.com/BP05Of

        The idea is bitmask dp and knowing that choosing odd and even number of items from a collection of size n is just 2^n-1

        Please look for "solve", which is the entry point. I know my template is big :|

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hack for the first problem: 5 72 72 73 74 69 Ans: 66

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sad! I forgot that "sectors should be continuous" and submitted something useless :(

    → Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Somebody please explain div2 A ,as it had the worst explanation ever :/

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      He Could've wrote subsegment instead of sectors, too misleading

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There is no any case for this-> if one of sector is not selected ?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Problems were harder than usual ( specially A and B )

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

How to solve div 2 problem A and B?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In problem A you can use dp, or just calculate the minimum sum, by(pseudo) cyclic shift. More in my code: Click

    → Reply
»
7 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Very interesting tasks, I enjoy a lot of solving this problems !

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to solve C?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      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].

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it

        the time complexity is 2^19 * 100000 = 5e10. Can it fit the time limit? UPDATED: we can actually do in 2^19 * 70.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No. But you can notice that there are atmost 70 distinct numbers and reduce the complexity to 219·70.

          → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Please explain a it more about the dp formulation.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      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 do

      dpi, 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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Can you give some hints for the rest of the solution?

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you think my solution for B will pass time limit, I used map<int,int> instead of index compression?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Gah problem B apparently had so many edge cases, I kept getting stuck at the later tests

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What's the hack for B?

→ Reply
»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

PEOPLE ON CODEFORCES ARE GOOD AT SARCASM

→ Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Very hard contest but problems were very interesting.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the answer of B:- 5 3 1 1 2 3 4 5

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -23 Vote: I do not like it

any idea about this code bug(bug'S)???-problem B-


#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int maxn=1e5+7;
int a[maxn];//,r[maxn],l[maxn];
map<int,int>mp,cnt;
pair<int,int>b[maxn];
vector<pair<int,int> >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<vec.size();i++)vec[i].S+=vec[i-1].S,b[i]=vec[i];
	for(int i=0;i<vec.size();i++){
		int l=upper_bound(b,b+vec.size(),make_pair(b[i].F+k*x,0))-b-1;
		int r=upper_bound(b,b+vec.size(),make_pair(b[i].F+k*x,0))-b-1;
		ans+=(vec[r].S-(l-1?vec[l-1].S:0)+1)*vec[i].S;
		// cout<<r<<" "<<l<<" "<<cnt[a[i]]<<endl;
	}
	cout<<ans;
}
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    5 3 1\n 1 2 3 4 5 ans is 9.your code prints 31.

    → Reply
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

excellent problem set!

→ Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

div1.7-1.8

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone help explain why my solution to B times out on case 14? Thanks in advance!

32692235

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Afaik distance works in o(n) with std::set.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      oh I didn't realize that. That's unfortunate for me. Thanks for the help!

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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!

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got WA in pretest 8 because I was taking a subsequence (not consecutive values).

    → Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How does this contest fit into the pizza of life?

→ Reply
»
7 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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 :(

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Why don't announce this change? NBAH

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    That's a huge error, they have to address it.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Spent the whole contest in this problem ...

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it +12 Vote: I do not like it

    It should've been announced.Even I solved the earlier version until i reread it in the last few minutes.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      No! For unordered pair, (i, j) = (j, i), however, for ordered pairs, (i, j) != (j, i). (of course for distinct i, j's).

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B: Is this

Spoiler

complexity optimal?

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

hmm

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the idea of problem C?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :(

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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])

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 4   Vote: I like it +6 Vote: I do not like it

      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.

      → Reply
»
7 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Many people will get rating rise just for solving A :v

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    And that's another reason why this contest was awful.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, since I'll probably get a rating rise, I'm not gonna say this is awful :)

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +2 Vote: I do not like it

        I only solved A and my rating will go up but that was an awful contest.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I only solved A and my rating went down so this was an awful contest! :)

          → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    I think they wanted to justify their statement "High ratings to everybody!" :P

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A contest where the one can be proud of solving A & B

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Good Questions , i really enjoyed it..hope others too ;-)

→ Reply
»
7 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Bitmasks + some knowledge of Combinatorics is Div.2 C now? What's the world coming to?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem A in

Test case 50:

7

41 38 41 31 22 41 146 Output: 14

Is it correct? and how Explain please

Thanks :)

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But if i take

      series 1: 41 41 41 38 22

      series 2:146 31

      than the difference between series1 and series2 is 6

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you must take some numbers which are adjacent to each other, note that in this problem first and last numbers are adjacent too

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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")

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your code gives 120 . The expected answer is 0 .

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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".

    → Reply
»
7 years ago, # |
  Vote: I like it +46 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why my solution to B gets WA on case 21? 32682296 Thanks.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Input:

    5 3 0

    2 4 5 7 9

    Your answer: 4

    Correct answer: 5. (1, 1), (2, 2), (3, 3), (4, 4), (2, 3)

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why here UndefinedBehavior http://mirror.codeforces.com/contest/895/submission/32691004 ? but here everything is normal http://mirror.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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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);

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was thinking I was the only one who have read B many times until really understand what to do in this problem

    → Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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 :)

→ Reply
»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I have trained for 5 days and became specialist. I am looking forward to next contest

→ Reply
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

http://mirror.codeforces.com/contest/895/submission/32679304 is judged an error, but works in my compiler?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    the last line in your while loop should be if(i==n) i=0 not i==0

    → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

[update: ACCEPTED] Where is my wrong approach for problem B 32694817

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

delete2/32687180, coutinho/32687203, OutSpace/32688038, blindspot/32689194

LOL, 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

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone please suggest some cases(possibly small n so that I can debug) for my code (Problem C) http://mirror.codeforces.com/contest/895/submission/32711673

It is giving correct answer till n=1000 (in System cases) but I don't know why it is giving WA for n around 10e5

→ Reply
»
7 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

Can anyone tell me what's wrong with this code?

#include<bits/stdc++.h>
#include <algorithm>
using namespace std;

int main() {
	long long n;
	cin>>n;
	vector<long long> 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<<mindiff<<endl;
	return 0;
}

Running fine on local. :(

Test: #1, time: 0 ms., memory: 1844 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER Input

4 90 90 90 90

Output -664469436

Answer 0

Checker Log wrong answer 1st numbers differ — expected: '0', found: '-664469436'

→ Reply
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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://mirror.codeforces.com/contest/895/submission/32683171 submission after the contest : http://mirror.codeforces.com/contest/895/submission/32733925

PLEASE NBAH CHECK THIS PROBLEM !

THANKS.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I belive that you accessed invalid position on the array as you used

    for (int j=i; j<N+i; j++)

    N+i-1 will be outside of bounds since the array has only N positions and, by accessing not allocated memory you get an undefined behviour, which means that anything could happen, even geting AC even though it is wrong. That is actually a very common doubt for begginers, in his last post Mike talked about that. In his words:

    "Many Codeforces visitors are already tired of the questions of less experienced participants: "Why does my solution not work on some test on the Codeforces servers, if I locally launch it and it works correctly? You have the wrong compiler/servers!" In 99% of cases this is an example of undefined behavior in a program."

    → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

One of the most informative rounds ever. Thanks for your efforts!

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain Meet in the middle solution for C?

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What's the idea behind this submission 32677264 for problem C?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks so much! That was the error, apparently. So the -1 output was just a coincidence. :P

      → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Nephren_Ruq_Insania WOW!

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There's a small bug in the winners.The rank9 of div1 is the same as the rank1 of div2.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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??? :(

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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?

    → Reply