juckter's blog

By juckter, history, 5 months ago, In English,

Hi Codeforces!

We are happy to invite you to take part in Codeforces Round #561 (Div. 2). The contest will be held on May/17/2019 18:05 (Moscow time).

You will be given 6 problems and 2 hours to solve them. The round will be rated for all contestants with rating below 2100. As usual, participants from the first division are welcome to join out of competition.

The problems were written and prepared by Jefe and me. We owe a huge thanks to KAN for coordinating the round, to lewin and mohammedehab2002 for testing, and of course, to MikeMirzayanov for the great Codeforces and Polygon platforms.

Good luck and have fun!

UPD: A huge thanks to neal, dreamoon_love_AA, and antguz for help with additional testing.

UPD2: Thanks for participating! System tests have finished. Congratulations to our winners!

Div. 2

  1. thuytrang12a2

  2. LordAlbusDumbledore

  3. HaylayWilliams

  4. albertg

  5. Tianhen

Div. 1 + Div. 2:

  1. kefaa2

  2. Um_nik

  3. uwi

  4. thuytrang12a2

  5. HIR180

Editorial will be available soon.

UPD3: Editorial is up!

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

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

A lot of rounds recently! That is awesome!

»
5 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Hope I become CM after this round.

»
5 months ago, # |
  Vote: I like it -57 Vote: I do not like it

Hope it will be harder than before

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

i wish i could solve 2 or more problems this time :)

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

hope is a good thing..

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

Great week for Codeforces. Three Contests

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

Good Chance for newbies

»
5 months ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

Thank you, i hope it'll be a nice and challenging round.

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

I Hope the statement will be short and nice like the announcement .

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

Auto comment: topic has been updated by juckter (previous revision, new revision, compare).

»
5 months ago, # |
  Vote: I like it -26 Vote: I do not like it

round done by weeb... ... ..... .. ....... .... ... i am scared to try it!!

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

    How come you haven't been blocked yet? I intentionally commented about 10 bad comments and Codeforces already threatened me.

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

Oh Mexico Round SMT new

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

Is there any plan to announce the scoring distribution?

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

Thanks for div2. I want to be Master.

»
5 months ago, # |
  Vote: I like it -21 Vote: I do not like it

I know , U know, what if I told u...

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

I will try to do screencast with live commentary in English. If everything will go smoothly, you will be able to check it out on my YouTube channel some time after the round. Warning: English will be bad.

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

So what's the score for each problem?

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

where is score distribution

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

contest ends after 1st hour for the ones whose rating is below 1600. p.s 4th and 5th question are tough!!

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

    D (4th) is a nice problem, I spent too much time with little bugs and post my only solution at last 7 secs, WA at TC 5. Perhaps next time I'll able to solve my first D in Div 2 xD

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

I was glad that the problems seemed good to me, but actually from my extra registration I can't submit my code, and it just alerts "You have submitted exactly same code before", though I didn't succeed to submit anything... Lost the chance to climb up qwq

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

Good Contest.

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

TestCase 12 for C?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    If I'm not mistaken, test case #12 for C is the test where the answer is bigger than 2^31-1.

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

      I was handling it. Let me check again. :/

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

Yay! A chance to be master if system tests won't reject me :P

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

    congo...

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      Thx! Took me 3 years :D

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

        I m struggling in green and grey...:'(

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          It has been only 3 months you have been participating! See my rating graph and look how I was struggling in newbie. By the way, I was newbie when I changed to that handle ;)

          Just choose a good practice way and reaching to expert is really easy after having enough experience and algorithmic skills.

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

    You can't even imagine how much I understand you ;)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Well, you also had some time in the very top of CM so I think that means a real potential to be master in the next contests! Good luck!

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

Mathforces???????????????????????????????????

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

I need proof for E

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

    How to solve E?

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

      Necessary condition for the solution to exists is : Any two days must have a store in common.

      Seems like, it is the sufficient condition too.

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

      This is really intuitive solution, which I came up with in last five minutes: iff there's any element that are contained in all $$$m$$$ days, you can make the number extremely big prime so that you will get larger LCM. Is it true?

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

        seems to be false, sorry

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Counterexample = 2 3 5 with her buying (2,3) (3,5) (2,5) from stores.

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

          This is true (it's sufficient), but it is not necessary. Other cases can be valid as long as there is no pair of days on which Dora visits two disjoint sets of stores.

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

        An example that your argument is not holding for "only if"

        3 4  
        2 1 2  
        2 2 3  
        3 1 3 4  
        

        Valid sequence :
        7 5 7 2

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Check if for any $$$2$$$ different days sets of shops Dasha visited have nonempty intersection

      But I don't know how to prove that it's a sufficient condition

      Actually, I just submitted that because I saw how much people got it accepted, so it has to be something really stupid O_o

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

        I did the same thing... didn't believe it will actually work...

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +62 Vote: I do not like it

    Let's take $$$m$$$ different primes, one for each query. Start with array of 1, and then multiply all the numbers in one query by the prime of this query. In each query LCM of our numbers will be product of all primes and LCM of all other numbers will lack prime of this query.

    Of course, this is true when all queries are pairwise intersecting.

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

    If there exist two disjoint sets, answer is obviously no. If every pair has common element we can do the following: First set all numbers to one. Lets consider one set: a1,a2...aS. We may multiplay all numbers a1,a2...aS by arbitrary large prime number. It will guarantee us that this set is correct. On the other hand, we dont make our situation worse, for other sets(days), i think it is clear why ( from definition of LCM).

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

    If on any day the set of stores visited by Dora is a subset of the set of stores visited by Swiper on any other day then it is impossible, else it is possible.

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

ALL THE PROBLEMS WERE BEAUTIFUL EXCEPT FOR C

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

D is hard to implement.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Well, I didn't know my solution is $$$O(k^3logm)$$$ for each query before submitting it. Time to pray for not getting TLE :P

    What I did was choosing the numbers greedily (the maximum I can put).

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

    And I started with D only, took me 1 hr 40 mins, RIP rating.

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

Constructforces :v

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

For question C what is going wrong with this approach? https://codeforces.com/contest/1166/submission/54311053 thanks.

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

Sad story!Next time,i will solve more problem

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

Is it just me or was problem A description confusing? I still don't get how three chatty students paired together are considered three chatty pairs, while two students together are considered one chatty pair

how does this generalise for n > 3 ?

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

how to solve E?

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

    The answer is possible if and only if there exists no pair of days on which Dora visits two disjoint sets of stores.

    The proof that no other cases work is trivial; the proof that all of these cases do is less so.

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

      Proof by construction -> for each set have unique prime and multiply all values visited on that day by the prime. Values start with 1 on day 1. Because each set contains its own prime and all primes of others, LCM in it will be maximum possible. On the other hand, if there is some value between stores that this set did not touch and its value is maximum possible, then it must contain all primes (I mean, number stored in it is divided by all those primes) and so each set contains it, contradiction, we said it was outside some set.

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

Problem C. Testcase:

4

1 1 2 2

What is the answer?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    All of the potential values are guaranteed to be distinct, so this is an invalid case.

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

      It never said they are distinct. "unordered pairs formed by two different elements", does not specify that, are two numbers distinct if they have the same value or different index? I went for the solution that counts such case just and it got accepted.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        The second line contains n pairwise distinct integers...

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

          Thanks, I see. It should be part of problem, not "Input" part then. I think, input is for constraints on sizes, not number properties.

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

Thanks, Codeforces for another good round! Although, unfortunately, it will take a long time until the next round...

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

IMHO, problems D and E should have been valued equally. I didn't solve E, but I can see in the comments that there is a simple idea behind the solution (and more people solved it than D). On the other hand, D was a rather implementation-intense problem, it took 40 minutes to code the solution :)

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

    I came up with Idea for E but did not submit it, it looked too easy. Seems I had right solution tho. I'd not say the idea is simple, but implementation really is.

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

for problem D isn't is hold? Any number between lower bound and upper bound form by current state a solution can be find ,i just did binary search by this but failed

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    My solution to D relied on the fact that through messy casework, we can prove that two numbers x and y with |x| <= |y| form a valid pair if and only if |y| <= 2|x|. I thus created a vector containing the absolute values of all the datapoints, sorted this vector, and then did two pointers.

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

    just found it was small mistake on bound ,modify it then got AC

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

thx 4 fast testing)

»
5 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

I read comments, many users have solved problem D with greedy algorithm. My solution is constructive, works in O(k^2) per query. I missed couple of minutes to submit:(((, but I believe I have a proof for my solution. Has anyone else solved it with a not greedy algorithm?

UPD: It turns out that my solution was wrong :( sometimes it doesn't find any solution), which is a pity as my solution was quite beautiful.

»
5 months ago, # |
  Vote: I like it -9 Vote: I do not like it

What is the point on setting too much math problems? >:(

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

    Do you think that implementing boring algorithms is better than nice, math problems with short and clean code?

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

      Yes. Precisely building your answer through hard thinking and combining algorithms is much prettier than just solving an inequation on paper and then passing it to boring code. This is not IMO but ICPC

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

Did anyone else solve E by constructing a DAG based on subsets, and checking for existance of topoloical order in that graph?

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

    This argument is valid, but I think you will need additional observations for dealing with memory issues (to make sure not too many subsets are being considered) It is enough to ensure that there are no conflicts — i.e, there are no set A and B of given sets, such that $$$A \subset B^c$$$. What you said is equivalent to this, but using some unnecessary subsets.

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

    ba iharke Paron Pashinyan

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

My first contest after a loooong time! Hello again Codeforces! ^^

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

Can someone tell me why I got WA on tc 20 for C 54289806

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

    Sorry, i cant understand java code completely, but did you count pairs {0,0}? It seems like not

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

      All numbers are pairwise distinct. {0, 0} won't appear.

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

    I have same approach and got WA on TC 20 too. I thought getting absolute values before sorting might cause a problem. Now testing with random small cases but haven't met a wrong answer. Only differences with not taking absolute values happens like that: For -3 3 our range is (0,6), but it should be (-6, 0). I'm not sure this might cause an error.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    Collections.binarySearch() is of no use when finding index if there is repetitions.

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

      That's it! I just put a condition for next item and it got accepted, and I met that same problem in another contest too. Hope next time I'll remember it

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

When both you and the problem setter do the math wrong...

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

    How come in problem C for the test case 3:

    2
    0 1
    

    The answer is 1? Shouldn't the answer be 0?

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

      The answer is indeed 0.

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

        Never mind, it's my bad, my code is throwing an error.

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

Did you guys know that a = b.flip() on bitsets changes value of b??? I guess I'm lucky to catch that bug while participating out-of-contest :D

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

I recommend you two pointers method for problem C. In my opinion so easier way than binary searches.

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

Auto comment: topic has been updated by juckter (previous revision, new revision, compare).

»
5 months ago, # |
  Vote: I like it -16 Vote: I do not like it

I cheated this contest and i am sorry for my behaviour, but i am still in the official list of participants and i think that i don't deserve to be in the official standings.

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

It’s a pity that I didn't become winner of div.2 qaq~

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

Auto comment: topic has been updated by juckter (previous revision, new revision, compare).

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

I kinda turned into genuis the last couple of rounds, it seems that the strategy solve C first seems to work.

»
5 months ago, # |
Rev. 2   Vote: I like it +25 Vote: I do not like it

I suggest from now on everyone who cheats to get last place in the contest as punishment, like i did and got -181.

»
5 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Codeforces must fix at least 1 contest every week. If possible 2-3 would be great!

»
5 months ago, # |
Rev. 3   Vote: I like it -17 Vote: I do not like it

The second test case for D problem is wrong as it is clearly mentioned in the question that ri>=1

juckter

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

    how is it wrong? The sequence only has one number so $$$r_i$$$ is not relevant.

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

Un Poco Loco.

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

Can someone please tell me why my codeis giving runtime error the only thing i did was to replace the first scanf for no. of test cases to cin

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You shouldn't mix scanf/printf with cin/cout if you're using ios_base::sync_with_stdio(false); , removing that line would fix it. Also, this blog post is for round #561, not #560.

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

Me during the contest:

(for those who don't know, they are pinyin for the Chinese words "yes" and "no" and I speak Chinese as a native language)