flamestorm's blog

Codeforces Round 937 (Div. 4)
By flamestorm, 2 years ago, In English

Hej, Codeforces!

mesanu, SlavicG and I are very excited to invite you to Codeforces Round 937 (Div. 4)! It starts on Mar/28/2024 17:45 (Moscow time).

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: erekle, vladmart, nika-skybytska, Vladosiya, KrowSavcik, Dominater069, LucaLucaM, MADE_IN_HEAVEN, tvladm, nor.

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

UPD: The round is delayed by 10 minutes: https://codeforces.me/blog/entry/127616?#comment-1133556.

UPD: The editorial is posted!

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

Comments Comments (99)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i wish i could solve all problems glhf

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

Why no green/cyan testers in Div4 round?

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

Hope everything goes OK!

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

Ramadan Kareem

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

Div 4 : The format of the event will be identical to Div. 3 rounds Div 3 : The format of the event will be identical to Edu rounds Edu rounds: The format of the event will be identical to Icpc rules

Is that a recursion?

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

Hope it isn't a div2.5 as last time

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

Ladies and gentlemen, finally I can say what I've always wanted to say at Div. 4 rounds announcements: My first unrated contest :")

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

please be a div 4 contest for div 4 people

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

Hopefully, My last rated div4

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

Hope efforts pay and this will be my last rated div 4

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

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

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

Hope to become Pupil with this contest :D

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

where are "one refresh costed me 10 minutes" comments?

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

Sorry, but I'm moving the round 10 minutes forward. The training session was very cool and long. I'm running to you from the gym!

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

The contest is delayed?

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

Hey guys, anyone have the problems for this div 4 so I can practice beforehand?

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

queueforces ?

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

Seems like div5

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

nice problem set , thanks to the authors

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

It's fun that due to the long queueforces (and my own laziness to open a proper local IDE) I would actually submit all problems in blind and fix them accordingly after every CE/WA/RTE/TLE/MLE...

What was I doing with my life...
Thoughts on problems
Hints on problems
→ Reply
»
2 years ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

How to do F in one line

Spoiler

Looks pretty weird but got AC by the way =))

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

    can you explain furtherly the thought process behind that?

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

      Basically the construction idea is identical to the editorial, so you should read it first. I will summarize a little bit.

      If a does not equal to c — 1, then there is no answer. Otherwise, we will build a full binary tree from top to bottom, using the nodes 2 and nodes 1. The height of this tree is p = ceil(log2(c)). After that we will calculate the number of "missing" nodes in the last level of the tree. It will be $$$2^p - c$$$. Finally, we will add the nodes 1 into the last level of the tree, level by level, as it will minimize the height of the tree.

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

Fast tutorial

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

do I have to participate in 5 contests to receive a rating? do all 5 contests have to be div.4??

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

A -> just do what is asked ( i had 1 wrong submission in it, forgot take input a , b , c ;( )

B -> just do what is asked pattern printing

C -> standard question leetcode style

D -> here i generated all the possible product possible, then counted whether they exist in my set or not

E -> string hashing to check wether string are equal or not ( wasted lot of time in implementing string hasing i am stupid )

F -> ran out of time

G -> ran out of time

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

Why does these 253813411 gets tle even though it looks to me as O(n*2^n)

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

    It seems like you are trying all possible routes, which I'm afraid would be $$$\mathcal{O}(n!)$$$.

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

      Thanks for your reply,but why does the initution fail that at every vertex we have two possibilities either to take it in our path or avoid it hence total 2^n operations in recursion

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

        Not quite. Assuming a complete graph of $$$n$$$ vertices, your DFS would function something like this:

        dfs(1,0) -> dfs(2,1) -> ... -> dfs(n-2,n-3) -> dfs(n-1,n-2) -> dfs(n,n-1) -> dfs(n-1,n-2) -> dfs(n-2,n-3) -> dfs(n, n-2) -> ....

        You could guess it. It goes back to n again, but from a different parent, to seek a different path.

        Your intuition neglected a fact that ordering also matters here, and assuming a full path is required always, each path will be a permutation of those $$$n$$$ vertices, implying the actual order in the path.

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

          Thank you very much!

          Can you give a hack idea please 253831864

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

            Hacked.

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

Good competition! Thanks flamestorm,mesanu, SlavicG, and the testers :)

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

interesting round and one of the best div 4's,keep it up.

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

Who approved g? Why?

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

    A NP-hard problem. LOL

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

      I submitted a n^2 2^n solution which later got hacked due to TLE. Any idea what was the intended time complexity/approach?

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

        It was the intended complexity. I assume that you were hacked because of unordered_map instead — this has something to do with hash tables' collisions.

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

          Oh my previous code was indeed the same code with map. Which was hacked either. It was so dumb of me to retry the code with unordered_map. I'll link my solution after the system tests. But the idea was:

          1) Find all the subsets of the songs given.

          2) Create a graph with vertices as the songs choosen and edges between them if they have a connection (common genre or song writer).

          3) If the graph has a Hamiltonian path then that order can be choosen and we try on larger size subsets.

          Update: I was able to locate it now itself: Submission

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

Wasted a lot of time in a dsu/graph-based solution in G, when it was such a straight bitmask dp :/ pain

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

about F, the only case answer -1 is c != a + 1 right...?

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

Good round, thanks mesanu SlavicG flamestorm and all testers.

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

in F can anyone explain the -1 case

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

    Initially there is one spot for a leaf. Adding type A vertex takes a spot for leaf, but creates two more (+1). Adding type B vertex takes a spot for leaf and makes one (+0). Adding type C vertex takes a spot for leaf (-1). All leaf spots should be taken so there is $$$1+a-c = 0\rightarrow a+1=c$$$.

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

      Right. Another way to see this is — for it to be a valid tree, number of edges should be equal to the number of vertices — 1, by definition. Hence,

      2 * a + b = a + b + c — 1

      a + 1 = c

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

Good round!

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

Here's my live coding + commentary during the above contest: https://www.youtube.com/watch?v=kQOWiTvgah0

Would be glad if some of you find it beneficial!

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

My submission 253708600 for E was hacked.

Can someone hack these as well:

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

I request to disqualify the competition because they included the name "Taylor Swift" in the test cases :-)

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

Happy to finally get in DIV4 rounds :), and finally promoting to pupil. The problems were nice, sadly I had not beeing able to finish all 7 as I used to much time for E. Thanks to the writers and testers for creating this beautiful round.

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

Does code force hack by someone yesterday I successfully submit 3 questions and accept all but few moments ego it not show any questions submitted and suddenly showing only one question submitted why this happened does this happen with only everyone facing this issue and not get any rating yet

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

I had only 5 jugs of lassi this time..... In next contest I will be mango lassi.... be tuned to see me there as well.

Yours Lovely Kesar Lassi

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

CONGRATULATIONS the system testing took forever

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

is this contest made unrated? Why it is showing unrated in my profile although I am having rating less than 1400

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

when will the ranks get updated? I was 600+, solved two problems. Shouldn't my rank be changed?

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

When will ratings be updated?

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

I think there is a bug with people rating changes for this contest

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

    oops, I think it was a lag, codeforces was showing their previous rank names even though their rating changed (for example for 1405 it was still showing pupil). But now it is ok

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

Are you OK? This f**k E, I use map get TLE, but use unordered_map or add a return get AC, just because constant. This solution is like n*sqrt(n), why just give 1s?

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

mesanu SlavicG I got a mail stating:- Your solution 253808750 for the problem 1950E significantly coincides with solutions SahooBishwajeet/253808750, candidate_3_months/253813331.

I checked the solution comparison and most of the common part was use of same #defines and variable initialization. Though the approach looks quite similar, which is to my surprise, I can assure you that I've not cheated in any form. I've followed an article on GeeksForGeeks which has a similar problem to solve the problem in the contest.

The problem approach is quite similar to the problem : https://www.geeksforgeeks.org/find-given-string-can-represented-substring-iterating-substring-n-times/

Please check the issue as I've not used any unfair means during the contest period and honestly gave the contest.

https://pasteboard.co/cdhdULYYUpns.png https://pasteboard.co/c8TFSsNWtA4b.png

Here are the comparison images for reference

→ Reply