Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Ari's blog

By Ari, history, 2 years ago, In English

Thank you for participating! We hope you liked our problems.

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +151
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +169 Vote: I do not like it

Everything was so fast :
System testing — Done
Editorials — Done
Rating Update — Done
And its just one hour after the contest.
Other CP sites should learn from this.

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

Good mathforces :)

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

    Can someone please explain what does this term "mathforces" really mean? I have seen it being used a lot in various contexts, seems like some inside joke or reference.

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

      Well, it is when the major part of the problem is solving an underlying math problem (incl. formula transformations, applying some theorems and common facts from algebra) rather than finding out and coding typical CP algorithms (DP, graph theory etc.). Some people argue that such problems give an unfair advantage to those who are participating in math competitions professionally. But it is well known that gaining good math skills is a part of one's development as a CP professional.

      ...or maybe I was getting it wrong all this time. Then please correct me :)

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

    There's no so much math I think. Anyway, very interesting round!

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

      Literally every task except maybe F requires solving a math formula before implementing the solution. In some, the math solution is relatively easy, say in A or B, in others its really hard to do without more advanced knowledge in maths, or maybe just having a mathematical mindset to solve the problems.

»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

mathforces back at it again :( (thanos snapped his fingers)(my rating doesn't feel so good right now)

»
2 years ago, # |
  Vote: I like it +26 Vote: I do not like it

I spent about half an hour thinking about details about Problem C, divided it into 3 cases (by the relationship between x, y, -x and 0), only to find that it can be solved in such a simple code:

for(int i = 1; i <= n; i++)
    ans += upper_bound(a + i, a + n + 1, 2 * a[i]) - (a + i) - 1;

Can you imagine how astonished I was ?

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

Good contest, loved the problems! Spent quite a lot of time on Problem C just to find out the error lied in one edge case of point at 0 :facepalm:

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

    Take x=0, y=1. Then, |x|=0, |y|=1, |x+y|=1, and |x-y|=1. Thus, old range is [0,1] while new range is [1,1] which does not cover the entire old range. It can be seen by symmetry that the same applies when x=1, y=0.

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

    The new range will not be [0, 1] but it will be [1, 1] which will not cover all the points. Moreover for the case of [0, X] the new range will be [X, X] so those points will not add to our result.

»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I actually liked this one — the problems were mainly idea-wise and my solutions could be extremely clean and elegant even compared to my usual doing. ;)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Greetings, can someone help me figure out what's wrong with my submission to problem C ? My solution is just like the tutorial's, but I couldn't pass TestCase 20. https://codeforces.com/contest/1166/submission/54322422

Many thanks in advance ^^

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it
    ll p = upper_bound(all(v), (ll) 2 * v[i]) - v.begin();
    

    not

    ll p = lower_bound(all(v), (ll) 2 * v[i]) - v.begin();
    
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I see.. I thought my if statement was enough to handle the issue, oh well many thanks ^^

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it -13 Vote: I do not like it

    May you can try this case:

    3

    1 2 -2

    The answer is 3.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Aha, my old solution was giving me 2 instead, I understand now. Thanks a lot ^^

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved problem A with sorting, so is it wrong solution?

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

    I don't think it's wrong but you kind of did more work than was required. Still, the solution is completely fine.

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

    @gkfkagkfka12 Please elaborate your approach for Problem1 after sorting? Thanks in advance!!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do people generally frame the questions? I am very curious to know that.

»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Problem E is great in constructive algorithms.But something bad is if you cannot create a valid solution,you can also get AC.

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

    Can a solution of E be like this ? Set the a[i] for all the stores that are common in all m days to some fixed value say 10. And all other values to 1. So , each day the lcm of visited stores is 10 and of unvisited is 1.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B, what do they mean by "filling the grid by diagonals" ?

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    It means that $$$a[0][0]=a$$$, $$$a[0][1]=a[1][0]=e$$$ $$$a[0][2]=a[1][1]=a[2][0]=i$$$ .. and so on formally if $$$i+j=n$$$ then $$$a[i][j]= \text{a vowel}$$$ Observe that this way the contions of the problem are satisfied

  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why can this satisfy the conditions?Can you tell me

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, i have a question. How can we get x <= 2y from |x+y| >= y? i got -x <= 2y. Please someone help me to understand that.

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    No we obtained results from |x-y| not |x+y| coz |x+y|>=x+y will always be true for positive x ........................................... |x-y| <= x ...... x-y <= x ..... y-x >= x ...... 2x <= y thus result

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

      Can you please explain how can we use 2 pointers to solve problem C.

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

      |x-y|<=x

      x-y<=x & x-y>=-x

      y>=0 & y<=2x

      Here we are able to get only y<=2x, But in editorial it is written that we also obtain x<=2y. How do we obtain this equation. Please clarify

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        y <= 2x is for the case when x <= y: then we have |x − y| <= x <= y <= x + y

        x can also be greater then y. then we have |x − y| <= y <= x <= x + y

        and here comes x − y <= y --> x <= 2y

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for Problem E, I wanted to prove(or disprove) it. Then I found

1

2,3

4,5,6.

m = 4, (124,136,456,235) I set each a_i a prime, then I realized 2>6, 6>2...which I'm stuck, (disprove?)

Thanks to editorial.. I didn't think about set PRODUCT of prime.

next time, I should take a submission first, instead of proving myself. :(

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone describe how the stores would be assigned integers in problem E ?
And can the time complexity be further improved?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I find the solutions? (Code)

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

    Go to standings, kefaa2 and Um_nik have easy to read solutions to the problems.

»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Is kefaa2 alt of Um_Nik?

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

[PROBLEM E]

Construction in problem E is so GREAT! I wonder how you can create such a nice construction like that. Can you share your MOTIVATION? Besides, problem would be a deserved E-class if it required constructing array a.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting WA on TC 12 in Problem C with the same logic backwards. https://codeforces.com/contest/1166/submission/54346570

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

    I changed all datatypes to long long and it got accepted. Thanks!

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

in D why cant we use binary search to find the value of r

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

Can someone please provide a simpler explanation to Problem D. The editorial seems to be a bit difficult for me.

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Problem D is basically about the series: 1 1 2 4 8 16 32 64 128 ............ U have to turn a into b using this series. Otherwise return -1

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If a am doing for(int i=1; i<=m; i++) { for(int j=i+1; j<=m; j++) { if((bs[i] & bs[j]) == 0) { cout<<"impossible"<<endl; return 0; } } } it gives correct answer but when I do for(int i=2; i<=m; i++) { if((bs[1] & bs[i]) == 0) { cout<<"impossible"<<endl; return 0; } }

it gives wrong answer. Why?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain problem D I did not understand the editorial

»
2 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

In problem D, why are we choosing r(i) = k + d(n-1-i) ? What is the intuition behind doing this, and what exactly are we trying to show?

Also, what does k denote here?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1166/submission/54423195 I am not able to get what wrong with my code, anyone has any idea pls share with me

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please elaborate editorial of problem A. I didn't get [cnta/2] part. Thanks In advance!!

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

    It's basically for counting floor and ceil of [total no. of students]/2 (as it is the most evenly possible distribution) and further dividing it by 2 to get total no. of pairs!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone elaborate on problem D??...I am not able to understand after writing r as d0d1...

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problem E, СЛАВЯНЕ!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C can also be done using simple queues in O(n).

https://codeforces.com/contest/1166/submission/56070478

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I read the editorial completely .There are two methods described — One writing b in a particular form : 2^(n−2)(a+k)+r(which i think is not easy to guess during contest) and the other Greedy Method . Author has not told completely to use greedy method and i tried to figure it out .After unsuccessful attempt i saw one of the submissions (http://codeforces.com/contest/1166/submission/56675841) . In this submission , first value of n is found and after that for n-2 times b is divided and changed to new value. There is another variable 'p' , which tells if we need to add 1 before dividing by 2 (basically it is alternatively) .

I want to know the thought process or how to come up with the solution that provided in that submission .Note that in other submissions also similar approach it taken .

I am new to competitive programming and i want to improve , hence it is necessary for me to solve difficult problems.

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

Can a solution of E be like this ? Set the a[i] for all the stores that are common in all m days to some fixed value say 10. And all other values to 1. So , each day the lcm of visited stores is 10 and of unvisited is 1.

»
18 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Problem E is a straightforward copypaste from the first Iranian Team Selection Test for International Mathematical Olympiad 2018. I don't know if this was intentional, but I thought it would be worth noting. https://artofproblemsolving.com/community/c639324_2018_iran_team_selection_test

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain this part of the editorial for question D?

Alternatively, after getting the formula, we can iterate on i from 2 to k and greedily choose the values of ri to be as large as we can without exceeding b. This can be easily shown to work using that the coefficients are consecutive powers of two.

I'm able to figure out the part, to check if the sequence exists or not. Also in the first solution that has been suggested, Write b as 2n−2(a+k)+r where r<2n−2, what is k here?