FelixMP's blog

By FelixMP, history, 3 years ago, In English

Hello!

It is a pleasure to invite you to CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!)! The round will take place on Mar/24/2022 17:35 (Moscow time). The round will be rated for all participants. The problems of the round were authored by FelixMP, and they were prepared by FelixMP and xpov1LL.

I would like to thank the following people:

There will be 9 problems in the round, with score distribution $$$500 - 1000 - 1500 - 2000 - 2500 - 3000 - 3250 - 3750 - 4500$$$. Hope you have fun!

UPDATE: Editorial.

Here is information from our partners:

Hello, Codeforces!

We, the TON Foundation team, are pleased to support the CodeTON round and invite you to the TON Smart Challenge 1 competition, which will be held on our platform.

The Open Network (TON) is a fully decentralized blockchain created by the Telegram team for a mass audience.

The TON protocol was designed by Nikolai Durov — who is a two-time ICPC world champion, a three-time IMO gold medalist, a multiple IOI medalist, and a co-founder of Telegram — and other winners of international competitions. Now TON is being developed by a community of independent developers and teams.

The winners of CodeTON Round 1 will receive valuable prizes.

The first 1,000 participants will receive prizes in TON cryptocurrency:

  • 1st place: 1,000 TON
  • 2–3 places: 600 TON each
  • 4–10 places: 100 TON each
  • 11–100 places: 15 TON each
  • 101–1,000 places: 8 TON each

Also, the top 15 participants of CodeTON Round 1 will receive branded hoodies.

In addition, a separate TON Smart Challenge 1 contest will start on our platform on March 28. We invite you to join this competition as well.

You can read more about this competition here:

TON Smart Challenge 1 →

We believe that the problems of optimizing the efficiency of smart contract code execution on the TON blockchain may be of interest to participants in algorithmic competitions. The development of smart contracts is a case where the experience of optimization earns money by definition because a network fee is paid for each operation on the blockchain.

We wish you good luck at CodeTON Round 1 and hope to see you among the TON Smart Challenge participants!

UPD: If you have got into prizes or just want to join the TON, then register a wallet, follow one of these links: https://tonkeeper.com/ or https://wallet.ton.org/

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +143 Vote: I do not like it

It seems that a TON of interesting tasks are waiting for us

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

Another cryptocurrency contest

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

Good luck everyone!!!!!

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

25 USD for the first place? 37 cents for the 11th place? What a joke

Edit: forgive my ignorance, there's two currencies both listed as TON, if it's the other one, then the prizes are quite decent

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

Why is the prize distribution so weird :/ For example, 1000th and 101st places are totally different levels of skills, I believe it would be better if they were distributed like global round points.

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

omg Catalan round

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

There are two different competitions being announced. I didn't notice that at first.

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

Organized by spanish olympiad problem setters, willing to meet you in the final next week

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

How many problems will there be in the round? Is the score distribution available?

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

    Still no information, sad…

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

      you guys preparing 16+ hours for contest by score distribution?

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

        Well by that you will know some difference between problems and like now you see that you have only 2 hours for 9 problems, which is kinda weird

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

All the best to everyone

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

Wow, crypto rewards

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

Problem A: write a protocol, Problem B: write a protocol .... last problem: write a superhard protocol

»
3 years ago, # |
  Vote: I like it -38 Vote: I do not like it

Please don't make this as the recent Codeforces Rounds where everyone from newbie to expert can easily do ABC and D can be done by only CM+.
From the past few contests, the difficulty gap between C and D is very high compared to any other problems. I request the setters of the upcoming contests to make the rounds balanced for everyone. Hoping it to be a good contest. >︿<

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

This might be a stupid question, but is Codeforces moving to 7:35 as the standard competition start time? I checked the upcoming contests; all of them are starting at 7:35

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

    If my googling serves me correctly, Russia does not observe daylight savings time (while the USA does), so CF contest times shift for Americans when DST begins and ends.

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

      Oh, that makes a lot of sense! Thanks!

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

What about system of contest ?! Held of Regular codeforces Round Or ICPC Rules Also, what about number of problems :(

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

Just curious, I want to ask how the bonus is distributed, is the winning user providing the cryptocurrency wallet address, and then you send the currency to the wallet?

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

How To become Specialist in this round ?? Wrong Answers only

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

9 problems contest o_O

»
3 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Is tourist participating?

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

Do you think tourist is gonna make record by achieving >= 4000 in this contest if yes then upvote, if no then don't vote

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

    Ninja technique of increasing upvotes

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

    Yes : No :

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

    Tourist got TLE'ed

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

How much is 1000 TON?

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

9 problems for 2 hours, what could possibly go wrong..

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

    A lot of those problems will probably be speedran by top ppl.

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

Good luck everyone!!!!!

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

I know I won't win anything but I hope I keep my color XD

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

Good luck guys, it'll be fun.

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

The Spanish Olympiad last year was really interesting, so I'm excited for this round!

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

Probably the shittiest round of my life

»
3 years ago, # |
  Vote: I like it -21 Vote: I do not like it

I hate Problem B (:

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

i found B harder than C :(
but I liked the challenge and it was a good feeling when I found the idea and solved it.

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

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

Legendary battle!

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

Mathforces

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

    you was warned:

    The TON protocol was designed by Nikolai Durov — who is a two-time ICPC world champion, a three-time IMO gold medalist,

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

How to solve D?

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

    I submitted my solution when it was 0.03 s but it said contest is over. So can't say if i am right or wrong. But i think it should be,

    If n is odd, the ans is 2.. If n is a power of two, then -1 Else n can be written as 2^r * q... where q is odd.. then min(q, 2^(r+1)

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

      Can someone say if i am right or wrong. If I was right, i would be very mad as I just got wrong answer at first by accidentally giving max in the place of min. And when i submitted it said contest is over

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

      .

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

      where q is prime

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

      If N=42; Then 42=2*3*7 . So min=(2,21)=2 ; According to your logic the ans is 2. How can we make 42 with 2 elements having remainders {0,1} ?

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

        well he said min(2^(r+1), q) in case of 42 r = 1 so ans is 4.. you can make 42 by using 4 elements 9 10 11 12

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

      sorry for my wrong eyes:) yes ,you are right.

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

        Thats why i wrote min(q,2^(r+1))... sorry for writing wrong at first

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

    It can be shown that any number x can be obtained by defined operation if and only if 2x can be written as product of two numbers a and b with the condition that a and b are of different parities and none of them are 1. k is equal to the minimum of them. You can obtain this by observing the following: 2x = k*(k+1)+2nk = k(k+1+2n) where n is an integer. My AC.

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

    Minimum sum with k numbers is $$$k*(k+1)/2$$$, and remainder will be 0 if $$$k$$$ is odd and $$$k/2$$$ if $$$k$$$ is even. If $$$n = 2^k$$$ answer doesn't exist, otherwise let $$$n = 2^k * p$$$, if $$$p*(p+1)/2 \leq n$$$ (since p divides n) answer is p else answer is $$$2^{k+1}$$$ (since $$$n = 2^k$$$ (mod $$$2^{k+1}$$$)

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

    A fact holds: $$$N$$$ is a $$$k$$$-good number, if and only if $$$N \le \dfrac{k\times (k+1)} 2$$$ and $$$(N - \dfrac{k\times (k+1)}2) = 0 \pmod k$$$.

    Let's look at the second equation. if $$$k$$$ is odd, it means that $$$k\ |\ N$$$, otherwise $$$\dfrac k 2\ |\ N$$$. and with the first equation, we can make a guess:

    Expressed $$$N$$$ as the product of an odd number $$$p$$$ and an even number $$$q$$$, and one of $$$p$$$, $$$2\times q$$$ works.

    It's easy to explain why it's true. From the previous observation, we know that both two numbers satisfy the second equation. As the first equation can be transferred into $$$k \geq \sqrt {2 \times N}$$$,but $$$p \times (2 \times q) = 2 \times N$$$, so if both of them obey the equation, then $$$2 \times N = p \times (2 \times q) < \sqrt {2 \times N}^2 = 2 \times N$$$, which is absolutely wrong.

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

      Some corner cases here:

      if $$$N$$$ is smaller than 5, we can just add some if-else to deal with them.

      if $$$N$$$ is an odd number, and it's greater than 4, then $$$N$$$ must be a 2-good number.

      $$$2^x$$$ is not $$$k$$$-good for any $$$k$$$.

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

i don't see any pattern in D x_x

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

Problem D is solved by prime factorization?

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

    No, isn't possible to factorize number up to 1e9. I think there is idea to make ansers 2, 4, 8... or some divisors of n

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

I submitted my code when it was 0.03 s but it said contest is over. Can anyone say why?

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

    Maybe there is a delay between your computer and the site.

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

lol, tourist prevented rating loss by hacking. Also he's still in div 1 after halving his rating

Wow, just tying 1st place causes rating loss for him

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

I hate Number Theory :(

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

1 hack attempt made a plot twist

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

How to do F? I kinda figured out you need to find an MST where the $$$a_i + a_j$$$ part of edges add up to 0. However, I am not sure how one would do that though.

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

    They don't need to, as long as there exists lines (representing tree costs) going up and down it'll be bounded from above. Your idea doesn't apply in test case 4. That being said, I don't know how to solve it.

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

    The number of possible MST is at most n-1.

    That is :

    sort the sequence .

    There is a number k :

    for all i<=k, there is an edge (i,n) .

    for all i>k ,there is an edge (1,i)

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

I think B is much harder than C

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

    B is easy! You just need to find 2 numbers whose difference is k

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

Tourist surpassing 4000 today.

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

Can anybody tell me the predicted rating for tourist....i don't have the chrome extention

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

Guess forces

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

    Totally agree! I made lots of guesses when solving problem B, D, E and F.

    It's like, intuition tells me this algorithm is right, so I write it down.

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

ad-hocforces.

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

I found a mistake in my code for G in the last minute but I failed to submit it:(.

I think the contest time could be a bit longer.

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

    It passed, getting a bit sad:(.

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

    Same happened with me in F, my solution was overflowing and I realized it after submitting (WA solution) in last 20 seconds. I got AC now :(

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

What in the world is problem C???? I'm probably the only one who could do D but not C. (cries for 9 consecutive contests)

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

    if not exist 1,all number can mod themselves if exist 1, for Ai,it need to mod Ai — 1,if exist Ai — Aj == 1 then ans is NO else YES

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

    how you solved D

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

    Found C way easier than B and D, everyone is different

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

    If you choose x as maximum number in array then only x becomes 0 and others remain same. Repeat few more times and all will be zero. there are corner cases with 1. Help me with D please!

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

      First, think of the condition of an integer $$$n$$$ to be a k-good number.

      • $$$k=2$$$, $$$n=3+2x$$$

      • $$$k=3$$$, $$$n=6+3x$$$ (For all multiples of 3!)

      • $$$k=4$$$, $$$n=10+4x$$$

      • $$$k=5$$$, $$$n=15+5x$$$ (For all multiples of 5!)

      • $$$k=6$$$, $$$n=21+6x$$$

      • $$$k=7$$$, $$$n=28+7x$$$ (For all multiples of 7!)

      (where $$$x \ge 0$$$)

      and so on..

      You can run a brute force for all $$$n$$$ from $$$1$$$ to $$$100$$$ on your computer. You will notice that: if $$$n$$$ is an odd number, than it will always be a 2-good number. If $$$n$$$ is an even number, then $$$k$$$ can be determined by $$$n$$$'s lowest bit.

      For example, we have the condition $$$k=8$$$, $$$n=36+8x$$$, which works for $$$n$$$ which have $$$4$$$ as their lowest bit. If $$$n \ge 36$$$, then $$$k=8$$$ is definitely an answer. If $$$n < 36$$$, then we will have to check the divisors of $$$n$$$. We can divide $$$n$$$ by its lowest bit, the result will definitely be $$$n$$$'s divisor.

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

^_^

Where can I take my 8 coins and how often will you do same rounds?

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

I am the guy hacked by tourist... no just kidding.

Congrats, to the king!

Edit: Oups, that aged badly :(

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

I solved A,B,C but my score is very poor kkkk..

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

Maybe I have witnessed history that the T God reached 4000

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

Is there any polite way on codeforces to express the thought "I didn't like the contest/problemset" so that MikeMirzayanov wouldn't come in the comments and write a huge paste, how am I wrong to belittle the work of the authors and coordinators?

»
3 years ago, # |
  Vote: I like it -14 Vote: I do not like it

thanks for the great tasks

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

The main idea of G is very similar to this problem: https://codeforces.me/problemset/problem/325/E

But I'm not mad as it is quite an old one and actually is one of my favourite problems ever.

I have quite funny story about it. That problem I linked is actually exactly the algorithmic version of 6th problem from finals of 56 PMO. When I participated in that Codeforces contest back then, I didn't like the mid-difficulty problems and decided to ragequit midway through (I guess I was just bad lol). After 10-15 minutes I thought "maybe I will at least read E" and came back to read it only to realize that it is one of my favourite problems ever and started coding it frantically. I was really tight with time and in the end I managed to implement it only to lack literally a second, because I did not manage to click "Submit" on time. And of course when I was allowed to submit after the contest it indeed turned out to be correct and would bring me from ~300th to ~30th position and would be my first ever Div1E problem accepted (I did not manage to get one for 3-5 years after that)

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

Pollard Rho algorithm passes pretests for D... :(

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

so krvk55 has become a celebrity

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

How do I redeem my TON?

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

whats wrong in this logic for c ans is yes when:- 1. all are already equal. 2.arr does not contain 0 and 1(we can divide each number with itself to get rem 0). 3.if 0 is present, 1 is absent(0 and 1 cannot be changed). 4.if 1 is present,2 is absent(1 cannot be changed, 2 can be changed but only to 0).

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

Just for my curiosity, if tourist did not make a successful hack and shared the first place with jiangly, would he still got -38 delta as CF predictor says? If so, how is it even possible?

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

    I guess its since he tied with someone with a lot of rating below him(?)

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

Here is some feedback on the problem set:

  • A: Nice easy problem.
  • B: Nice easy problem. Initially I was confused and it seemed like a knapsack problem, then I saw the pattern. This may have appeared in the past, but who cares. It was a nice easy problem and I enjoyed solving it.
  • C: Ok problem. Not particularly interesting, it is just a matter of considering various cases.
  • D: The problem is okayish, but [edit: here the was a rant about the TL, but I discovered that there is a solution which requires only to find an odd divisor of $$$n$$$ so what I was saying is nonsense.]
  • E: Wonderful problem. I spent 1 hour thinking and not able to come up with something respecting the constraint on the size of the weights. Then the correct idea struck me and it was wonderful.
  • F: Boring standard problem.

Thanks to the authors.

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

    D can be solve in $$$O(\log n)$$$. It's just enough to divide into $$$2^x \times p = 2n$$$ where $$$p$$$ is odd, and the answer would be $$$\min(p, 2^x)$$$, with a failure if $$$n$$$ is a power of 2.

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

    Thank you for your feedback. Could you please elaborate on why you thought F was standard, for example linking to a similar problem?

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

      You are welcome.

      Regarding F: The statement is artificial.

      The solution has three independent ideas:

      1. Reducing the problem to the case of costs $$$c_{ij}=a_ia_j$$$ by replacing $$$a_ia_j + t(a_i+a_j)$$$ with $$$(a_i+t)(a_j+t)-t^2$$$.
      2. Finding the structure of the MST for graphs with $$$c_{ij}=a_ia_j$$$.
      3. Answering what the problem asks.

      A problem which can be split in three independent ideas, unless one of such ideas is clearly more deep than the others, it's not the best problem as it ends up being the sum of three standard problems. But let's go deeper:

      1. For me this step was immediate. This is standard because the expression given is so artificial that it suggests heavily to look for a nicer form.
      2. This is the core of the problem. Even though the construction is not particularly unexpected, I don't remember ever seeing this in the past. Still, this is easy and not-so-deep for a problem F. Moreover, it is obvious that a nice construction must exist, otherwise the problem is unsolvable.
      3. Thanks to 1, 2 one knows that $$$f(t)$$$ is piecewise linear. Computing the maximum of a piecewise linear function is standard.

      I don't see why you gave the problem with an arbitrary $$$t$$$, instead of asking to compute the MST for $$$c_{ij} = a_ia_j + a_i + a_j$$$ (or even for $$$c_{ij}=a_ia_j$$$). With $$$t=1$$$, Step 1 and step 2 are exactly the same (with $$$t=0$$$ Step 1 disappears), but step 3 disappears and the implementation becomes easier (which is a plus in a contest with 6 problems to solve in 2 hours). If the answer is "Because the problem would have been too easy", I would answer with "It's never a good idea to make a problem harder just by adding an obfuscation layer which requires also some implementation effort".

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

        Thank you for the detailed feedback. I agree that the statement is somewhat artificial.

        Also, I have seen how you have posted those problem-by-problem feedback in each of the rounds and I must say it is very helpful for problem authors.

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

        I understand where you're coming from, but just to put a counter-weight — I don't share your views and I think this problem is totally fine. Maybe not the most exciting one, but not one that turns me off either. For me adding the $$$t$$$ parameter surely makes the problem more attractive. A bit different way of looking at it was that "each spanning tree gives a linear function and we take minimum out of all of them, hence we have piecewise linear concave graph". Investigating whether it is bounded was a nice starting point to get some understanding and since it is concave we can ternary search. Tbh I did not even think of a $$$(a_i+t)(a_j+t) - t^2$$$ reformulation even though that should have definitely crossed my mind, but I managed to get around without doing it either way.

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

Why such logic for C doesn't work?

We can transform any number x to either 0 or 1 by % x or % (x — 1) (We have sorted all of them and now making tranformations from higher to lower x). We have some limitations such as we can't transform 0 -> 1, 2 -> 1 and 1 -> 0. So the answer is "no" <=> we have (0 in array || 2 in array) && (1 in array). Otherwise the answer is always "yes".

Where am I wrong?

150748690

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

A

constructive algorithms

C

constructive algorithms

D

constructive algorithms

E

constructive algorithms

F

constructive algorithms

G

constructive algorithms

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

    A competitive programming problem

    B competitive programming problem

    C competitive programming problem

    D competitive programming problem

    E competitive programming problem

    F competitive programming problem

    G competitive programming problem

    H competitive programming problem

    I competitive programming problem

    The only problems out of these that I would classify as constructive problems are E and G. The rest as constructive problems is a super stretch

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

      No important algorithms were involved in the solutions, atleast for us div 2 participants. Almost all problems could be solved in 4-5 lines of code. Overall the contest was not balanced I would say

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

        That I can't refute. However that does not imply these were constructive problems

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

I must say I like the problems. So clear, concise, and to the point. I kinda don't like the problems which revolve around a story or too much information to even just understand input and output format.

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

FST moment for tourist

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

Tourist system test failed T_T

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

problems a,b,c,d need only math skills not programming

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

Got FST on D , from less than <1000 before system testing to 1765 ;(

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

D. Strange, but it works...

    #include <bits/stdc++.h>
     
    using namespace std;
     
    #define int long long
     
    signed main() {
        int tttt{};
        cin >> tttt;
        while (tttt--) {
            int n{};
            cin >> n;
            if (n % 2 == 1) {
                cout << "2\n";
            } else {
                int yyy = 2;
                while (n % 2 == 0) {
                    n /= 2;
                    yyy *= 2;
                }
                if (n == 1) {
                    cout << "-1\n";
                } else {
                    if (yyy < n) n = yyy;
                    cout << n << "\n";
                }
            }
        }
        return 0;
    }
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    could you prove/explain your approach when n is even and not of the form of 2^k

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

      nope, my intuition could, but I'm lazy ;)

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

      Basically, the task asks us to find a $$$k$$$ where $$$k$$$ divides $$$(n - \frac{k(k - 1)}{2})$$$. Also, there is an extra constraint that $$$\frac{k(k - 1)}{2}$$$ should be less than $$$n$$$.

      A simple observation is that if $$$k$$$ is odds, $$$k$$$ divides $$$\frac{k(k - 1)}{2}$$$. Otherwise, $$$\frac{k(k - 1)}{2} \bmod k = \frac{k}{2}$$$.

      Suppose that $$$n = 2^t q$$$ where $$$q$$$ is odd number. If $$$1 < q < \sqrt{n}$$$, using $$$q$$$ works, because $$$q$$$ divides both $$$n$$$ and $$$\frac{q(q - 1)}{2}$$$.

      On the other hand, $$$2^{t + 1}$$$ also works. The reason is that $$$(n - \frac{2^{t + 1} (2^{t + 1} - 1)}{2}) \bmod 2^{t + 1} = (q - (2^{t + 1} - 1)) \bmod 2 = 0$$$.

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

One more hack to 1000 TON. The lesson learned from the contest the bucket count is different for different versions of C++.

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

Thank you for participating!

If you have got into prizes or just want to join the TON, then register a wallet, follow one of these links: https://tonkeeper.com/ or https://wallet.ton.org/

Tomorrow, I will ask all prize winners to fill out a form with their wallet address (48 character string).

UPD: Here is the link to the form: https://codeforces.me/userForm/203c74605996e40f

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

    21 hours have gone

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

    where is the form

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

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

    41 hours now,where's the form :(

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

    45 hours have gone.

    More and more hours, what should I do?

    More and more hours, what should I do?

    More and more hours, what should I do?

    More and more hours, what should I do?

    More and more hours, what should I do?

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

    I believe that before distributing a prizes you should take a closer look on participants who made to top 1000 with newly created CF account (after round announcement to be precise). It looks like some already existing users may have created alts and rewrote their solutions a bit to not get caught in order to get more coins for making into top 1000. One such suspicious user is forcoin (even name is suspicious, doesn't it?). Looking at his submission 150775063 you may notice declaring variable long long y=n; with further usage it instead of n without any change. Typical obfuscation thing.

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

      Found even better example 150736946:

      1. int x; cin >> x; f[x]++; a[i] = x; without further usage of x
      2. if (f[a[i] - k] > (a[i] - k == a[i])) — the audience award for the most sophisticated way to say 0 considering that k always positive :)

      BTW, account was created half an hour before a contest start. At the same time forcoin's account was created 3 minutes after contest start.

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

        do you try to find 7 most strange participants among 1000, baka?)

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

          You caught me! :)

          But at the same time I'm always trying to fight plagiarism and rules violation (especially when it's not just "virtual points" at stake) and this time I'm sure there is some illegal stuff going on.

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

            maybe yes, but it is not ok to suggest that some solutions is not honest because them looks like not honest and on them is label "not honest"

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

              I'm not asking to consider these solutions not honest just because it looks so, I'm just pointing that they are suspicious. MikeMirzayanov may have some better criteria of checking that then just a code analysis. E.g. if CF servers store IP of every session — he may look if these users were accessing the website from same IP and judge if I'm right based on that. Or if there were some other users taking part in the contest from same IP as one of these (to prove that they are alts) etc. The code weirdness is just a signal for further investigation — not a resolution. And all what I'm saying is that these users are suspicious enough to do such investigation.

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

                IP-checking is bad too. maybe two people have solving contest from one IP but from different monitors. in some university, for example.

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

Why i failed a system test in B and my complexity is O(n log n) searching for a pair whose difference is k??

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

Anyone failed B due to unordered_map / unordered_set ?

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

Todays contest was quite easy i think

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

I mistakenly thought $$$n\leq 10^5$$$ in B (actually $$$2\times 10^5$$$) and passed the pretests. How could it be so weak like this...

I think I can avoid this problem if I use int a[100002],n,k; instead of int n,k,a[100002];. Is it almost correct?

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

Thanks for the great problemset! This is one of my favorite CF rounds.

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

    I am really having a hard time figuring out if this is a joke or you actually mean it ?

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

problem E has a weak system test.

My solution https://codeforces.me/contest/1656/submission/150810889 can pass both the pertest and the system test, but it works in O(n*a[root])

A graph like 99999 nodes connecting with one node directly can hack this solution

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

    Such a case was already present in the system tests. However, in that testcase the central vertex is not $$$1$$$, so your solution passes.

    Do you know if it is possible to construct a case against your solution if you start from a random vertex instead of vertex $$$1$$$?

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

      No way, cause it can probably choose a vertex with minimal edges. By the way, the solution can be fixed easily by choose a good vertex

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

      but if a use a leaf as a root then i'll get WA because a[i] is out of [-1e5,1e5]

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

Highly appreciate the person who writes the problem Statement.To the point and easy to read,no unwanted story and other stuff. Highly NJoyed

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

No sane coordinator would accept a round where the first 7 problems are geometry, DP or data structure bash, but somehow this is acceptable?

I think that the problems individually are fine, but I absolutely hated the set as a whole, there is no variety at all. None of these problems involves any consideration of time complexity, it's just "figure out a single idea and then write a trivial implementation". No data structures, no algorithms, no DP, just simple greedy, ad-hoc observations and constructions. DE would be better suited for a IMO-style contest with the statement changed to "prove that this is always possible".

Though I know that it is futile to ask given where the platform's contests are heading, I once again have to ask, please, no more rounds like this in the future. It's on the coordinator to ensure that the problem set is balanced over topics, and this round absolutely fails on that metric.

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

    Given your rating and your position in the final standings, I understand you are annoyed because of your performance in this contest. In this contest the most typical topics such as known algorithms or DP were not present as you mentioned, and I assume this is the kind of problems in which you perform the best. However, the most common themes don't need to appear in every contest, so you shouldn't blame the coordinators for your dependence in said themes to perform at your usual level.

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

      Stop making assumptions! All he is saying is that a contest shouldn't contain problems based on just one topic.

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

      Given your rating and your position in the final standings, I understand you are happy because of your performance in this contest. In this contest the most typical topics such as known algorithms or DP were not present as you mentioned, and I assume this is the kind of problems in which you perform the worst. However, the most common themes don't need to appear in every contest, so you shouldn't blame the coordinators for your dependence in said themes to perform at your usual level.

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

      I think it is ridiculous to try to refute my complaints by just pointing to the fact that I lost rating. If you think I am complaining just because I did badly, you might want to see the last time a round like this happened. That time I got +14 rating.

      However, the most common themes don't need to appear in every contest

      Yes, absolutely. I do not dislike this round because this round didn't have DP, because it didn't have data structure problems, or because it didn't have anything algorithmic. My issue is that this round had only ad-hoc problems, which by the way are by far the most common theme on codeforces. When was the last time you saw a round without ad-hoc problems?

      Once again, I want to state that I think the problems are not bad. The issue is that there is no variety.

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

        Glad to see someone against Constructive-force.

        I have to admit ad-hoc tasks often amaze me, though I barely solve them personally.

        Also I would like to add another point that putting the task I in a 2-hour long contest is ... insane. Given the number of definition and lemma in the editorial, may I ask if it was taken from some Algorithmic Graph Theory textbook?

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

For those, who solved E. Just curious, how did you came up with the solution?

Reading the editorial, I understand the proof of correctness, but don't understand the intuition behind it.

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

    I first rooted the tree. Then I tried to think if I could make each subtree of even distance from the root have sum 1, and each subtree of odd distance have sum -1. Then the only thing left is to make sure the root has sum 0. I believe this ends up as the same construction in the editorial.

    (To see why alternating +1,-1 is desirable, try drawing it out on a decently large tree, and examining what each component looks like after removing a vertex.)

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

    I quickly realized that if S is the sum of all weights of vertices, then S — W[v] must be divisible by deg[v] for all vertices v. My first instinct was to try to force S — W[v] = 0, but this clearly can’t work for all v. As a result, I suspected that the construction would depend heavily on deg[v], and writing out the sample case after that was enough to come up with the construction.

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

    I ended up characterizing all solutions to such a tree. Let $$$s_u$$$ be the common sum of the components when $$$u$$$ is removed. Let the sum of values of all vertices be $$$S$$$. Then when you go from a vertex $$$u$$$ to an adjacent vertex $$$v$$$, you get $$$s_u + s_v = X$$$, so if you color vertices in an alternating manner (say in red and blue), you get that $$$s_u$$$ is the same for all vertices with the same color. Now inductively, you can show that if $$$x$$$ is the $$$s_u$$$ for red vertices, and $$$y$$$ for blue vertices, then $$$a_u = x - (d_u - 1)y$$$ for blue $$$u$$$ and $$$a_u = y - (d_u - 1)x$$$ for red $$$u$$$, where $$$d_u$$$ is the degree of $$$u$$$. This clearly works if you set $$$x + y = 0$$$, and the intended solution uses $$$(x, y) = (-1, 1)$$$.

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

    I considered a case of a path on 4 vertices. First solution I found was [2, -1, 1, 1], but that doesn't look particularly nice, so I kept searching for nicer solutions. Then I found [-1, 2, -2, 1], which looked much nicer. I noted that prefix sums are [-1, 1, -1, 0] what led me to that path IanDeHaan described

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

Newbie here,

can someone tell me why with unordered_set is giving tle 150812826 but not on set 150813232.

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

I think tests for D are weak. It's not hard to generate counter cases of naive prime factorization on $$$n \le 10 ^ 9$$$ or pollard-rho on $$$n \le 10 ^ {18}$$$.

»
3 years ago, # |
Rev. 4   Vote: I like it +41 Vote: I do not like it

Before the contest: Wish tourist to cross 4000 line

5 minutes before contest ends: Rank 2, no hope to cross 4000.

contest ends: Tourist hack others, rank 1! First contestant to cross 4000 !

After system test: Tourist failed in problem G, rank 8, drop back to 3800+.

Life is drama.

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

Solution to D: It's obvious that when n is odd, we can just let k == 2 be the answer, so the following steps are cases that n is an even number. It's easy to have the equation: k(k-1)/2 + mk = n, m is a arbitrary number. If k is an odd number, then we must have n/k > (k-1)/2 + m. If k is an even number, we can change the equation into 2*n/k = k + 2*m — 1. We can see that the right part is an odd number. So an idea is to divide 2*n into sum * odd, in which sum is a power of 2. If odd is smaller than sum, we can see that 2*n/odd > odd, n/odd > (odd-1)/2=odd/2 so odd is the answer. If odd is bigger than sum, we can let k == sum, 2*n / sum > sum, which 2*n/sum is the odd number k + 2*m — 1.

150775598

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

Why is my code giving TLE for problem B? submission:150815444

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

    Please read this: unordered_map is an associated container that stores elements formed by the combination of key-value and a mapped value. The key value is used to uniquely identify the element and the mapped value is the content associated with the key. Both key and value can be of any type predefined or user-defined.

    Internally unordered_map is implemented using Hash Table, the key provided to map are hashed into indices of a hash table that is why the performance of data structure depends on hash function a lot but on an average, the cost of search, insert and delete from the hash table is O(1).

    Note: In the worst case, its time complexity can go from O(1) to O(n2), especially for big prime numbers.

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

    It is advised to use Ordered_map instead of unordered_map

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

Can anyone help me with the corner case for which this might fail(Problem C): https://codeforces.me/contest/1656/submission/150819310

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

Hello everybody! Thanks for your feedback!

I would like to invite you to the online mirror of Spain's Olympiad in Informatics which will be held on 2 and 3 April. Check this blog post to see details. Note that if you want to participate, you should register before this Saturday.

If you liked the problems on this round, be sure to participate! And if you didn't — well, there are some additional different problemsetters in the Olympiad other than me, so you should participate anyways.

Cheers!

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

Good short statements. Everything was easy to understand.

ABCDE were a bad combo of mathy/constructive problems. F was ok and H was nice, but I would enjoy them more in a div1 contest as B and D, with some time left for a more difficult problem.

Please stop using linear scoring distribution in combined rounds. If every next problem is only +500 extra points, you discourage people from switching to hard problems. Spending an extra minute while solving ABC is already more important than spending an extra minute in H. And it hurts a lot if somebody fails a medium problem because it's worth more than a hard problem (~2500 for F and ~2200 for G and H today).

Geometric scoring is much better. If you don't want to use values as big as 6000 points, just decrease A to 250 points.

UPD: If you have got into prizes or just want to join the TON, then register a wallet, follow one of these links: https://tonkeeper.com/ or https://wallet.ton.org/

Strange instructions. We should do this and the prize will magically appear?

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

    It's hard to find Mike's comment among these 250 comments.

    "Tomorrow, I will ask all prize winners to fill out a form with their wallet address (48 character string)."

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

    Geometric score distribution can lead to a strategy, where you solve a problem from G to A. Maybe the contest writer didn't like these kind of strategies.

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

      Why is it bad?

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

        Because that's more like ATCoder: some coders just set a goal(like 4 problems in ARC for me) and solve the target problem first. If that problem takes too much time, they just abort the contest and get unrated. For ATCoder, they set a rule called "rated/unrated participation" and I think this rule is worse than the current one :(

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

          Good point. You indeed can try a hard problem and skip a contest if you don't come up with a solution fast enough. But it's less extreme in CF because the sum of submission times matters. You shouldn't solve multiple problems and wait with submitting. (So I still think geometric scoring is a better option.)

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

How to redeem the prizes?

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

I have a TON Wallet now, so what should I do to deal with it?:D

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

    This might follow from the fact that $$$f(t)$$$ is convex.

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

Jiangly YYDS!!!!!

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

jiangly yyds!

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

Is it a joke that the I problem is rated 1800 ? UPD : Now it's rated 3500 xD