isaf27's blog

By isaf27, history, 3 weeks ago, translation, In English

Hi all!

This weekend, at Nov/14/2021 09:05 (Moscow time) we will hold Codeforces Round #755 (Div. 1, based on Technocup 2022 Elimination Round 2) and Codeforces Round #755 (Div. 2, based on Technocup 2022 Elimination Round 2). They are based on problems of Technocup 2022 Elimination Round 2 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup website and take part in the Elimination Round.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

Have fun!

The scoring distribution:

  • Technocup: 500 — 500 — 1000 — 1500 — 2000 — 2500 — 3250
  • Div1: 500 — 1000 — 1500 — 2000 — 2750 — 3750
  • Div2: 500 — 500 — 1000 — 1500 — 2000 — 2500

The round is over. Congratulations to the winners:

Technocup

  1. Artyom123
  2. turmax
  3. Kirill22
  4. expwmh
  5. Kapt

Div1

  1. ko_osaga
  2. maroonrk
  3. xay5421
  4. jiangly
  5. uwi

Div2

  1. 1443356159
  2. int65536
  3. strongerthanspeed
  4. DSair
  5. nunu03

Editorial

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

»
3 weeks ago, # |
  Vote: I like it +42 Vote: I do not like it

Note the unusual timings

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My first contest with green color , I hope I will do well, good luck every one .

»
3 weeks ago, # |
Rev. 2   Vote: I like it -35 Vote: I do not like it

hope I can get rid of grey soon...

»
3 weeks ago, # |
  Vote: I like it -36 Vote: I do not like it

I just hope I Got a Good Name.

»
3 weeks ago, # |
  Vote: I like it -44 Vote: I do not like it

11.35 am I would love to give the round if I woke up by thenಥ_ಥ who keeps round so early in morning that too on Sunday ಥ_ಥ ಥ_ಥ

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "who keeps round so early in morning that too on Sunday"

    A lot of people around the world usually have to wake up wayyyy earlier than 11:35am for a contest. It is what it is.

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

      I do understand that its just my pov not meant to offend anyone.(^◡^ )

»
3 weeks ago, # |
  Vote: I like it -89 Vote: I do not like it

We have to postpone contest a bit. No way I can wake up that early

»
3 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

Which approach is better for practicing problems in problemset: topic-wise or difficulty-wise?

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

    Difficuty wise , because when you are filtering questions according to a topic then you would already have an idea before even looking at the problem that this question can be solved using this perticular logic and this is not good, why i am saying that because when you are giving a contest you are unaware of the approach which is being used thats why it is better to sort according to difficlty then solve.

»
3 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

Sleep vs contest. Ape choose sleep.

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

It overlaps with Grand Prix of EDG :'(

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

The contest is right after Google kick start, look forward to it. (Finally a good time for NA competitors

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wish I had read your comment sooner. I didn't realize the time was in 24 hr format :_(

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

google kick start (or) codeforces div2

»
3 weeks ago, # |
  Vote: I like it -62 Vote: I do not like it

no contestants, the time is unusual and bad

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Dare to join this contest just after Google Kickstart Round-H;)

»
3 weeks ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Google kick stat round H plus codeforces round 755 makes me 5 hours of marathon coding competition.

UPD: It's the third time I become candidate master.

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Overlaps with AHC006. If you fully participate CFR755, only 2h40m will remained for AHC006.

»
3 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

Scoring distribution still not announced.

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

very few registrations this time.

»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Speedforces

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How can someone hack a problem even after I locked it ?

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

    That's what locking is for

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

    After locking, you cannot submit again and can hack other participant's solutions. If not locked, you can submit again but cannot hack other participant's solutions.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Thanks to this comment I hacked 7 people.

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

Sorry for asking this, but I accidentally submitted a WA after an AC. So the AC solution done before will be counted for results right? Or is last submission for that problem considered regardless?

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

    Your AC solution counts, check standings :)

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

What is the hack for C?

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Div1B/2D is a really nice problem, bricked for a really long time trying to figure out how to solve the problem in just 1 pass of binary search, but the observation needed to solve it is cool af.

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

    How do you solve it in one pass?

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

      Difference between $$$query(1, k) - query(1, k-1)$$$ is equal to the $$$k-j+1$$$.

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

        Thanks :) Couldn't figure out during contest but the idea is actually very beautiful nonetheless.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it +24 Vote: I do not like it

      Binary search on ranges of the form $$$[1, x]$$$ to find $$$k$$$ (smallest index with same number of inversions as range [1, n]).

      Now lets realize that since all elements in $$$[i, j - 1]$$$ are smaller than those in $$$[j, k]$$$, the number of inversions is exactly $$$\frac{y \cdot (y - 1)}{2} + \frac{z \cdot (z - 1)}{2}$$$ where $$$y = (j - i)$$$ and $$$z = k - j + 1$$$.

      Now if we query the range $$$[1, k - 1]$$$, the number of inversions is $$$\frac{y \cdot (y - 1)}{2} + \frac{(z - 1) \cdot (z - 2)}{2}$$$, or exactly $$$z - 1$$$ less than the previous value.

      So we now have $$$z$$$ and can get $$$j$$$ from it.

      We also have the total, so we can just binary search to find $$$y$$$ that satisfies $$$\frac{y \cdot (y - 1)}{2} = total - \frac{z \cdot (z - 1)}{2}$$$. So we can also get $$$i$$$.

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

        Also the part of binary searching y can be eliminated using the main observation by querying [1, j-1] and [1, j-2] and subtracting the second from the first to know length of [i, j-1].

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

        If you binary search two times then won't the total number of queries be $$$2 \log_2(N) \approx 60$$$ ?

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

          The second binary search in his comment is to solve an equation not to query.

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

          The second binary search is finding the largest $$$y$$$ such that $$$y \cdot (y - 1) \leq total - \frac{z \cdot (z - 1)}{2}$$$. Just a local calculation, no queries or anything.

          You can just do $$$\sqrt{total - \frac{z \cdot (z - 1)}$$$ and check close by values if you aren't paranoid that will somehow make you FST lol.

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Fragile pretests on C lol. Hacked 8 submissions

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

    ape hack . ape happy

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

    I hacked 3 using following test:

    1

    3

    4 4 4

    3 3 3

    Anc I jumped from rk~150 to rk~50 lol

    Is that weakppforces?

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

The pretests in C were reasonably weak. I hacked my way from ~1000 rank to ~350 (And so did a lot of other people).

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

hackfor C es!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is div-2 D some sort of ternary search?

»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

ko_osaga did it again!

Where is E from?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +74 Vote: I do not like it

    Hi, it's NEERC 2015 Northern Subregional K. It is not very equivalent, but the main observation for that problem can be applied directly. Shoutout to ainta for recommending me this problem.

    main observation for that problem
  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Also, at least one problem in CF and a recent WF problem related to "distance to line", the only difference is to handle case when distance to segment is to one of two ends, it is easy by sweeping and two pointers.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi,

Even though I probably didn't have the right algorithm on the E, the statement was a bit ambiguous on the issue of size 1 segments and other details (e.g. can we increase the ends without increasing the only values adjacent in the subsegment). I rather liked this exercise even if my performance on this competition does not exemplify me :)

»
3 weeks ago, # |
  Vote: I like it +62 Vote: I do not like it

Problem C and D are easy to come up with . But really hard to implement and debug ...

  • »
    »
    3 weeks ago, # ^ |
    Rev. 4   Vote: I like it +38 Vote: I do not like it

    Agreed, on problem C it took me:

    • 5 mins to get rough idea
    • 10-15 mins to work out all technical details
    • 40-45 mins to implement and debug till it passed samples
    • 10 mins to write brute and stress test when I got WA2.

    The basic idea of parity sums and prefix not becoming negative is fairly standard. I'm pretty sure there was Div2 problem a while ago that required exactly those two observations.

    Edit: Apparently Div1C is extremely easy to code if you use k-th order statistics. See this submission — 135379742.

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

      Thanks , I know few about pd_ds. I think I need to learn more about it .

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please share any hints about problem div1 C, thank you very much.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hint: you can perform the operations from left to right , and find out when the array is possible to clear . Use some data structure to maintain it !

»
3 weeks ago, # |
Rev. 2   Vote: I like it +272 Vote: I do not like it

I'm interested in what happened to antontrygubO_o

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

problem C hack when it's almost time :D

My rank has dropped like crazy

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Donno where my code was failing in DIV 2 problem B ,C was easier though

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Today I did my first hack on Codeforces. Felt a little too good to be evil, lol.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain the logic behind solution of problem B??

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      (n*m+2)/3

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        take 3 squares at a time. color the middle. if extra box(either 1 or 2) color 1

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

      First thing to figure out is that when you make rectangles of dimension 3*1 you need minimum possible colourings. So, we divide the base rectangle into as any 3*1 rectangles possible and we will be left with (n%3)*(m%3) sized rectangle, now, the possible rectangles will be 2*2, 2*1 and 1*1 . First 2 cases will have half tiles coloured and the last case is prohibited so what we do here is we spare 4 tiles in one line and divide the rest all in rectangles of size 3. The remaining 4 will have 2 tiles coloured.

      If I was difficult to understand. Here is my solution- 135359905

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

Cries to death

»
3 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Ready to get FSTd Solution to C cannot be so simple

»
3 weeks ago, # |
  Vote: I like it +116 Vote: I do not like it

I didn't manage to remove cheaters in previous rounds yet. I will do it soon, but as a result, it is likely outcome that someone will change their division of participation in round 755. Regardless of the new division (after removing the cheaters), your participation will be rated in the exact division that you actually participated in round 755. That is, even if after removing the cheaters you change the division, then round 755 will remain rated for you.

»
3 weeks ago, # |
Rev. 2   Vote: I like it -24 Vote: I do not like it

if(technocup){ pretest = weak as hell; }

next technocup arrives hacker be like "Yeah boiii";-)

»
3 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

I am not upset that pretests of C were weak ,I am upset that I didn't attempt to hack

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have the same feeling, I found the hack very soon but I was so scared to try because it was my first time trying to hack, by the time by I gathered the courage 3 hackable solutions were hacked in my room so I had only 1 solution to hack.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      Yeah I also would have felt little nervous as I never hacked before ( It always feels nervy in an unknown territory )

»
3 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

I wonder if Div2.C(Div1.A)'spretest is SO WEAK Because I add abs() and go through pretest as well

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

am disappointed because weak test cases in problem C

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello All, just needed your attention here. I submitted C once and it showed me an accepted verdict again after a few minutes I again submitted with a slight different approach and it showed a passed verdict.Just when the contest got over I saw a skipped Verdict and queued verdict. May I know why it is happening so.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is fact what solve with complexity O(n**2) getting AC in Div1C OK? 135376136

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

    Hacked. It seems that the test cases are too weak.

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

weakpretest :(

»
3 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

I never wanted be hacked more than now

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
3 weeks ago, # |
Rev. 3   Vote: I like it -83 Vote: I do not like it
some downvoted words
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    A is difficult only if you failed your algebra class in school

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it +7 Vote: I do not like it

      My point is not on A.I decided to solve it after D.

      now found it the worst decision ever.

      More,only 5000/9000 participants submitted A.It's not a good thing for cf.

»
3 weeks ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

A. Math, Was quite tough to me
B. It could just as well be A
C. It can be solved with one-liner, why is it C and why there are so many hacks and fst?
D. Nice problem, enjoyed solving it

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A. I still enjoy solving problems related to algebra, interesting for me.

    B. Problem was meh, div 3 type.

    C. Really bad C. This problem is meant for div 3A. How did this even...

    D. This problem looks interesting

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem B, I realized we need to take as much as 1*3 as possible so my solution was based on that. I see some solutions like cout << (n*m+2)/3 << '\n'; how the solution got reduced to that !?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi ! In fact the answer is ceil(n*m/3), and with few attempts, you can realise that this is equal to floor(n*m + 2/3).

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

    In total we have $$$n * m$$$ little squares. You mentioned right, that we need to take as much $$$1 * 3$$$ rectangle pieces as we can. Now $$$(n * m + 2) / 3$$$ is a way to find how much $$$1 * 3$$$ pieces we will have plus check if there is something left, so basically it is [ $$$(n * m) / 3$$$ + remainder ], where remainder is one if $$$n * m$$$ is not divisible by 3. That means that we are left with $$$1*2$$$ or $$$1*1$$$ rectangle and in both cases we will need to paint exactly $$$1$$$ more sell with blue

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

Thank this contest let me become a candidate master.

I think problems are good.

But the pretest of C was terrible and there were so many hacks.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Me Newbie here, how to interpret Scoring Distributions?

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

I think D1D is just this problem with much harder implementation.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

So weak pretests on problem C !!!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Huge difference between no of accepted solution div2 C and D. There should have another problem in middle difficulty.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Here are the video Solutions to the first 4 problems of Div-2 in Case you are interested.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally turned green..WohooooOOo

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

    Finally turned green after being specialist and expert. Wooohoooo

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

Why such a huge gap in the difficulties of (ABC) and D in div2..A newbie could also solve upto C and D was very tough for a specialist(maybe for an expert too)

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maybe for some cm too

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

    D was pretty much as always
    The gap is because C was easier than it should have been. In general C is intended for cyans

»
3 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

how come no editorials?

»
3 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

This has to be the most unbalanced div 2 round till date

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Weak pretests for problem C :(

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

waiting for editorial.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution

Can anyone please tell me why this is wrong ?

It passed the pretest but now it is showing WA

I cannot even understand the test case it failed

1
1
2
1

like why it is failing why its o/p is NO it should be YES isn't? Am i missing anything or my understanding of the problem is flawed?

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

    you lack of consideration of b[i] < a[i]

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Damn it! this little observation gave me a negative rating

      Thanks for replying and helping me

      PS: Just an hour ago I saw you had 2 upvotes on the above reply and now I see 0 I don't know why people just downvote comments that may help others. :(

»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Could anyone tell me what's wrong with my C code? I can not find out and I am wondering whether it is necessary to sort. 135383484

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try this TC and you'll realize why is it not working
    1
    2
    1 2
    2 1

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much~ I know what's wrong with it now

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Since editorial is late and for some reason no one is discussing solutions, could someone tell me what is the idea on how to optimize D2E(D1C) from O(n^2)?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I’ve always thought that rounds based on technocup are difficult and need a good knowledge of advanced algorithms, but i think this contest is a bit different , problems A,B,C are the same as a div3

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Any hints on how to solve B of div 2 :)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Think of rectangles of rectangles of area 3

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if you have block consists of 3 cells so you can only do this : Red Blue Red -> RBR so think about using MOD 3 to know how many cells you will have at the end.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

as a Python user, this contest was pretty disappointing. The tutorial Div1D and E solutions have essentially no hope of running in the given time limits in Python because of the absurdly large constraint allotments.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretty good contest, I like this type of style, only on suggestion, the gap between some problems might be a little too big.

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

EASY contest

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

Congratulations to the winners