flamestorm's blog

Codeforces Round 928 (Div. 4)
By flamestorm, 12 months ago, In English

mesanu, SlavicG and I are very excited to invite you to Codeforces Round 928 (Div. 4)! It starts on Feb/19/2024 17:35 (Moscow time). We would also like to give a very special thanks to the efforts of MikeMirzayanov and Vladosiya, who helped significantly with the preparation of the round!

The format of the event will be identical to Div. 3 rounds:

  • 5-8 tasks;
  • ICPC rules with a penalty of 10 minutes for an incorrect submission;
  • 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
  • after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
  • by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

Thanks a lot to the testers: MADE_IN_HEAVEN, Gheal, Dominater069, Phantom_Performer, Vladosiya, htetgm, sparkles, tvladm!

We suggest reading all of the problems and hope you will find them interesting. Good luck!

UPD: Editorial is posted!

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

Comments Comments (197)
| Write comment?
»
12 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Still a lot to learn.

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

My first unrated contest. Hope to solve all problems.

→ Reply
»
12 months ago, # |
  Vote: I like it +31 Vote: I do not like it
Le Cyans
→ Reply
»
12 months ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

I remember the night after Codeforces Round 922 (Div. 2) this was the only contest on schedule. What I didn't expect is the whole week of contests from Feb11...

And finally time to end the winter vacation in a relaxing Div.4

Hope to AK.

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
oops
→ Reply
»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

7:51 PM

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Dsy before yesterday this was unrated for me. Today it's rated. Tomorrow after rating update of today's div3 this will be again unrated for me

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

After such a long time, a division 4 contest!

Meanwhile:

codeforces

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

e236aa49858efa9da2330e82b3d41e57ca2733ba

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

I hope I dont become unrated in this after todays Div 3. Plzz rating be below 1400.

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

If my rating before the begining of this contest is lower than 1400, but then(after the begining)it increases(because of previous Div3), will I be rated participant or not?

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Rating distribution please.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My first unrated Div 4 ;-) Still lots to learn...

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

the rating predictor is showing me -10 after the last div3 so i should be allowed to participate in this div-4 but they are not allowing me for now so is there anything that i can do

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Being a tester of this round i can easily this is worth giving for participants of all rating... You can push your time limits.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Cyan pls

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

In blog mentioned 5-8 tasks, but all div4's shows atleast 7 tasks but none of them shows 5 or 6 tasks . Plz change it to 7-8 tasks instead of 5-8 tasks.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My first unrated Div4:)

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

unrated is 1400 and over btw

been waiting for this for a while lol

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

First unrated contest :)

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

This becomes unrated for me after yesterday's Div3 rating changes :/

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my first competition is that okay?

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

here for the reach my apologies

all of this was in a response to a comment i made on the thinkcell round post asking how 2ball did A to C in eight minutes he reached out to me in the dm's and here is what transgressed. I am not accusing him of anything other than being vulgar and disrespectful, a 20 something year old should not retaliate by calling someone the N word i am attaching the pictures of the chat MikeMirzayanov please take the necessary action edit- the image link i don't think i am able to embed it properly https://imgur.com/a/o00YXuU

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

    It's funny how jealousy's got him moving mad like this.

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

    I kindly ask flamestorm and MikeMirzayanov to take action against CHATTY-Bebob as he is leaking private data, and as the individual in question appears to be seeking attention. If they were not seeking attention, they would have directly contacted the authorities or the contest conductor,

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

Good luck for everyone!!!!!!

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

finally unrated for me!

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey there I want to put light on cheating going on during contests. I found few evidences against CHATTY-Bebob that he surely has been copying codes during contests. He has used 2 different templates in the same contest which makes no sense And in the 3rd code I found something interesting , there was a comment asking not to completely copy the code .So it is clear that he has been copying codes which is pretty evident from gradient if his ranks too

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

    I often ask chat gpt to fix my code ergo the other templates.

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

      Bro chatgpt wont put that comment , it surely is copied from some other user and everyone knows chatgpt cont fix good codes. Whom are u fooling bro . I request MikeMirzayanov to ban cheater like CHATTY-Bebob

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

        That don’t copy my shit code comment is mine. It used to be over my dummy functions so yeah that’s that

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

Good luck to everyone and have fun!

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

Is this really div 4?

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

RIP Div4 trusted participants

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i felt like C had something to do with repetition of the series 1...9 but wasnt able to prove it in the contest , did anyone get the proof?

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Hint
    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah i did that because I couldnt prove that the repetition could be generalized into a formula.

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

      Are you saying looping over 1e5 and storing all results would pass in 1/2 seconds ?

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

        It is possbile to precompute answer in O(n), then you can answer queries in O(1)

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

          Actually precalculation is O(nlogn). For integer n, compute the digit sum of n is O(log n). Or is there any optimization?

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

            Because it has many testcases.The force algorithm in O（Tnlogn）in bad case。

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

              we are not calculating for each test case.

              calculation is once which is nlogn and answering t queries in constant time. which is nlogn + t

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

                Of course, I mean solving it in brute force instead of precalculating the problem.

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

            sorry, I initially intended to reply to someone else.

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

            you are right.

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

            Hey, log n is 5 at max so it is O(5*n) which is O(n)

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

              In same，it can be regard as log10^n.

              → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe this is Div3 or Div2.5？

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is this div4?

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

it is not div4 , it is div 2.5 or div3 and also C problem is not easy

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

    I'm agree. It was like Div 3 but problem C is okay because it said that time limit of problem is 0.5.

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

seems this contest was too hard for a div4 contest.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

loved the div. E is brilliant , i don't think div 4 contestants would know dp though to put it in C.

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

    do you really count prefix sums as dp...

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

      ooh yeah you're right , dp was what came in my mind that time but yeah it's prefix sums my bad

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

    I think precomputation would fit better for the name of the concept lol

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

Awful contest as a div4. It sucks.

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

    Catch

    IMO this is unfriendly for div4, esp. D and F I keep failing F as well

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Try not to make half the problem set depends on math challenge.

difficulty : impossible

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

My first contest, still a lot to learn

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

Hardest Div. 4 ever

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain or give some hints for F? i thought in bitmask dp but i think the states won't fit on memory or time limit ( thought also in DnC but i think it still won't fit on time limits)

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

    i thought the problem was putting a number on every cross and putting the numbers on the positions of the cross. it becomes this problem: you have different sets of numbers from 1 to n, what is the minimum number of sets you can choose so their reunion is 1....n? i just feel like i know this problem but i forgot the solution

    → Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it
    Spoiler
    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      so maybe i just can bruteforce on all state with a bfs like apporach?

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

        Yes, I bruteforced but not by bfs but by checking all possible placements of flips (with constraint from the above hint).

        Additionally, I used two more hints:

        Spoiler
        Spoiler
        → Reply
        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thanks i got the first spoiler but didn't get the last one but i will think in why its true thanks alot

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

            Yes, the last one is the hardest to grasp. Without it my program run about 10s.

            Spoiler

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

    dp bitmask works. Suppose we are at cell (i, j), we only need to consider 16 previous cells. So we can have a solution with complexity $$$O(T * 7 * 7 * 2^{16})$$$. Luckily it fits to time limit.

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

      oh i didn't think on that i was thinking in something like n2 * 2^49 thanks

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

        If you want to know more about this technique, it is called DP on Broken Profile.

        In my experience, this technique is quite rare, and it is actually the first time I have encountered it in a live contest. (Though I tried to cheese it and solve the problem in $$$O(T\cdot N \cdot 2^{3 \cdot N})$$$, which failed)

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

          thanks alot first time hearing about that technique i will check it out

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

    The first thing to note is that you just need to modify the black cells located in the central $$$5 \times 5$$$ cells. With this fact, you can just bruteforce all the $$$2^{25}$$$ patterns and check the cross pattern, which requires $$$2^{25} \cdot 25$$$ loops at most. This is actually too much -- what can we do to improve this?

    It turns out that you can separate the whole board into two by their parity: $$$A = \{ (x, y); x + y \; \text{is even} \}$$$ and $$$B = \{ (x, y); x + y \; \text{is odd} \}$$$ (imagine the chessboard pattern). The cells in $$$A$$$ do not interfere with cells in $$$B$$$, and vice versa. Therefore, you can bruteforce each of them, resulting algorithm with $$$(2^{13} \cdot 13 + 2^{12} \cdot 12)$$$ loops, which is fast enough.

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do C?

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

    I believe just pre-computing all the value before hand will work.

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

    First, prepare all answers from $$$1$$$ to $$$2\cdot10^5$$$ in an array. To do that, make a loop from $$$1$$$ to $$$2\cdot10^5$$$ and in the loop write $$$a[i]=a[i-1]+sumOfDigits(i)$$$ where $$$sumOfDigits$$$ is like this:

    int sumOfDigits(int n){
    int s=0;
    s = s + n%10; //(last digit of n)
    n = n / 10; //(remove last digit)
    return s;
}

    then for each input $$$n$$$, output $$$a[n]$$$.

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

I rarely take part in Div4 and Div3 contests but today I had some free time and decided to give it a casual try. I must say, that I was positively surprised. I especially enjoyed problem F, which was one of the nicest problems I have solved for quite some time. The solving process just felt joyful and everything in this problem fits very nicely to a solution that runs below 4s. Big thank you to the author of this problem :D

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

hardest div4 ever. The writers should include more low rated people in testing.

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

I recorded myself live while solving A,B,C,D,E and thinking F. Hope it helps someone: https://www.youtube.com/watch?v=Zr2JbyTwq0A

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve F though, i was thinking backtracking but the complexity is too big

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

    I used backtracking. Solution is 8 at max and we need to switch only Bs which are not on the border of the grid.

    So we have to do backtracking just on 25 elements, choosing maximum 7 out of them (if its not solution, then the answer is 8). With the solution check, the final complexity will be T * 7 * 7 * C(25,7) which can be amortized.

    Despite the mask solution, I don't know of any other solutions.

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

      i didn't think about that maximum solution is 8 that's why I couldn't make the solution better i guess yeah thanks that helped

      → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the description of E is not clear enough.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I did just C in 2 hour and someone did just B in 20 min. Why i am not higher on standing as i soved a more difficult problem??

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

    Because they past 2 problems but one for you

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

    in ICPC style contests there is no assigned difficulty to each problem, all are the same,since he was faster , he is ranked higher

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Ill miss specialist by 3 points :(( carrot sowing 40, i need 43

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

    You needn't worry . Carrot often underestimates the growth rating . According to my experience you will get specialist this round :)

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

it is too hard for div.4 F，F hard than G too much，i think maybe F can be 2000+

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

I solved G using MaxFlow. I think this solution is overkill and more likely fail system test. Can anyone hack my solution please? Link for my submissions: https://codeforces.net/contest/1926/submission/247343993

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

    I am pretty sure your solution is correct. The problem can be reduced to finding the minimum cut from every node labeled P to every node labeled S. Your solution finds the maximum flow, which is equal to the mincut according to the max-flow min-cut theorem. Since the graph you build is a unit graph, it should fit within the time limit with $$$O(N \sqrt{N})$$$ complexity.

    Please correct me If I'm mistaken.

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

      To be more precise, Dinic works in $$$O(\min(E^{1/2}, V^{2/3}) \cdot E)$$$ on unit graphs, and this bound is tight. The $$$O(E^{1/2} E)$$$ part is textbook (residual paths get longer on each iteration), and the original paper for the $$$O(V^{2/3} E)$$$ bound is "Network Flow and Testing Graph Connectivity" by Shimon Even and R. Endre Tarjan (1975).

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

      I think you are right. I did not use the property of unit graph in order to compute the time complexity. My bad.

      → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This div4 round is not easier than most div3 round I met . Did CF notice during the check process？

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Problem G can be solved trivially using the techniques discussed in the tutorials DP on Spanning Subgraphs and DP on Induced Subgraphs

Of course, easier solutions exist, but if you are aware of the technique of adding children incrementally, this can reduce your brainstorming time.

Here are 3 practice contests to test your understanding of the topic:

Contest 1 Contest 2 Contest 3

My submission, based on the ideas discussed in the blog.

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

div. 4?

div. 2.5!

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

Codeforces Round 928 (Div. 4) (A + Div. 3)

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Description of problem B is terrible , we have to assume that where-ever 1 appears , it would be part of a pattern

my approach was just to check if number of 1s in two consecutive rows would be same , it will be a square

else triangle

it fails on:

0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0

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

    It is guarenteed that only either of triangle or square is appeared on the grid. No pattern other than a triangle or a square is possible.

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

      in the explanation part the case highlighted with a big cross...what does it mean ?

      doesn't it mean that such cases would be a part of input as well ?

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

        That can be ignored since the answer was always either TRIANGLE OR a SQUARE , so had to check if there was a single star in a row, if it was , then answer would definitely be triangle else square

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

    Here's a Codeforces life hack that I've started doing and it has helped me a lot most of the time: if a problem statement or problem editorial is too confusing, try to ask ChatGPT to translate the original russian text to english. It will usally translate it better.

    Example for today's problem B

    You can see it's way clearer from that translation that if there's a $$$1$$$ in the grid, it will necessarily be part of a square or triangle.

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Haha B took me 35 minutes, but C took me 4, D took me 5 and E took me 27

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

problem f is harder than problem g :skull:

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

the last div3 is much easier than this round lol.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell why am I getting TLE ? https://codeforces.net/contest/1926/submission/247263560

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    the to_string() function take O(n) time, so using it in inside of a loop takes your complexity to O(n^2), which gives tle

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

      what does n denotes here ? the number n itself or the digits of n

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

    Change int dp[mxN]; to int dp[mxN+1];. See 247374406

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

    to_string(x) works in O(num digs of x) = O(log x).

    Your code is TLEing because of accessing dp[mxN] when size is mxN. And this causes an undefined behavior.

    // wrong
    for (int i = 1; i <= mxN; ++i) {
// correct
    for (int i = 1; i < mxN; ++i) {
    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great round really enjoyed hope to have 5 minutes more as so I could submit G within time although kudo's to whole team.

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Greedy solution for G: Do a dfs and while doing a dfs pick edges as greedily. For each vertex v we remember a value: After greedily picking edges, if we look at the component of thin walls that v is in, if it contains a sleepy student, it's value is 1, if it contains a party student then it's value is 2 and if it doesn't matter we value it with 3.

Now, we want to pick new edges,currently at vertex v.

If v is sleepy, we should pick all edges from v to children with value 2. The value of vertex v is 1.

If v is partying, we should pick all edges from v to children with value 1. The value of vertex v is 2.

But what if v doesn't care? Well let cnt1 be the number of edges from v to a child with value 1, and cnt2 be the same thing but with value 2.

If cnt1 > cnt2: We pick edges from v to children with value two.(cnt2 edges) and the value of v is 1.

If cnt1 < cnt2: We pick edges from v to children with value one.(cnt1 edges) and the value of v is 2.

But if cnt1 == cnt2: We don't really care what side we pick, as it's equally optimal we take bothe of them(at least for now). So the value of v is 3.(We add cnt1(or cnt2) to number of edges we picked). The reason for this in that when updating the parent node, we can choose the side of vertex v we want to pick based on the chosen value of parent vertex so really the value of v doesn't matter and is not counted.

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

    Ya my approach was same I just did dfs calculate for child then for current node make the above cases

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

First time using Haskell in contest!

Screenshot

Thank you guys for the amazing round!

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

    The code looks like a literal translation of C++ though, each function having do defeats the idea of Haskell.

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

      Yes, the code may look C like but actually that's all I know about Haskell so far and I'm comfortable with this style, I find it readable and easy to debug if needed also.

      And since it's Div4 so I want to make something new beside using C++ in almost every round, I think I will use Haskell more often in the future.

      Thank you for reading my code and commenting!

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

        Out of curiosity I looked couple times if anyone uses Haskell, and there were very nice solutions, if you want to learn functional style there are examples of it. Although when coming from C++ sometimes it's not obvious, for example, in one problem there was TLE, and then after random (for my eye) shuffling and it's AC :)

        → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great problems, but I think F is a little hard in Div.4 and G is too easy to be the last problem.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why I am getting TLE? How can I modify it? https://codeforces.net/contest/1926/submission/247369927

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

    Two pointers 247373952. I came up with the idea of this solution after the contest. Since we want to match numbers such that $$$x XOR y = INTMAX$$$ and the following is true: $$$x < y => XOR(x, INTMAX) > XOR(y, INTMAX)$$$ we can match numbers using two pointers. This avoids maps and sets.

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

    Like this: 247436179

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explains why my solution for problem F is wrong 247324886 ?

Idea : while there is at lease 1 black cells with four diagonal neighbors, find the most common cell and make it white. Is my approach wrong or the error is in the code ?

Thanks in advance.

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

Round 925 is easier than Round 928

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint for c ... please

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

could anyone tell me where my code will fail for problem D, i am getting WA on test case 3

https://codeforces.net/contest/1926/submission/247380111

Spoiler
→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    When input is with length of 4: 0 2147483647 2147483647 2147483647, you answer gives 1. Correct answer is 3.

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

In problem G — "The second line of each test case contains n−1 integers a2,…,an (1≤ai<i) — it means there is an edge between i and ai in the tree."

What does this mean ? How should I form the edges ?

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

    It's basically giving you the ``normal" representation but in a slightly different way, instead of inputting two variables, $$$u$$$, and $$$v$$$, only one is inputted, and you get the other one from the line number.

    --a[i];
adj[i].push_back(a[i]);
adj[a[i]].push_back(i));
    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why do you reduce a[i] by 1 ? How did you interpret it as an edge between a[i]-1 and i ? Also is i from 1 to n or 0 to n-1 ?

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

        Reducing $$$a_i$$$ by $$$1$$$ is due to zero-indexing versus one-indexing. $$$i$$$ is from $$$1$$$ to $$$n - 1$$$ (it is actually from $$$2$$$ to $$$n$$$, but once again zero-indexing versus one-indexing). You can use whatever way you want; if you're used to one-indexed, you can just not subtract $$$1$$$ from $$$a_i$$$, and use it as is. I'm more used to zero-indexing though, so I use zero-indexing.

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

    It means {1, 2, ..., n} is a topological ordering if you view the tree as a directed graph with root at 1, because the index of the parent of i is less than i.

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I was able to solve 1st and the 3rd problem during the contest but i find hard to implement the second problem .

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

    You can have a look on my solution 247235514, it is very easy to understand and smart solution

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this get TLE https://codeforces.net/contest/1926/submission/247355922 while this doesn't https://codeforces.net/contest/1926/submission/247356724 ? Only difference is unordered_map vs map (unordered_map is getting TLE while map isn't)

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

    It's because unordered_map uses a hash table, and one of the tests has been engineered to make the hash table work badly by creating many collisions. See this blog post for a more detailed explanation.

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

I think F and G are harder than div.3...

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For me, F is too hard to solve.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was someone able to find a mathematical formula for C?

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

    you can read my comment, I have been posted it 4-5 minutes ago

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is sad news, I originally thought that the performance score was above 1609 half an hour ago, but at this time, when the final settlement was announced, it was 1450, which made me still have a gap of 9 points from the goal, T_T

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

    ikr, I usually get more rating than carrot's prediction, but this time got lower rating.

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

      I guess i have the badest luck then

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

        Hopefully get to the blue before the provincial race :)

        Chin up, I believe it is not far from being realized

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

It was my first and last rated Div.4 round.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good bye pupil, Hello specialist

→ Reply
»
12 months ago, # |
← Rev. 11   Vote: I like it 0 Vote: I do not like it

Is there anyone who solved problem C by using math? I was trying to solve it by using math, and noticed that the difference of the sum of the sum of digits of each number from one to nine and ten to nineteen is equal to 10 and the difference of the sum of the sum of digits of each number from ten to nineteen and twenty to twenty nine is also equal to 10 and ... I am interested by the next question: -Can be this problem solved by using law for sum of sum of digits I have noticed?

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

    I solved it in this way

    input is 1434

    then find the answer upto 1 to 1000 then 1001 to 1400 then 1401 to 1430 then 1431 to 1434

    and add the result of the above 4 answers

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

    Check my submission for C I used recursive function to solve it

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

    Perhaps you can refer to mine 247347016

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

hii

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

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

Hello, due to the message I received that my code for the Problem C is very similar to some other people's, I have seen this problem before in GeeksForGeeks and I knew the solution . I think I did not do anything illegal!

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

CODEFORCES ROUND 928 DIV4-

For the Question C of the contest codeforces round 928,I got this message

Your solution 247285175 for the problem 1926C significantly coincides with solutions JonahWeaver/247270977, arnavra3/247285175, Jelly.bean/247290520. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I have evidence that the function that i have used for the question https://codeforces.net/contest/1926/problem/C was already published long before the contest.

The coincidence occurred due to using the same function to solve the question. (coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details). This is the function used to solve the question- https://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/

Thanks for your time and for looking into this.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

CODEFORCES ROUND 928 DIV4-

For the Question C of the contest codeforces round 928,I got this message

Your solution 247332861 for the problem 1926C significantly coincides with solutions Banik1313/247268922, mahendraakshansh/247332861. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I have evidence that the function that i have used for the question https://codeforces.net/contest/1926/problem/C was already published long before the contest.

This is the function used to solve the question- https://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/

Further a small change was done by changing the functions variables using gpt. Thank you for looking into this.

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

On my C problem in round 928 (Div 4) I got this message from the system:

"Attention!

Your solution 247290520 for the problem 1926C significantly coincides with solutions JonahWeaver/247270977, arnavra3/247285175, Jelly.bean/247290520. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked."

In my solution, I took reference from an online website https://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/

It was already uploaded on the website long back, and using it thus does not violate the rules and regulations probably.

I thus request you to look into this matter and do appropriate changes.

Thankyou

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

I received a mail as follows:-

Attention!

Your solution 247340583 for the problem 1926E significantly coincides with solutions sahilPict_26/247340583, MisterCheese/247358707. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I am really sorry if you find anything misbehave, but I have done the code myself, and I have used ideaone platform in public mode, because of it some one might have copied it , I don't even know the person MisterCheese. I will definitely take care of it from next time so please give my rating back as you can see my past contest history I have never tried to copy or misbehave during the contest,And I promise you I will take care of keeping my code private during the contest.

I also have refered an function which was already available on internet before the contest:- **https://www.geeksforgeeks.org/minimize-replacements-of-array-elements-to-make-bitwise-and-greater-than-k/**

This is the website were I refered the function it might be because of that the solution may look similar.

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

CODEFORCES ROUND 928 DIV4-

For the Question C of the contest codeforces round 928,I got this message

"Attention!

Your solution 247268922 for the problem 1926C significantly coincides with solutions Banik1313/247268922, mahendraakshansh/247332861. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked."

I have evidence that the function that i have used for the question Problem Link was already published long before the contest.

The coincidence occurred due to using the same function to solve the question. (coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details). This is the function used to solve the question- Coinciding Fuction Written well before the contest

Thanks for your time and for looking into this.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

CODEFORCES ROUND 928 DIV4- For the C Question, I got this message:

Attention! Your solution 247303195 for the problem 1926C significantly coincides with solutions saikumarailwar9/247274058, ved292/247303195. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I have evidence that the function that i have used for the question https://codeforces.net/contest/1926/problem/C was already published before the contest.

The coincidence occurred due to using the same function to solve the question. This is the function used to solve the question- https://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/

Kindly look into it.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

They removed our rating for a similar code with a person with whom we study together, but they analyzed a similar problem and wrote down the code in a notebook.

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

E: Would building an Euler tour and then looking at pairs of nodes of the same colour with no other node of the same colour between them on the tour work? Update: Nope. And wrong thread altogether. :)

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have received an attention for the problem https://codeforces.net/contest/1926/problem/C of Codeforces Round 928 (Div. 4). The message was here. Attention!

Your solution 247303669 for the problem 1926C significantly coincides with solutions sntanju07/247303669, Rafid_Nabil/247351936. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

The code I have used from https://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/ which was last updated on 27 Jun, 2022. That's why, I can prove that the code exists before the contest. The coincidence occurred for using a common source.

Please consider it. Thank you.

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

I have received an attention for the problem https://codeforces.net/contest/1926/problem/C of Codeforces Round 928 (Div. 4). The message was here. Attention!

Your solution 247310309 for the problem 1926C significantly coincides with solutions kurvep18/247310309, Ritiksharma_09/247338668. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

The code I have used from https://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/ which was last updated on 27 Jun, 2022. That's why, I can prove that the code exists before the contest. The coincidence occurred for using a common source.

My codeforces id :- kurvep18 which was registered with email :- [email protected] has been blocked by codeforces, please review this comment and consider reactivataion of my id [kurvep18]

Please consider it. Thank you.

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

Dear mesanu, SlavicG, flamestorm I got to know that my submission 247357510 was similar to a few other submissions. All I did was copy a template (As I'm a newcomer, I didn't have any submission template with me. So, I literally took a template as it is from a CodeForces blogpost) which is available online on GitHub, link to which is :- https://ncduy0303.github.io/Competitive-Programming/Contest%20Template/main.cpp

Could you please check this. I assure you that I've not cheated in any way. Even the approach taken to solve the problem is a generic approach using bit manipulation & maps.

https://www.google.com/amp/s/www.geeksforgeeks.org/number-of-mismatching-bits-in-the-binary-representation-of-two-integers/amp/

I used the concept of Approach 2 provided in this article. Please look into it and do the necessary.

Thank you

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My Submission link ved292's submission

Article i copied from

Blog about rule for third party code

According to the 1st point mentioned in the blog

This

I haven't copied this solution from him it was an coincidence that my code is matched with his code

I request you to look into this issue MikeMirzayanov

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A to E was OK, F was much harder.

→ Reply