Vladosiya's blog

By Vladosiya, history, 2 weeks ago, translation, In English

Hello! Codeforces Round #811 (Div. 3) will start at Aug/01/2022 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third 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 1900 or higher in the rating. Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University teams: MikeMirzayanov, myav, Gol_D, Aris, SixtyWithoutExam, me Vladosiya.

Also many thanks to yorky, Jostic11, turmax, Bugman, Crescendo, antonis.white, molney, KerakTelor, andrey.starodubtsev, Ahmad45123, myway, Myao, Muhammad98 for testing the contest and valuable feedback.

Good luck!

UPD: Editorial

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

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

Good Luck everyone! I hope everyone has fun!

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

    I agree. I wish you all the best success!

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

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

    This contest was in fact fun, I can confirm. There is one thing on my mind though. When will ratings change?

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it depends. some contests give rating points after only 12 hours, while other can take up to 36, or even 48 hours. Reason? I don't know. I only speak based on my contest participating experience

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Where is the link to register? I haven't participated in any of the rounds earlier. Can someone direct me, how to do so. Thanks.

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Good luck everyone!

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Good Luck to everybody.

»
2 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

I am competing tourist in parrallel universe.

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Finally a div.3 round!!❤(●'◡'●)

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes lads we gray guys can finally answer more than just the first 2-3 questions

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

All The Best EveryOne !!

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

Hopeful this contest will be more friendly to newbies. Best of luck.

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

I hope it will be a great contest for everyone

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope everyone has fun Good luck for all participants I hope it will be nice contest

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Ollie gave

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally a div 3 round to be held. I was really looking forward to it. Good luck to everyone

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck Everyone for Div3 contest. I wish that newbie got high ratings in this contest

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

All my dreams are of an AK. (It only happened on a div 4)

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Agree with you! Me too having a dream to AK a div3!

    Now finally! I can participate in a contest.. after a long time (I had my exams). Hope this div3 would be last rated div3 for me! ;)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You all know that tourist decided G at the last minute.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope everyone will participate

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

let the rating increase!!!

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck Everyone :D hope i'll able to solve 1 or 2 problems ^__^

»
13 days ago, # |
  Vote: I like it -17 Vote: I do not like it

I am so weak that I can only get higher rating by div3 or div4 :(

  • »
    »
    12 days ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Why so many downvotes???I can't understand.

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

      Because you even got rating down on div3, like these downvotes.

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

Hope me and everyone good luck. I wish to AK some contest... I'm so weak that I can only solve 1 problem in Div.2...

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck Everyone! I hope that I get Pupil.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm registered as out of competition due to rating rollback, when the contests start will I be considered as out of competition or what?

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

    No, only the rating while registering is considered. If you want to participate as rated, you can unregister and register

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

One person is missing is Vovuh :p BTW, Thanks Vladosiya and team for the contest.

»
13 days ago, # |
  Vote: I like it -10 Vote: I do not like it

How to do well in Div. 3? What's your opinion if someone fails to solve all of the problems..?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    then try solve div 4

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Assuming you meant to fail to solve any problems, knowing arrays, sortings, and elementary maths is usually enough for first problems.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

oh, it's starts)

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope i solve ABC

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

wtf is that difficulty jump from c to d. Either try to make d easier or abc a little harder

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

    I personally found E easier than D. Although I didn't give much time to D cause it didn't strike me ngl XD.

»
13 days ago, # |
Rev. 2   Vote: I like it -39 Vote: I do not like it

swap F G!!!

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

    I don't think it is a good idea to swap them during the round.

    Аfter all, it is ICPC rules, the order doesn't play huge role here.

    • »
      »
      »
      13 days ago, # ^ |
      Rev. 2   Vote: I like it +18 Vote: I do not like it

      I mean,F is more difficult to solve than G. not really swap them :)

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

        finally I solved both of them :)

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

          So you open an alter account for div3?

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

    Sorry It's a typo that make me downvoted.

    I wrote E and F by mistake.

»
13 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Hardest Div3 ?

»
13 days ago, # |
  Vote: I like it +64 Vote: I do not like it

I shouldn't work out problems from back to the front.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

oh,how to solve tast D and E?It's too difficult!

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problem D:

    Since |T| <= 100, you can find all substrings.

    While finding the substrings, loop through each string s and see if it is equal to the current substring. If it is, store its index, start, and end in a vector. This takes O(N^3).

    Now you have a vector of segments. The problem then becomes: find the minimum number of segments needed to cover a line, in this case, T. You can do this greedily in O(N).

    For each segment left of the current position, find the one that goes farthest right. Keep doing this until you reach the end or it's impossible to solve this case.

    My submission

    Sorry if if the implementation is bad. I was rushing.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i do the same but not think greedly how to take minimum of them Thanks for sharing your submission

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

      Nice approach. I didn't think about this. I use DP instead. :')

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can u please explain your solution.

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

          Let $$$dp_i$$$ be the minimum required string to color string $$$t$$$ where letters at $$$t_i$$$, $$$t_{i+1}$$$, ..., $$$t_{|t|}$$$ are going to be colored (all the letters from $$$1, 2, ..., i-1$$$ must already been colored)

          Then I will try all possible $$$s_j (1 \le j \le n)$$$ that can fits position $$$i$$$ (in other words, I will try to color $$$t_i$$$, $$$t_{i+1}$$$, ... $$$t_{i+|s_j|-1}$$$ using the selected $$$s_j$$$). To check which $$$s_j$$$ match, I use a simple pattern matching logic

          Then for the transition for the next $$$i$$$ (call it $$$i'$$$), I will pick such starting index so that all the letters between $$$1$$$ to $$$i'$$$ already colored

          In other words the value of $$$i'$$$ lies between $$$i+1, i+2, ..., i+|s_j|$$$. I pick those who gives minimum value and construct the answer.

          Therefore : $$$dp_i = min(dp_{i'})$$$ for all possible $$$i'$$$

          You can look at my submission for more details

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

      Grassypotato Awesome bro !! I had the same approach but struggled with implementation. My friends told me that it is dp and I was about to give up when I saw your comment.

      Here's my implementation greedy approach. The problem basically simplifies to finding minimum intervals to cover entire text.

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

      Oh god, I was thinking that you have to choose the substring covering the highest amount of still black characters and struggled to find a bug in my code, thank you for the explanation.

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

    Problem E

    If we add the first digit a certain amount of times, we always get 2 as the last digit

    • 11 + 1 = 12
    • 12 + 2 = 14 + 4 = 18 + 8 = 26 + 6 = 32 (see this)
    • 13 + 3 = 16 + 6 = 2 2
    • 14 + 4 = 18 + 8 = 26 + 6 = 32
    • 16 + 6 = 22
    • 17 + 7 = 24 + 4 = 28 + 8 = 26 + 6 = 42
    • 18 + 8 = 26 + 6 = 32
    • 19 + 9 = 28 + 8 = 36 + 6 = 42

    The special cases are 0 and 5, because

    • 10 + 0 = 10 + 0 = 10...
    • 15 + 5 = 20 + 0 = 20...

    So if any number has a 0 or 5 in the last digit we must check if all numbers with 0 as last digit are equal, and if the last digit is 5, we must add 5 and check again that all are equal. If a number doesn't have 0 or 5 as last digit, we can't do it.

    If not we increase every number to have a 2 as last digit and check if all a[i]/10 (the number minus the last digit) have the same parity.

    The reason: if you look in the examples, secondly we have 12 to 32, and to go from a digit 2 to the next digit 2, we must add 20, if we ignore the last digit (as we do in a[i]/10) we must add 2.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the idea, I couldn’t come up with the last steps :)

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "If we add the first digit a certain amount of times, we always get 2 as the last digit"

      Actually, the digits 2, 4, 8, and 6 will all work for this.

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

      I also applied the same approach, because after solving certain amount of questions which include a huge role of last digits in a number , a similar pattern is observed after executing few steps. In this case it was 2-4-8-6. Well it doesnt happen always but ya most of the time ig.

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Please do a STRICT PLAG CHECK. According to me, D was quite tough , 2k submissions seems fishy

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually it isn't once you realize that it is a variation of merge intervals problem.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's heavy implementation problem. Also A, B, C (and probably E) were really fast to implement once you got the right idea. So, in my opinion, that's why problem D got so many last second submissions (I've spent around 1 hour 30 minutes writing + debugging it and only got AC after the contest).

»
13 days ago, # |
  Vote: I like it +31 Vote: I do not like it

Why is C SAME as 1462C - Unique Number!?

Only difference is that in contest today x $$$<=$$$ 45 and not x $$$<=$$$ 50.

»
13 days ago, # |
  Vote: I like it +10 Vote: I do not like it

I think number of a div increased by 1 accidentally

»
13 days ago, # |
Rev. 4   Vote: I like it -15 Vote: I do not like it

Another Div 3 which I'm going to downvote. Authors think that they are preparing problems for Div 2.

D — good idea but shit ton of implementation.

E — couldn't solve but I think it's some casework which I absolutely hate, hence didn't bother.

Also, C = https://codeforces.com/contest/1462/problem/C. wtf?

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

    E is just being able to observe a certain pattern that arises when you keep applying the operation on a number.

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

    E is not about casework but observation

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

    E was a great problem that taught you about cycles without having to go into any implementation

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    C could also be done using recursion ,just have a set of numbers from 1 to 9 and generate subsets with each subset representing a number and just check whether the minimum number which satisfies the condition.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I submitted question E in the last three minutes and passed it successfully

»
13 days ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

isn't G just a simple dfs solution ??

»
13 days ago, # |
  Vote: I like it +7 Vote: I do not like it

I hate all those people who are expert or more and do not participate with their main account, But after all this was a round that I didn't like(just my opinion)

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

may i say this round is just a piece of shit ? div3 seriously?

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 1714E - Add Modulo 10?

This is my submission. I have feeling I am either very far away from solution or like one line away from solution.

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

    So basically there is a cycle of ones digits, and if u keep adding u will eventually enter 2, 4, 8, 6 etc, which is a cycle of size 20. You simulate for every number until it reaches the digit that you choose, 2, 4, 8, or 6, and the difference between all numbers must be divisible by 20, due to the cycle. The other case is 5 and 0, which, if it's a ones digit with 5, u add the 5 and see if all the values are equal, because the 0 can not change the number.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Keep applying the operation on a number. Notice the last digit. The following pattern always occurs- 2 4 8 6 2 4 8 6... when the initial value of the number isn't divisible by 10.

    Notice that the number gets incremented by 20 every 4 operations (Except when its initial value is odd.)

    Use this to determine if it's possible to make all the elements equal.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Take a look at Ticket 15967 from CF Stress for a counter example.

»
13 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Why is D so much implementation???

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I have observed that number of submissions during last 10-20 minutes is too much high. Especially in this contest, I saw that submission rose too much.

Is this an indicator of cheating or are these really clutch submissions?

Also I don't understand how can problem E have more submissions than G. G was so straight forward, E atleast required some property of functional graph and heavy implementation.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought g was straightforward, which is why I started to work on it before E, but I couldn't implement a correct solution, so I went to E since it is mathy.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Am I the only one who overkilled G with k-th ancestor and binary search stuff? I supposed there had to be an easier way but I didn't think about using lower_bound on a stack. Well, at least I solved it...

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    E probably had more submissions just because it came before G and people assumed it would be easier.

»
13 days ago, # |
  Vote: I like it +10 Vote: I do not like it

U THINK F INTERESTING ? I came up with it in 5 minutes and get WA on pt 2 all the time lol

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1714/submission/166587546 this is my solution for d can anyone tell me please why it is wrong

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Huge gap between C and D

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

166589237

Can anyone tell why it is failing?

edit: nvm, got it

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

    That's too much of implementation. You can solve it easily if you measure time only in minutes

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my D giving MLE? 166596216 Will there be any more space efficient solution.

»
13 days ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

did someone notice that problem A — 1714A - Everyone Loves to Sleep was difficult than normal A problems

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved ABCDE, got too tired to think about F or G lol.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I wasted approx 45 minutes solving D and implementing it was a hell . but it gets TLE and from the submissions it looks E was easier than D.

Can anyone guide me how to improve my rating as i am stuck here since very long

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    E is implementation aswell, I don't know how did it got that many submissions, wait till hacking phase finishes then judge

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      E was not implementation, it was based on the observation that digits other than 0 and 5 cycle every 20. I feel like E there were a lot of cheaters, I saw it jumped ~600 AC in the last 10 minutes.

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I almost want to give up,but I figured out question E in the last three minutes.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      there was a very small error in my D which lead to infinite loop feeling very frustated as i could gain some rating but sadly not this time too happening last 4 rounds as i keep on loosing my rating and look like this time i will again become newbie

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Are hacks rated?

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

 Missed my AK~

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D my solution during the contest in c++20 link got WA in test case 1 but later got accepted in c++17 link Why is this happening?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You probably got lucky. For example, on CF Stress, your code fails on this testcase: Ticket 15965 (Although it'd pass on CF. Probably some uninitialized value access).

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved B and C, got stuck at A !!!!

Any hints for A ? Stuck at test 3

My Submission

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

    Convert times in minutes. Determine what happens if the current time is before/during/after each alarms and compute in minutes the difference of the current time and the alarm. Output the minimum difference in hours-minutes format.

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

    It will be easier if you convert everything to minutes and then output $$$ans÷60$$$, $$$ans$$$ $$$mod$$$ $$$60$$$ .

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    (diff1.second + diff2.second) could be more than 60 so you should add (diff1.second + diff2.second)/60 to (diff1.first+diff2.first) and make (diff1.second+diff2.second) = (diff1.second + diff2.second)%60;

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it would be better convert the time into minutes and then try solving, output the minimum of the difference of alarm time and sleeping time, difference cant be negative so if the time in minutes for the case of alarm is less than the time at which he sleeps, subtract 1440(24*60) from his sleeping time

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Take a look at Ticket 15964 from CF Stress for a counter example.

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

Amazing trick for looping through array or string backwards (used in todays B):

for(i=n-1; ~i; i--)

If you use ~i it will return false for $$$i=-1$$$ and true for all other $$$i$$$.

»
13 days ago, # |
  Vote: I like it -8 Vote: I do not like it

I should've attempted G first!

»
13 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Problem D = debugging infinite loops for an hour, at least thats what I felt and still couldnt find out whats causing it

Thats what happens when you nest while loops

and problem G, which I would have solved in 20-30 mins on LC using the standard recursive dfs approach, I didnt do it because I knew it wouldnt pass and idk how to implement that iteratively. Thats why my 2330 LC rating using pure python wouldnt matter here lol :/ same for two of my friends who used python only have 2400+ LC and 5 stars codechef but couldnt hit expert on cf

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Wait, am i on next level or smth? Why so many people talk about A being harder then usually? Is it really that hard to observe, that you need to sum this day time left and new day time if m < M? Or what is the difficult?

No offence to ones who didn't solve it, but i am really curious.

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

    Usually A is one simple observation, and simple implementation. For this one you had to consider multiple cases and also figure out a way to quickly convert the hours into minutes and back again.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Its just that, its a little bit confusing/harder to implement than B & C in todays contest.

»
13 days ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

In today's contest, these two users have the exact same code for problems E and F (the slightly harder ones), Chahel and goelarnav12. Please take action, as this is against the spirit of individual competition and is blatant plagiarism.

In fact, this is goelarnav12 's second offence. This user has plagiarised in the past. You can look at the "skipped" submissions. Kindly take strict action against these people.

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

So, I registered, participated. Couldn't solve a single question. Bahaaha, almost hysterical.

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone explain the dp method for problem D? Thanks in advance

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Neal wu did dp, hope he posts a video on this round

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone try hacking my D? (https://codeforces.com/contest/1714/submission/166556061) Feeling paranoid now since I'll finally get to expert with this round probably, but seeing a lot of TLEs.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "I want to get expert. Can somebody please prevent me from getting expert?" lmao

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      All submissions will eventually be tested against hacks anyways, so I'd just like some confirmation so I can celebrate/grieve in peace.

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

What are the hacks for problem D?Can anyone provide some test cases since there are no points for hacking in div3 round.

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

someone please help me in G my complexity is o(2*nlogn) but I get TLE submission : https://codeforces.com/contest/1714/submission/166597686 basically for every node , I increment the b as much as I can

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If your tree is a path then height is no lomger log(n) and your time complexity hits O(n^2).

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tought it is still o(n) , like A traverses the tree and B comes afterwards , so there are a total of 2 traverses , what is wrong with that ?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When you have a long path with short sum of b's for vertex v, which has a lot of children each requiring adding up all b's, yours becomes O(n^2).

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

      freehandle I didnt get it , can you giva a case , I will run jt on my machine too see how many operations does it make , btw I want to point out that : if vertes V's ancestors b is k , then to start searching for V's b , we will start the search from k , so it wont start from the root for every node to find their b's

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

        Exactly what I wrote is the case. Start a path with a = 1, b = 10^8, make a long path of length n/2 with a = b = 1, then make n/2 children at the end with a = 10^9, b = 1. For each children, you have to add up n/2 b's.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the point of such tasks as C? The stupidest precalc (166535760) solves them.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my submission for Problem D failing on test 5? 166614128

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    1
    abababac
    2
    aba
    bac
    

    Your solution outputs 4, but you can solve it in 3 iterations (1 1; 1 3; 2 6).

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C using recursion 166615609

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It can also be done with bitmasks.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

»
13 days ago, # |
  Vote: I like it +2 Vote: I do not like it

In E Problem, I thought that if the last 2 digits are the same, those values can become the same after some finite operations, but it is giving WA. Can anybody help why my solution is wrong

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

Why am getting TLE in question B?

Trying to do it O(n) only :[

Solution

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

    You are failing this test:

    $$$t = 10^4$$$

    $$$n = 1$$$ for each test

    And for every testcase you create $$$10^5$$$ array, that means you do $$$t \cdot 10^5 = 10^9$$$ operations

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

    There are a few optimizations for your code. Don't use vector<int> freq(200001, 0). You can use map<int, bool> freq or set<int> freq.

    You might be thinking: but I cannot use those data structures because freq[a[i]] can be $$$2$$$. You actually can if you first check if freq[a[i]] == 1 (in this case same as freq[a[i]]) and if it isn't then increase freq[a[i]] by $$$1$$$.

    This way time complexity is $$$O(NlogN)$$$ because grabbing elements in std::map takes $$$O(logN)$$$ and std::set.count() also takes $$$O(logN)$$$.

    Your accepted solution using std::map: 166667859.

    Your accepted solution using std::set: 166668032.

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

      Or I can just declare a vector of size n+1 as i did in this solution solution

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

        Yes. With map and set you use less memory, though.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I highly recommend watching neal's explanation for problem E if you don't know how to solve it.

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

It seems like I faced the same issue as some other people with F. Got Runtime Error on 2nd test case. I suspect it had to do with the case $$$n=3$$$ (from my own testing).

Happy to get E early though!

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Did anyone noticed that lots of the hacked solutions for D have almost the same code ?

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what's wrong with the problem E? This is my code here.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When a[i]%10==2 for all i, f doesn't get set

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If a[i]%10!=0 or 5, then all a[i] can be transformed into a[i]%10==2 by using the operations. In my code, f means if a[i]%10==2 exists, then if there is another a[i]%10==0 or 5, the answer should be no.

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

        Yes, f is meant to indicate whether a[i]%10==2 exists after the transformation, but f is not being set when a[i]%10==2 for all i in the original array.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the solution for. problem E??

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    There is a small observation.Say the current number is x. If x%10 is 2, and you perform operations you get a series. 2->4->8->6->2 so after performing 5 operations from any of these numbers you get back to the number itself with a sum of 20.Now suppose x%10 is 1,3,7 or 9. again if you perform one operation you reach 2,6,4,8 respectively.So the numbers become a part of the series.Now the only numbers which cannot be a part of these series are 0,5.So there are three cases.

    1. The array has numbers of the form 0,5 and at least one number from rest of the numbers.In this case the answer is No.
    2. The array has numbers only of form 0,5. In this case for the numbers having x%10=5 do the operation once.Now all elements end with 0 in the array, so no operation can be don further.Now all elements in the array must be equal for an answer to exist.If all elements are equal answer is Yes.Else answer is No.
    3. Now if all elements are of the form 1,2,3,4,6,7,8, or 9.For numbers having 1,3,9 do the operation once.So now all numbers are of form 2,4,6,or 8 in the end.Now as mentioned we can add 20 to any of these numbers without any issue. So we add 20 to all numbers such that the difference between all numbers of 20 is within 20.Now we try to make all elements of this array equal to the maximum element of the array using operations on each of the element. suppose the maximum element of the array is 38, We would try to make all elements of the array equal to 38 46 52 or 54.If is it possible to make all elements equal to any of these elements answer is Yes else answer is No.Note :we are not checking for 58 as if we can make all elements equal to 38 we can also make all elements equal to 54.

    For implementation details check this out 166574350

»
12 days ago, # |
  Vote: I like it +10 Vote: I do not like it

HAVE BEETHOVEN97 DONE MOST HACK IN CODEFORCES HISTORY?

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

    Hacking is not a very easy thing to do, it takes patience to look through everyone's code and attempt to hack it, and hacking so many solutions in every contest is pretty impressive. The man's a legend and i hope he doesn't stop.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

"Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you."
Does this mean I could get some points from this contest if my rating is less than 1600?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my first submission of problem A wrong answer but passed the hack?

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem D can be treated as a graph problem and can be solved by greedy and DFS or similar. Just store the adjacent strings that satisfy the condition, making it a directed graph, do BFS, and backtracking. Though the implementation is awkward and the cases are trivial at least to me LOL. Checking out this solution if you want. 166652986

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

    never thought about it that way, thanks for the info, I will try bfs with the shortest path and see what happens, correct me if I'm wrong, although we can create the adjacency list here, it will probably TLE for a larger constraint, right?

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

When will ratings come?

p.s. hopefully i get pupil :3

edit: yay i am pupil now :)

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why Rating not updated yet?

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

Hello everybody! Can anybody tell me why my E problem changed it’s green color to red? Yesterday during the round it passed all tests and got “full solution” status… I suppose that it’s connected with “hacks” but I am new here and still barely understand the matter of that word.

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

    Well, maybe it was a system mistake, now everything is OK. But I still don’t mind if anyone explains me what is “hack”:)

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

    A successful hack is when someone finds a test case where a given code doesn't give correct output. After hacking phase is completed, all test cases from successful hacks are tested against all solutions of that problem.

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

deleted

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why am getting TLE in G link: https://codeforces.com/contest/1714/submission/166682000

the dfs is supposed to have TC of O(2*n)

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

    This solution is not actually O(n) since the two pointer system goes back.

    Imagine if the current position was 50k and the pointer was at position 1,

    Now you enter node at depth 50001 and the value is large enough to allow the pointer to move from 1 to 50k, that needs 50k operations, now you get to the end and go back in dfs to 50000, the pointer is back at 1 and when you another node at depth 50001 with a large value the pointer needs to move back to 50000 again.

    Worst case performance is (n^2)/4 or O(n^2) giving TLE.

    Edit: If you take a look at the test case that fails you can notice that the pointer will be stoped at value 1 while the tree continues going down in a tower with small values. At some point the values will become large again and the pointer will need to move back down a lot of times.

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

      But still the pointer will not visit any node twice right? Suppose we are at noode root then in all subtrees of root the pointer will only visit to the depth only once.

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

        This is not correct, when going from root to 50k the pointer will visit all nodes, when the dfs goes back the pointer will return to 1 and can visit the same nodes again.

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Ok i will dry run it on few tc Thanks for explanation

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

      Hey your explanation was great could you also review this ? https://codeforces.com/contest/1714/submission/166712292 thanks in advance

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You seem to have a similar issue, the while loop inside your function that moves the pointer behaves in the save way that caused the issue I described above.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi I had appeared for Codeforces Round #811 (Div. 3) yesterday i.e. 01-08-2022. It was going great for me, having first two questions too quickly as per my timings, later on I managed to do 2 more questions during the contest. Also later on after the contest I completed a further one more problem. I have my candidature disqualified because some people coincidently have similar codes to mine. I have not checked their codes but I saw they were sort of bot profiles, they appear for no contests, registered for years , and somehow have similarities with me. I am a regular contest taker at codeforces and had landed a great ranking this time according to me atleast , I request to check out the issue and give me back my candidature according to the number of questions i completed and increase the rating accordingly , it was an easy 2800s something rank and i was absolutely mesmerized and now this . Solve this asap

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

    I have not plagiarised neither given code to anyone , I can guarantee these codes were mine with confirmation as my writing style and anyone can confirm the same because I have the code wrong submission multiple times which also explains it was me who was trying to solve the problem and other's comment to this post i can say , some bot accounts are creating havoc for us who do solve honestly but copying our codes somehow , you need to crackdown against them , because some cheaters are messing with many people , you can see for it for other participants of the contest too I would be waiting for further communication

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

      @MikeMirzayanov I would looking forward to your help

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

        MikeMirzayanov any help?

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

          i dont know how they found my codes even as i didnt gave them or anything like cheating but you can check i submitted the codes first in time then somehow they managed to get them , i believe its issue on codeforces side, somehow somethings wrong and i am getting crushed , help

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Does someone know what is test case 354 from test 2 at problem F?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

My submission for G was considered as plagiarism even though I don't even know the other person. Compiled and tested solution locally. Please look into this MikeMirzayanov

https://codeforces.com/contest/1714/submission/166555725 https://codeforces.com/contest/1714/submission/166575418

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

    anything happened? is the issue resolved , i too have the same problem and got all my code plagiarised

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

Attention!

Your solution 166560427 for the problem 1714D significantly coincides with solutions aldol_reaction/166560427, Cx330_L/166571248. 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.com/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.

MikeMirzayanov Hello, the main function part of my code comes from https://blog.csdn.net/mashizuren/article/details/113345347

Me and cx330_ L is not consistent. I use KMP and he uses bruteforce. In interval merging, we use the merging method of this article. You can see that my code style is always the same for all the topics in this field. Please restore my place and return my score. I didn't cheat.

my: https://codeforces.com/contest/1714/submission/166560427 his: https://codeforces.com/contest/1714/submission/166571248

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

    anything happened? is the issue resolved , i too have the same problem and got all my code plagiarised

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

      He didn't plagiarize my code, we just refer to code from a same blog that was posted before. The problem is not solved.

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

        mine is a bit different then i believe , all my codes are plagiarised somehow , i dont know how they leaked even as i didnt upload them anywhere ;-;

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

MikeMirzayanov Hi I solved abcd I have got plag on A why i cheat in A lol how I cheat A and solve BCD? please look at this thank you

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

    same bro , if your issue is resolved do reply and tell me what can i do to get the issue fixed as well

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

My code is not working for a particular test case. Can anyone check! Thanks here's my solution: https://codeforces.com/contest/1714/submission/166584533

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Your second last for loop misses the final element (the condition should be i < n). It gets AC after fixing this.

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

      You're a lifesaver, man I wasted so much time on this.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone look and tell why is my solution for G is giving RTE for testcase 3? 166727901

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

    Recursion depth exceeded would be one issue you cannot just do recursive dfs directly

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

Edit 1 : Thanks, I figured it out...

Can anybody kindly help me with this https://codeforces.com/contest/1714/submission/166761762 , this is my code for G which getting memory limit exceeded on test 3, I think either the way I am making the graph is taking more memory or the vector for B_i's I update everytime in dfs is taking alot of memory but I can't figure out how to do the problem without using the vector for B_i's and if anybody can see the tutorial kindly send me the link cause I can't see it (maybe its not out yet...).