vovuh's blog

Codeforces Round #674 (Div. 3)
By vovuh, history, 4 years ago, In English

Notice the unusual start time.

Hello!

Codeforces Round 674 (Div. 3) will start at Sep/28/2020 11:05 (Moscow time). You will be offered 6 or 7 problems (or 8) 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 rating 1600 or higher, can register for the round unofficially.

This round consists mostly of the problems of the first stage of All-Russian Olympiad of School Students in Saratov and will be hosted during the real competition time. The problems were invented and prepared by Ivan BledDest Androsov, Alexander fcspartakm Frolov and me.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours 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 participants of the third division, you must:

  • take part in at least two 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 my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

UPD: Thanks to Ivan MrReDoX Ushakov, Ivan Ivan19981305 Georgiev and Dmitry nuipojaluista Kadomtsev for testing the round!

UPD2: Editorial is published!

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

Comments Comments (117)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +35 Vote: I do not like it

*Notice the unusual start time.

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

I think vovuh should update the blog mentioning unusual start time.

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

weird time tho

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

Sorry cannot participate because of the practical class at the same time

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

Me Also. xD :) (SAVE_20200927_1219521f486f74dbb24105.jpg)

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

Why so unusual start time ?? :(

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

    "This round consists mostly of the problems of the first stage of All-Russian Olympiad of School Students in Saratov and will be hosted during the real competition time."

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

      I See, its going to be fun then!!!!!!!!!

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

So unusual time. Its lunchtime here in India.

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

All-Russian Olympiad alright imma skip this one

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

Me after remembering the previous div2 contest based on russian Olympiad for school students: i am gonna skip this because of unusual time.

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

    Its Div-3 bro, what do you got to lose, its unrated for you

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

really wanted to participate but wont be able to due to my online classes.hope for some magic

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

Really excited for this contest, but it's unusual time is not suitable for most of the college students in India as we have online lecture at that time.

→ Reply
»
4 years ago, # |
  Vote: I like it -75 Vote: I do not like it

submit F in last 5 seconds and find my output is following:

YES
1 1 1 1
1 1 1 3
4 2 3 1
RDLL
DRDD
ULUU
NO

instead of 

YES
1 1 1 1
1 1 1 3
4 2 3 1
R D L L
D R D D
U L U U
NO

Hope my solution is wrong XD

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

    Round is not even started yet, but u already submitted, Ur coding speed is so enormous!

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

      I miss the golden time in which I can delete the misplaced comment. T_T

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

    well looks like your wish came true xD

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

Deleted for posting at a wrong place.

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

Gonna wake up at 4 am(my local time) for this contest! Very excited!

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

Your text to link here...

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

Time too bad. Have classes. Any after 3pm UTC works fine.

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

Every time I want to improve my CP skills, my college is letting me down and this is another example.

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

It would be pretty good if CF were in this time rectangle in the future.

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

Another suitable time for Chinese......

But "based on" makes me afraid!

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

    I can finally have a CF competition and have not to sleep at 1:00 in China :)

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

Oops, sorry It was the wrong post :((

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +31 Vote: I do not like it
Spoiler
→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

vovuh score distribution plzz..

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

    There are no score distributions in Div.3

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

IN INDIA IT's OUR ONLINE CLASS TIME

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

    It's impossible to conduct a contest such that time will be suitable for everyone across the world.

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

This is the first time a div3 round is not rated for me!

idk i just want to share this

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

After a long time, a rated div3 for me :P.

glhf

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

2olj4n.jpg

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

How to solve F?

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

    we want to count the total number of abc, ab?, ?b?, ???, ??c, a?c, a??, ?bc subsequences occurring in all the strings, we can replace ? with the character that we need to make it abc. I've named variables for better understanding. In my code, k = count of ? so far submission

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

how to solve c?

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

    For this, I got a pattern of the required number of moves like 0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, ......

    Hope it will be helpful.

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

      Took time for figuring that out. Found editorialist solution more easy btw.

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

    Suppose we perform the +1 operation $$$x$$$ times and the duplicate operation $$$y$$$ times. Clearly we want to perform all the $$$x$$$ operations first, so that each subsequent $$$y$$$ operation adds as much as possible. Then the sum of the array will be $$$(1+x)+y(1+x)=(1+x)(1+y)$$$. We want $$$(1+x)(1+y) \ge n$$$, so each of $$$(1+x)$$$ and $$$(1+y)$$$ is either $$$\lfloor \sqrt(n) \rfloor$$$ or $$$\lfloor \sqrt(n) \rfloor+1$$$. Then we can just try the cases.

    94077437

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

      so each of (1+x) and (1+y) is either ⌊(√n)⌋ or ⌊(√n)⌋+1. Then we can just try the cases.

      i didnt get the last part how this is possible?

      and why the solution does not go beyond the root n thanks

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

        If we want to minimize $$$a+b$$$ and want $$$ab\ge n$$$, then we want $$$a$$$ and $$$b$$$ to be as close to each other as possible (just try a few values... it's very intuitive). That means each of $$$a,b$$$ must be around $$$\sqrt{n}$$$. In this problem, $$$a=1+x$$$ and $$$b=1+y$$$.

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

    it is better to increase 1 up to some number let say x and then append this x up to when the array sum becomes equals or greater than target value n

    here x should be the floor(square root of n) or 1 plus to this value

    here is mine solution 94092529

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

what was the testcase no 10 of problem D??

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

Can some one give me idea about B & D

thanks in advance

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

    for B: if any 2x2 tile has diagonal element same then answer will be yes, keep in mind that tile length and width is 2 so the the resultant square will be multiple of two

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

Problem F is exactly the same as ABC104 Problem D

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

How to solve D neatly ? I can think of one way where we count the disjoint subarrays with zero sum.

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

    Think of it as you have, say $$$k$$$ intervals (imagine as segments on the $$$x$$$-axis, from $$$interval[i][0]$$$ to $$$interval[i][1]-1$$$) and each interval has elements that sums to $$$0$$$. Now basically, you need to find the total number of vertical lines to make, such that every segment is cut at least once. Implementation

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

How to solve D? went upto prefix sums and thought if prefixsum[i] is 0 or has already occurred then add 1 to the answer but it doesn't seem to work because segments can collide. Can anybody explain a neat approach?

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

    i counted all the segment that collides in one then also ans was coming wrong on testcase 10 anyone can explain

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 4   Vote: I like it +1 Vote: I do not like it
      • If you find subarray with sum zero ending at index i then you insert very big number between index i-1 and i.
      • Now you don't need to care about elements to the left of index i.
      inline void solve()
{
	ll n, i, s = 0, ans = 0;
	cin >> n;
 
	ll a[n];
	set<ll> st;
 
	for (i = 0; i < n; i++)
		cin >> a[i];
 
	for (i = 0; i < n; i++)
	{
		s += a[i];
		if (st.find(s) != st.end() || s == 0)  //there is case of zero subarray sum
		{                                      //So we increase our ans and
			ans++;                         //clear set and  make sum = a[i]
			st.clear();                   
			s = a[i];
		}
		st.insert(s);
	}
 
	cout << ans << endl;
 
}
      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    went up to prefix sums and thought if prefixsum[i] is 0 or has already occurred then add 1 to the answer — it's perfectly okay till now then you just need to clear your container and do everything that you need by assuming the current position of the array as the starting position. Hopefully, it will do your job.

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

    Think of it as you have, say $$$k$$$ intervals (imagine as segments on the $$$x$$$-axis, from $$$interval[i][0]$$$ to $$$interval[i][1]-1$$$) and each interval has elements that sums to $$$0$$$. Now basically, you need to find the total number of vertical lines to make, such that every segment is cut at least once. Implementation

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

Can someone help with with this submission? I could not think of a testcase that fails. 94110488

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

    your code will fail for when n=1 and X =1 Cuz (1-2)/1=-1 So else part will give -1+1=0

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

Did codeforces recently changed the rating formula?

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

    I dont know but maybe this might be the reason...the number of participants is less hence you may see less change in delta even if you have good rank.

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

      Yeah, I thought that I was really hoping to touch expert but nevermind I try next round.

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

        Yes and I wanted to be specialist..sed..next round.

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

        I followed you, and I think if you are not hacked, you will turn blue.

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

Excuse me! Why is E like A in terms of difficulty?

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

    The fact that it is E has psychological effect hence the number of solves is almost 10 times less then A..despite the difficulty level.

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

      Number of solves is 10 times less mainly because there are 3 more questions between A and E which people attempt, and mostly move ahead only when they are done with those.

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

    There is a general thing. People can solve A because its A, people cant solve E even if its easy cause thats E

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

There is a question: I did not participate in this round because of something. If I hack someone, will I be rated?

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

I started the contest half an hour late... yet managed to solve A,B,C,D ! Today was a good day for me!

Thanks vovuh for the awesome round :)

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

    Why good day? You managed to get lot of penalties with better performance due to be late

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

Today's Div. 3 (Round #674):

Spoiler alert for those who are thinking to give contest (virtually)
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The advantages of being a Chinese have been revealed ：） The start time is 16:05 for me.

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

Is there any benefit for successful hacking, in this round?

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

Why don't we go beyond sqrt(n) in problem C ?

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

is there any point for hacking in div3?

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

Can anyone tell me on what test case my solution for B fails? It is hacked. Here is my submission.

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

Can someone explain how hacks work for ICPC-style rounds like this one? Is there any competitive reward for successful hacks?

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

Hands down the best contest I have participated in so far!

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

Can anyone explain how this works:

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

I see xin_chen, CupCapCup and midheight at places [3, 4 and 5] accordingly. But that doesn't seam right: Their places are increasing but their (finish time + #WA * penalty) is decreasing >> [ (55 + 4 * 10) == 95 , (70 + 2 * 10) = 90 , (62 + 10) = 72] Plus, their number of WA decreasing: [4, 2, 1] but Penalty is increasing: 188, 193, 199 — it could make sense if their finish time was increasing, but it's not the case.

How to make any sense of it? Thank you in advance.

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

    The penalty of xin_chen is: 2 + 9 + 13 + 27 + 42 + 55 (number of minutes since the start until the task is solved) + 4 * 10 (for WA) = 188

    Hope that will make it clearer

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

      Wow, Super! Thank you, that made everything clear.

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

Why my rating is still not updated?

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

Will it not be rated for untrusted participants? As my ratings haven't changed yet, being < 1600 and already 5+ hours have passed after the end of the hacking phase.

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

    This is because they might be working on the plagarism tests now and removing the cheaters.

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

As I am new to Codeforces so can anyone tell me that in this contest will I get any rating or not because I have solved the 3 questions but and also got my rank but not any rating and even in my contest section it is not showing anything.

please help me out?

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

When are the ratings going to update for this round?

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

Why hasn't the rating updated after the contest? it's almost 24 hours now...

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

When the ratings will be updated?

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

Hi everyone! Can someone please help me with this solution from ecnerwala. How did he find max-flow in non winning edges in the code here — https://codeforces.me/contest/1426/submission/94072786

How did he arrive at that one liner solution? Just a little insight will be very helpful.

Thanks a lot

→ Reply