DeadlyCritic's blog

Codeforces Round #652 (Div. 2)
By DeadlyCritic, history, 6 years ago, In English
$$$~-\text{In the name of God}~-$$$

Hi community,

I'm glad to invite you to my first contest, Codeforces Round 652 (Div. 2) which will be held at Jun/23/2020 17:05 (Moscow time) ($$$\text{notice the unusual time}$$$). The problems are mainly prepared and invented by me. The round is rated for participants with rating strictly less than $$$2100$$$, others are able to take part in the round out of competition. You will be given $$$2$$$ $$$\text{hours}$$$ to solve $$$6$$$ $$$\text{problems}$$$.

Firstly I'd like to thank adedalic for coordinating and reviewing the round, as well as helping with many different things.

I'd like to thank antontrygubO_o, physics0523, McDic, Ashishgup, dannyboy20031204, Kuzey, SinaSahabi, FieryPhoenix, lov.ish, ITDOI, AM_I_Learning, awoo, lynmisakura, JustasLe and ArimeZ for testing the round and giving valuable feedback.

Also I'd like to thank coauthors, amiralisalimi, AS.82 and davooddkareshki for helping me with inventing and choosing the problems.

Finally, thanks to MikeMirzayanov for very nice and convenient Codeforces and Polygon platforms.

I wish you all will find the problems interesting, thank you for participating, and good luck!

$$$\text{Scoring distribution : } \; 500 ~- 1000 ~- 1500 ~- 2000 ~- 2500 ~- 3000$$$

$$$\textbf{UPD}$$$ : Editorial is out

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

Comments Comments (311)
| Write comment?
»
6 years ago, hide # |
 
Vote: I like it +55 Vote: I do not like it

An Iranian round after a long time .....
Thanks for your hard work.

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

I am an atheist.Can i participate in this round?

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

Ashishgup held three rounds and now he is a tester in this one. That's a lot of work.

→ Reply
»
6 years ago, hide # |
← Rev. 4  
Vote: I like it -72 Vote: I do not like it

Deleted

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

I am a beginner.Can any one give some advice about this contest.Please ,It will be helpful for me.

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

    A — dificulty will be less than 1200 & B -will less than 1400 most of the time..practise those problem from problemset with those difficulties . I think it will help

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

      many many thanks for your advice.

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

      If you get stuck on these, read the editorials. They will give you an idea of the sorts of algorithms that you need for problems at this level.

      → Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +42 Vote: I do not like it

    If it your first contest, don't worry if you don't solve much. Even as a very experienced programmer (40 years as a professional software engineer) it took me a few tries to get the hang of programming contests.

    Unless you are in the last couple of minutes of a contest, always try running the provided examples locally (or using "custom test") before you submit. On Codeforces you lose points for failed submissions.

    If you know more than one programming language use whichever you find easiest to write. So long as you find a reasonable algorithm, performance is unlikely to be a major issue until at least the 4th of 5th problem. I use Python for my submissions, and (using PyPy3 to run it) I have yet to find a problem that it is too slow for.

    → Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    • A-difficulty between 800 to 1200 with tags including 'brute force', 'implementation', 'math', 'sorting' (rarely), etc;
    • B-difficulty between 1200 to 1500 with tags including 'binary search', 'data structure', 'divide and conquer', 'strings', 'combinatorics', etc;
    • C-difficulty between 1400 to 1800 with tags including 'dp', 'dfs', 'trees', 'graphs', 'bitmasking', etc;

    Moreover, after the contest is over you can always read the editorials or can refer others solutions. You can practice for any difficulty or any tag from the problemset by using filter provided on the right side.

    "Happy Coding :)".

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

      Thanks a lot...... I will remember your suggestions... again thanks a lot .... "Happy Coding you too & this community :)"

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

As a Tester I feel that the problem set is more diverse and good for everyone , there is something for everyone to solve and ya the round is good for those who just want to start with competitive coding!. Hope everyone to give this nice round!

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

Any specific reason for the unusual time?

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

Very Excited for your first contest!!

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

I think that's the beauty of codeforces. We get the best of problems from different countries which covers lot of diverse types of problems and helps us improve in different areas with each contest. We got 2-3 good indian rounds, this one is an Iranian round and 654 Div2 will be a Japanese round:).

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

    First time when i came across this platform, I found it very weird because it's UI is not very attractive but when i started participating in contests I have just fallen in love with this platform and no other coding platform gives me this much of joy while solving questions. I think codeforces community is really great and helps a lot in growing as a competitive coder.

    → Reply
»
6 years ago, hide # |
← Rev. 6  
Vote: I like it -106 Vote: I do not like it

Now Wish you Bad luck for downvoting bruh!

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

Downvoted. There's no reason to drag in religion here on Codeforces -- keep it to yourself.

→ Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +283 Vote: I do not like it

    I don't see any reason to not to add a single line, which doesn't hurt anyone in any kind(or does it?). If i could see, then i would not.

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

      I'd say the setter has some freedom to include selected topics in his announcement/problems. A few contests back we defended Codeforces Round 645 (Div. 2) for having the corona-virus theme. Clearly, while the theme is offensive to some people, the vast majority of users seemed to find no harm in the in the author expressing his personal humor here.

      We must not adopt double standards: we tend to give our authors leeway to include their personal touch in their contests and announcements. Whether it is references to anime, marvel universes, corona, or religion, a persona touch is usually tolerated by the community historically.

      If a subject is considered too divisive then the community will naturally express it with sufficient downvotes, so either way we'll find out what everyone thinks.

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

        I think allowing the authors to add their 'personal touch' is the right approach. It's lots of work to author a contest, they should be able to broadcast their messages to people who read the CF announcements.

        Also, I can't imagine too many people caring enough to mass downvote an announcement or editorial. And this is good because most of us are here to improve on our CP abilities and not to get offended by the authors' political views, religion, and memes.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, hide # ^ |
           
          Vote: I like it -9 Vote: I do not like it

          I think as long it is not offensive for anybody, authors can add whatever they want.

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

        Thank you brother karim

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

      You can proudly add it bro. I think, this will not hurt anyone.

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

      I personally love when the authors include their personal touch to problems(or blog) and the editorials. It feels real-like problems. Also if you make an editorial like this I'd love it :-)

      → Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it -94 Vote: I do not like it

    When You are not start every work with name of GOD means there are not any GOD that is the best.

    if he use "In the name of Allah" it may be correct but it's a General sentence and all of people know it and hear it at least once.

    → Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it -57 Vote: I do not like it

    FYI in Iran it's a formal compulsory custom, much like a head cover for girls. Every article, movie etc. must start with this string. It's not an author's personal statement. More like a national trademark for a text.

    please correct me if I was wrong.

    → Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +21 Vote: I do not like it

    Guys! Just take it easy! You are blaming the author cause of adding a simple line with some common words(And not a verse of Quran!), while you are sharing the black lives matter hashtag on Instagram and Twitter, HYPOCRITICALLY! You put knees on faiths' throat and try to kill them instead of learning that they exist, and you should live along them. I'm sorry if I just hurt someone with a kind of brute comment, but think about it!

    → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
      ← Rev. 4  
      Vote: I like it +6 Vote: I do not like it

      Bismillāh is not "some common words", and your metaphor is ridiculous. Regardless, everyone should be free to follow their beliefs and traditions.

      → Reply
      • »
        »
        »
        »
        6 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it +1 Vote: I do not like it

        Do you see any "Allah" word?! God is a common word that doesn't really refer to any specific religion. It's not Allah, Jesus and things like that which they belong to a religion. Of course God is a common and general word

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

    Stop being so boring

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

→ Reply
»
6 years ago, hide # |
← Rev. 5  
Vote: I like it +37 Vote: I do not like it

Ok, I'm deleting this meme.

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

In the name of God... Me an atheist....

It is going to be an interesting round.

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

Great

→ Reply
»
6 years ago, hide # |
 
Vote: I like it -41 Vote: I do not like it
  • Will this round be rated?
  • How many people will be participating?
  • Is there going to be any math involved?
  • How large are the statements?
→ Reply
»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Looking forward to the contest!

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

Lol Ashishgup everywhere orz...

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

[Deleted]

→ Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it -19 Vote: I do not like it

    you can not be a good coder by skipping geometry problem.so need to practice more in which you are weak

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

I wish there aren't any interactive problems because i'm done with those.

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

Hey guys..did you notice vovuh is back with his div-3 round...? so excited!!

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

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

Is it just me or do others feel as well that the quality of comments section is going down? All I see are a lot of shitty memes, "Is it rated" and relentless pursuit from a lot of people to just comment on something for the sake of it. It's extremely uncomfortable as quality discussion on problems gets suppressed due to a lot of this unnecessary crap

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

The last time there was a single setter vs an army of testers,Ehab happened! Hope God saves this round!

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

Please mention about unusual start time in announcement. I noticed it after reading it in comment section.

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

BTW I did my best to make the statements as short and clear as they should be, stories are written in another font so you can skip them, but don't forget to read them when waiting for system test. I tried to lessen number of tests so we should not see long queues.

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

You welcome.

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

guys post god memes

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

thanks for your explanation!

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

All the best to you for your maiden contest!

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

Thank you for remembering me.

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

How much money does someone makes by problem setting in these contests ,

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

once again Ashishgup

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

Edit: Got it. thanks.

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

.

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

Well ,Is there anybody else other than me who can relate to this ?
WhatsApp-Image-2020-06-22-at-4.00.51-PM.jpg

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

Score distributions are out.

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

Till now I was thinking that the round will be held today. I was prepared for it. :(

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

OK, got it.

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

Hope your first contest will be more interesting.

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

I have a good feeling to this contest <3 ;)

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

How can i see my solved problem distribution on CF ? (difficulty-wise) Thanks in advance........

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

DeadlyCritic Bro what an inspiring curve of rating you have . As a beginner these things motivate me a lot . Hoping to have more rounds from you!!

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

UNUSUAL TIME

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

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

Me: Yes, I can do it. I can solve all the problems. I will be rank 1. But after solving at max two problems, enough I am done with it. I am going to sleep.

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

I hope to be a pupil in today's contest anyway.

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

CodeForces and all the problem setters, coordinators, testers are doing an amazing job to arrange such good contests on such regular basis. Hats Off to their efforts!

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

Why people nowadays are discussing such irrelevant topics in the comment sections?You guys have other social sites to do these stuffs.CF is not the right place to share memes & have a discussion about if the author can add "In The Name of God" in his post or not.

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

Humble request to authors: Don't make it Propaganda forces Thank you!

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

Hopefully, your entry as a contest writer will be interesting and hoping for an interesting contest as you said :).

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

submissions in queue for a long time. will contest delay?

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

This time is very unusual as per India. As many of the students stay in the hostel, and it coincides with dinner timings of the mess: 1930-2130 IST. So either we have to skip dinner or lag in the contest.

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

GLHF EVERYONE!

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

Man I keep getting Wa on A again I solved 3 problems and my rating will stay the same :(

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

How to solve D What was D.

→ Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it +10 Vote: I do not like it 
    if(x%3==0) f(x) = 2*f(x-2) + f(x-1) + 4
else f(x) = 2*f(x-2) + f(x-1)
    → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
       
      Vote: I like it +7 Vote: I do not like it

      can you please prove this.i was able to get both recurrence but was not able to figure out when to put the condition .

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

        The tree of level x can be decomposed into three subtrees of level (x-2), (x-2), (x-1) respectively, which are connected by root node. Claws can be chosen from the bottom. The claw including root is used for x=3. For x=4, one subtree will be of level 3 so its root cannot be used. For x=5, two subtrees will be of level 3 so root cannot be used. For x=6, the roots of all three subtrees are unused so one more claw can be picked. similarly, for every multiple of 3 one extra claw is picked.

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

I lost too much time convincing myself that the proof for problem B I had in my mind was correct :D Anyway, I really enjoyed the problems. It was a good contest.

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

"For each test case, print a single integer — the maximum number of yellow vertices Lee can make modulo 10^9+7." — having the maximum modulo instead of the maximum actual answer modulo 10^9+7 was very nasty. Should have been explained better, as usually the problems require the actual maximum modulo something.

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

    What? I think that's just messed up wording, because I solved the standard problem and passed the pretests.

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

Summary of the contest:

Wrong answer on pretest 2

Easy D

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

How to solve D??

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

    $$$f(n) = f(n-3) + 4*T_{n-2,0}$$$
    where $$$T_{n,0}$$$ is the number of nodes with degree 0 in the RDB of level n

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

Please don't write −In the name of God − from next time :(

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

How to solve problem E? I tried to model the problem using graph network- food type as node and each friend as edge. How to proceed?

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

    If solution exists then for any subset of people solution exists as well, so try to find a guy who can be in last position.

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

    E should be solved using greedy and has no relationship with graphs.

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

any hint for problem D !?

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

How to solve E? It is a variation of Cow and Snacks. How to handle multiplicity of plates?

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

Nice and hard problem E, thank you author

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

I did not like this one. For me D and E where hard to understand, I restarted two or three times just to notice after some times that I did get the question wrong.

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

    Agree. I have to read D and E many times to understand them correctly. The statements are easy to cause confusion.

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

You tried to make a hard D ? You definitely made a deceptive D. Loved solving it.

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

    Actually earlier D was something Different which you might not Like , this was invented after hardships , this was a really nice DP problem I ever solved.

    → Reply
»
6 years ago, hide # |
← Rev. 4  
Vote: I like it +48 Vote: I do not like it

I don't know why my D solution is correct.

    for (int i = 4; i <= 2000000; i++)
        f[i][0] = max(f[i - 1][0], f[i - 1][1]) + max(f[i - 2][0], f[i - 2][1]) * 2,
        f[i][0] %= P,
        f[i][1] = 4 + f[i - 1][0] + 2 * f[i - 2][0],
        f[i][1] %= P;
→ Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Edit: oh nvm disregard

    → Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it -10 Vote: I do not like it

    [deleted]

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

    You are very lucky, because the modulo of the max is different from the maximum of modulo. But in this problem the two values doesn't differ from more than 4, so with some luck it works.

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

    you get maximum of two thing that differ at most one. this solotion is correct but our solotin is another thing

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

    Generally max(a, b) != max(a % mod, b % mod)

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

      Wow, it's true, and my solution with max should fall, but it worked :)

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

        It should not, as we know $$$a$$$ and $$$b$$$ differ by $$$4$$$ at most, so it works as long as $$$max(a \% mod, b \% mod) \lt mod-4$$$, and smallest such $$$n$$$ was so big.

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

          Did you consider changing Mod value instead of N or was it intended to leave that solution AC?

          Spoiler
          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, hide # ^ |
             
            Vote: I like it +5 Vote: I do not like it

            I didn't realize that I can change Mod, thanks I will note it for my later rounds, thank you. I prefer those solutions to fall, at least one-third of the solutions would fall.

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

              You're welcome :) I liked the problems actually they were very interesting. In the contest I've written solution similar to his one but was sure it will fail and you planed to trick us with such a case so I gave it 10 minutes more to find out the pattern when N is divisible by 3! That's why I tried to generate a valid MOD to prove I was thinking correctly LOL.

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

                :), If the MOD was something special, then yes I would do the same, but not when MOD is $$$10^9+7$$$. Also the sample had $$$2\cdot 10^6$$$, so there were no room for WA. Except some special Time Limit exceeded.

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

                  Sure actually $$$1000002193$$$ is the first prime number >= $$$10^9$$$ which could make their solution fail as I tested for each prime all possible values of N. I know it's hard to find such cases unless you predict that someone would do that exact solution while writing the problem constraints!

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

    I think it's OK, this is my code:

    for(i=3;i<maxn;i++){
	f[i][0]=(max(f[i-2][0],f[i-2][1])*2+max(f[i-1][0],f[i-1][1]))%mod;
	f[i][1]=(f[i-2][0]*2+f[i-1][0]+4)%mod;
}

    Isn't it right? Why you think it's incorrect?

    My English is't well, please forgive me. ovo

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

    To be sure that they will be no errors with the max, you can remark that the second value is greater than the first one if and only if i%3 == 0

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

Very descriptive questions. And I must say, the names were quite good too.

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

Why problem D I can mod then max to pp the testcases?

→ Reply
  • »
    »
    6 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +11 Vote: I do not like it

    No need to use max, ans is:

    dp[x] = (4*(!(x%3)) + ((2LL*solve(x-2))%mod + solve(x-1))%mod)%mod;

    PS: Just clarifying that badcw was asking another thing before, I have no idea why the solution with max works.

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

Can someone please help me out with B?

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

    you just have to find first and last occurrence of "1" and change substring between first and last "1" to either "0" if any "0" is present in it . or substring remains same if there is no "0" in it

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

'A' problem ruined my day,thx

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

'C' --> peace of shit

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

    was C about picking first i+b(i)-1 FOR.MIN AND THEN K max elemnt for max?

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

      It was sorting plus two pointers problem. First sort both arrays. Then one pointer at last element of arr1 and second at n-kth position, then move both pointers carefully.

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

      Every friend gets one of the k biggest numbers. Then distribute from the remaining numbers the w[0] smallest to the friends getting the most numbers. Then next friend with next biggest number gets next w[1] smallest numbers etc...

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

    After got 4 wrong answer and then got accepted.. Then just i thought ,, "How foolish i am" !

    Edit: answer was quite easy .

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

Cool problem D, even though my finger is fat and I typed %2, instead of %3. Just realized :D

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

How to solve D?

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

    By DP, ans is:

    dp[x] = (4*(!(x%3)) + ((2LL*solve(x-2))%mod + solve(x-1))%mod)%mod;

    If you try to draw the first trees, you will realize that a tree of level x is composed by this three trees.

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

    By DP. You can build a relation. ans[x] = (4*leaves[x-2] + ans[x-3]). Here leaves[i] denotes the number of leaf nodes in ith level tree.

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

When First Problem is A Geometry Problem, its just a mood spoiler ! :/

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

Why the problem suffix has to be "LEE"?

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

Interesting problems. Especially E, though I could not solve it. How to solve E?

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

Looks like I am the only one who thought that the sum of n over all test cases can exceed 10^7 in problem D :(.

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

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

Nice Contest! Liked the problems, hoping for more contests from you in future :)

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

Why max function is work here?. https://mirror.codeforces.com/contest/1369/submission/84764258

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

https://mirror.codeforces.com/contest/1369/submission/84784993 really?? What about making strong systests?

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

Problem A, why call it OX-axis and OY-axis ? What does O stand for ?

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

Plenty of examples. +1

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

Story in problem E was amusing

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

.

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

Here as the virtual Moss for Codeforces, busting cheaters and getting them out of their bills. I hereby present you another team Admiral_Wolf and smiling_addu

B: 84762137 and 84789248 , If you swap the if-else part, it's easy to say the solutions are the same.

C: 84771585 and 84786359 , Only the vectors in both the solutions are different. Also c <= k and the strange way c-k <= 0 are again the same, they did to save them from the moss.

D: 84791187 and 84796767 , Again the solutions are the same if you look at the parts below it's evident something is strange

dp[i] += (dp[i - 1] + dp[i - 2] + dp[i - 2]) % MOD;

dp[i] = (dp[i] + dp[i-1] + 2*dp[i-2])%mod;

To save from Moss, 2*dp[i-2] == the strange way dp[i-2] + dp[i-2]

DeadlyCritic MikeMirzayanov adedalic

UPD: The solutions are skipped

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

Not able to view the editorial. Its showing- "You are not allowed to view the requested page".

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

Recently, lots of cheating is happening in codeforces. In most of the contests solution of problems A, B, C and sometimes D (Div. 2) are being made available in ideone, which is not only increasing fake ratings, many genuine ratings are also being affected because of increasing ranks.

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

    It's very disappointing and the ones who are suffering due to this are mainly noobs, after doing 3 problems many are getting huge rating drops. It is even leading to frustration and loss of confidence.

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

    Really glad to see someone speak on this. In almost every contest, someone posts the solution on ideone(knowingly) and there are so many talented coders out there copying the same and getting their ratings boosted. Also some people are getting huge rating drops due to this. It's also ruining the fun of the contests. Are we helpless and can't do anything against this other than plagiarism checks.

    Also, I am ready to receive all the downvotes from the cheaters.

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

That was quite the LEE-round

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

I submitted the C question and passed the pretest but now it shows wrong answer. My logic matches the editorial and i am not able to find the bug in my code. Please help. https://mirror.codeforces.com/contest/1369/submission/84786141

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

Why does this doesn't work for D? I find for every level how many more(new) vertices with 3 children were added from previous level and then do dp[i]=dp[i]+dp[i-2]. Solution: https://mirror.codeforces.com/contest/1369/submission/84822790

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

Can anyone tell me how the answer for the case n = 5 is 12 in problem D? Any image would be highly appreciated

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

I accidentally used Ideone on public settings and someone copied and submitted the same code int this contest and now i received a system email regarding the penalty for this. Can someone guide me as to what should i do. This is the link of my submissions https://ideone.com/qDpu3b

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

Why I am getting MLE on this submisssion https://mirror.codeforces.com/contest/1369/submission/84815861 for problem C? tnx. My biggest variables are two arrays of integers of size 200000 each which makes it in total less than 2 MB.

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

    Your insertion sort doesn't terminate if the element needs to be at the start of the array.

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

      It seems insertion sort works fine. Can you please be a little more concrete?

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

        Try the test case below. During insertion sort key will be -1 and get compared to 13 (a[1]), then 1 (a[0]), then undefined (a[-1]) and at that point you rely on uninitialised memory to be <= -1 to stop it.

        1

        4 2

        1 13 -1 17

        3 1

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

Here's my screencast of getting 7th place. I discuss the solutions to all problems at the end.

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

Enjoyed the contest and neat editorials. Thank you DeadlyCritic and team !

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

A fact :

Problems' names are connected to difficulties, also they show you the gaps with high accuracy.

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

My first round))

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

My first round

→ Reply