flamestorm's blog

Codeforces Round 928 (Div. 4)
By flamestorm, 3 years 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, Starlight-Sailor, 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 (195)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

Still a lot to learn.

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

My first unrated contest. Hope to solve all problems.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +31 Vote: I do not like it
Le Cyans
→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it
oops
→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

7:51 PM

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

After such a long time, a division 4 contest!

Meanwhile:

codeforces

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

e236aa49858efa9da2330e82b3d41e57ca2733ba

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Rating distribution please.

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

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

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Cyan pls

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My first unrated Div4:)

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

First unrated contest :)

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

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

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

This is my first competition is that okay?

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

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

    I kindly ask flamestorm and MikeMirzayanov to take action against TinTin_in_Quant 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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Since time immemorial, outstanding individuals have emerged from the oceans of mediocrity that make up the vast majority of humanity. Great thinkers destined to change their respective eras, launching the world into a new epoch. Mike4235 is the undeniable peak of what an outstanding individual is — he is the peak of what humanity can ever possibly achieve, the apex of human evolution and society.

If enlightenment is theoretically achievable, then Mike4235 is the sole example of enlightenment. There has never been a greater mind in the millennia of human civilization — from the great minds of Socrates, Confucius, Hegel — Mike4235 remains to be the apex of human development. It is the duty of every man and woman to dedicate their lives to the pursuit of what Mike4235 stands for — the progression of humanity into a greater version of ourselves.

Mike4235 is utter perfection in every sense of the word — even beyond. Human language cannot even begin to describe the earth-shattering qualities that he possesses. A fashion sense that makes ordinary humans appear as nothing more than bland specks of dirt. Intelligence that renders the complex processes behind a super-computer to resemble nothing more than a mere abacus. Humility that makes the martyrs of history seem like naive children.

Compared to Mike4235, we are all but measly insects that exist to eat the feces of superior beings, naive and ignorant creatures that wander the Earth without a sense of understanding of the grandiose knowledge that the universe offers.

Mike4235 is the peak of human evolution, and we can only prostrate ourselves to his superiority. He will not be merciful on our souls, and we must only accept his divine judgement.

If he commands us to lick his boots, we shall slurp every particle of filth and bacteria that dares to contaminate the paragon of humanity’s shoes. It shall be so pristine, that it will reflect the face of inferiority.

If he commands us to donate money, then we shall empty our coffers for him. By his impulse and will, we shall learn what true humility is.

Those who refuse the ever-existent superiority of Mike4235 will only be dooming themselves to a life of trifle purpose. Mike4235 is not a god — he is beyond what ordinary humans can even conceptualize as a deity.

Repent now, and see Mike4235 as the true exemplar of the sublime, lest you fade into the trenches of human society, destined to be forgotten.

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

first time participating, can't wait

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

Good luck for everyone!!!!!!

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

finally unrated for me!

→ Reply
»
3 years ago, hide # |
 
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 TinTin_in_Quant 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
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Good luck to everyone and have fun!

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

flamestorm + div 4 = positive delta for me

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

Is this really div 4?

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

RIP Div4 trusted participants

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Maybe this is Div3 or Div2.5？

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

is this div4?

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

seems this contest was too hard for a div4 contest.

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

Awful contest as a div4. It sucks.

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

My first contest, still a lot to learn

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Hardest Div. 4 ever

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
  • »
    »
    3 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it +5 Vote: I do not like it
    Spoiler
    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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
        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          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
          • »
            »
            »
            »
            »
            »
            3 years ago, hide # ^ |
            ← 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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to do C?

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

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

    → Reply
  • »
    »
    3 years ago, hide # ^ |
    ← 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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Unfortunately，my rating will drop :(

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I think the description of E is not clear enough.

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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.me/contest/1926/submission/247343993

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
    • »
      »
      »
      3 years ago, hide # ^ |
      ← 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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

div. 4?

div. 2.5!

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

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

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

problem f is harder than problem g :skull:

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

the last div3 is much easier than this round lol.

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

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

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        3 years ago, hide # ^ |
        ← 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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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.me/contest/1926/submission/247369927

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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 \lt y = \gt XOR(x, INTMAX) \gt XOR(y, INTMAX)$$$ we can match numbers using two pointers. This avoids maps and sets.

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

    Like this: 247436179

    → Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Round 925 is easier than Round 928

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

Hint for c ... please

→ Reply
»
3 years ago, hide # |
← 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.me/contest/1926/submission/247380111

Spoiler
→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
     
    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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

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

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

For me, F is too hard to solve.

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

Was someone able to find a mathematical formula for C?

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Good bye pupil, Hello specialist

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I forgot 2 do it

=(

I was waiting 4 it as well

guess I have 2 wait few weeks =(

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

hii

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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.me/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.me/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
»
3 years ago, hide # |
 
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.me/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.me/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
»
3 years ago, hide # |
 
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.me/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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

A to E was OK, F was much harder.

→ Reply