Monogon's blog

Codeforces Round #712
By Monogon, history, 4 years ago, In English

omg hi!

I am pleased to invite you to participate in Codeforces Round 712 (Div. 1) and Codeforces Round 712 (Div. 2)! You will be given 6 problems and 2 hours 15 minutes to solve them. I'm happy to announce the theme of this round is déjà vu!

I would like to thank the following people:

Make sure you read all problems, and I'm happy to announce the theme of this round is déjà vu! Good luck, have fun!

The score distribution will be announced immediately because you deserve it ❤️:

Div. 1: 750 — 1000 — 1250 — 1750 — 2500 — 4000

Div. 2: 500 — 1000 — 1750 — 2000 — 2250 — 3000

UPD: Editorial

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

Comments Comments (206)
| Write comment?
»
4 years ago, # |
  Vote: I like it +304 Vote: I do not like it

As a useful tester, give me contribution!

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

    As a useful tester and your amazing user activity profile, you deserve lot of contribution.

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

    As an ancestor of the "gon" family, I wish Monogon all the best for the round!!

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

    Can you please tell me solution of problem A-C.

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

    I will upvote only after seeing the problems in the contest :)

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

      Well be ready to click that green button then :)

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

As a tester, this bit is getting old.

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

As a useful tester, I can confirm that the problems are very high quality and have short and clear statements. All hail lord 1-gon! Also, contribution pls, thx.

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

As a useful tester and loyal Monogon supporter,

Reddit may have GME Stock, but we have Monogon's contribution! TO THE MOON, COMRADES!!!

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

As a tester, Its my first round I have tested, so please give me contribution :)

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

    so did you found this round interesting

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

      I can confirm that the round was awesome, well written statements and well balanced and interesting round

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

        But bro when I hover over your name on the testers list, it says "Useless Tester prabhAmbrose" :(

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

          In that case, you missed the real hovering

          Screenshot-20210402130610-1920x1080

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

            The blog does not have the only other hover text on this page ;)

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

As a tester, is anyone else tired of as a tester comments?

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

    As a tester, yes.

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

      Wow!!! First time seeing a dog testing round for humans ORZ!!!

      PS: Why downvote if you don't know the context, Nika helping me hard to get upvotes :(

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

omg Monoannouncement! Will you reply to this comment :pleading_face:

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

.

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

As the first person to register, I spent 5 minutes waiting for the registration to open. :( That's a 5 minutes I'll never get back, so give me contribution!

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

    While we sleep, he spams F5

    While we eat, he spams F5

    While we solve problems, he spams F5

    While we spam F5, he spams F5...

    give him contribution already

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

Why do I feel like, I've been here before ?

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

as a future participant to this contest, i wish to everybody good luck!!1!! I hope you all get rating increase!1!!

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

I hope the deja vu plot isn't a part of April Fool's Day,lol!!

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

How to become tester?

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

I would like to see a trend where every Monogon's blog's comments will have crazy high upvotes (even is it rated? comments).

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

Having a weird feeling that 712 has happened before :)

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

How to become a contestant?

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

I'm happy to announce the theme of this round is déjà vu!

So there will be problem on recursion

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

oh man when we select the statement antontrygubO_o for accepting all of my problems we see antontrygubO_o for accepting all of my problems at gunpoint

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

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

    You'll solve C so fast that you become The Flash?

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

    If it fails on FST, you will have new kind of head pain added to your list. (＞..＜)

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

    Your profile picture makes it even funnier XD

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

I was very confused about how Anton accepted all the problems.

Then I double-clicked on the line and I was relieved.

Then I clicked on Anton's profile link and I was relieved again.

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

14
post pictures

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

.

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

I am going to be green after this round. Give me Contribution.

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

My first CF round

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

    First cf round ,that too of mongon. All the best.

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

Hope to solve at least one problem :)

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

do you guys noted this thing?

Screenshot-2021-04-02-at-1-24-39-AM

for those image is not loading : image

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

As a person I love the CodeForce community. Give me a contribution ..

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

How to be a useful tester

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

Why is 3rd question 1250 in Div1 and 1750 in Div2? In score distribution

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

    Because the authors would like it to be that (Or maybe not?) .

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

Great! I'm going to participate in this wonderful round((

I hope everyone here gets high rating!(at least higher than me)

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

[deleted]

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

Deja vu

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

1-gon orz

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

Really excited for the theme xD

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

As a useful tester, I am certain Monogon deserves to have more than $$$200$$$ total contribution for this round is just perfect.

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

Me trying my luck for the contribution giveways.

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

Will Déjà vu! theme challenge this equation?

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

Its funny, the first thing that hits my head when I see a Monogon contest is not his penchant for contribution but that his first contest was made unrated cuz of queueforces. And now that he announced that the theme is deja-vu ... <cold face emoji>

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

the enthusiasm in this blog is on another level 0:)

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

Monogon + déjà vu == Unrated contest?

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

after a long leave , i' back,I will participate the contest,hope a nice problem,ovo~

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

Is it rated contest?

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

    If you see a contest named 'Codeforces Round #...' , then it must be rated.

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

Sadly it is clashing with leetcode biweekly

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

Monogon orz

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

Solid A I guess.

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

I didn't expect that SecondThread will make a video to upvote the post. That's great!!! I had already upvoted the post before watching the video .. DOUBLE CHECK!!!!!!

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

https://youtu.be/Oqew3Y2CNqg 1-gon please reply if it's you ?? Thank you!!

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

I'm happy to know that the theme of this round is déjà vu!

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

So excited to know that the theme of this round is déjà vu!

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

USA is an actually a good country :D

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

I like problems selected by antontrygubO_o

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

The first time I jion into Div.1 !

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

Monogon problems so great so antontrygubO_o couldn't reject any of them! orz

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

    I wonder how many notifications orz gets per day bcoz of unnecessary tags.

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

Пересекается с открытием и пробным туром nerc(

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

All the best guys. I hope to reach pupil.

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

My 200th round is going to be monogon round.

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

Hope the questions stand up to my vote.

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

I think C will be much more difficult than B, as there is large point difference between B and C.

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

Can I have my upvote back ..

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

Good round and interesting problems time to upvote the blog and the tester's comment's ")

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

[deleted]

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

I'm going to become Specialist First time. :) what a feel !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! :)

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

    Hurrrahhhhhhhhhhhhhhhhhhhhhhh.. And now I'm Specialist !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! :)

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

Nice problems. But was D really tougher than C?

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

    Quite easier than C

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

    Maybe this is why I should read all problems... Got stuck on C for so long :(

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

    I think it was placed there because it was interactive

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

      Yes probably. But given that almost every second contest nowadays has an interactive problem, I think most people are comfortable with them and just being interactive shouldn't increase the problems difficulty.

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

    The idea was easier for D, but D took me longer to code up because there were more places to be careful about edge cases. Besides, putting an interactive problem too early in the contest may ruin it for some people.

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

why isn't there any stream after contest today? Isn't stream always there after a Div2 contest?

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

    Probably cuz there is a concurrent div 1 at the same time.

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

C and D were nice problems. Although I did find D easier than I thought.

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

Electricity gone contest start after 3 minutes and come back almost after 30 minutes but i stil come back of monogon sir contest. uuhhhhhhh

Thanks Monogon sir for the nice problem-set. ;-)

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

Maybe a silly question: why did D2 have empty lines between the inputs?

Even with the sample input, I think this should be clearly mentioned in the statement. Specially for interactive problems that are not as easily testable before submitting.

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

    I think it's just a mistake in the sample input. My solution was accepted and didn't read or write any additional newlines.

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

      I had a runtime error in my first submission (I suspect due to attempting to parse the empty line into an integer), so I am pretty sure the pretests did include the empty lines (as can be seen in the sample input).

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

      Empty lines in sample exist to distinguish the order of input and output. Not a mistake.

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

        Could you explain? What would happen if there were no empty lines in the input?

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

          That input means 'After reading all input, then print all output, including empty line.'

          Basically, if you match the sample output and sample input, you can see that it is a perfect fit.

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

    Might be I might be missing something... Can you help where I've gone wrong. Submission-111933010

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

      you can't have ios_sync_with_stdio(0) and the other 2 lines in an interactive problem. And also try '\n' instead of endl for printing. And also the complexity can be a problem, i am not sure if 1e8 operations (because you have O(n^4)) in an interactive problem are done in 3 seconds.

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

        Not sure about all that, but my code with fastio, endl, and 1e8 operations passed the main test also.:)

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

      Is your code guaranteed to print something on every round? Structurally it looks like if the "if" condition isn't met you don't publish anything, and attempt to read the next input while the checker is still waiting for your output for this round.

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

        According to me it should print in each round, but there might be some cases which are not covered, that can be a reason..

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

          You can add exit or print random words in those cases that should be unreachable, and see if that idleness error turns into wrong answer.

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

just about to submit D , Message pops out contest is over :(

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

    Unlucky, you will get D in your next contest, I am sure :))

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

      Thank you. And I just submitted My solution of D and it got accepted, Now it hurts even more :(

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

    same here buddy!
    i submitted after sys test and got ac.
    Now it hurts even more :( (2)

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

I could not solve C. I solved A and B.

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

Can someone explain how the interactor script was written for problem B? This is the first time I encountered an "adaptive interactor". It will be interesting to know how exactly it works. BTW, cool problem, although it felt waaaaay easier than Problem A.

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

    The input to the interactor is described in the "Hack Format" section. It sees a list of colors that Alice plans to say in order.

    However, if at any point the interactor sees that Alice can win by saying the same color for the remaining turns, it will deviate from the list of colors and just win the game. Since this check is a bit expensive, it doesn't check for this case as often in larger grids.

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

In my opinion, I think D is easier than C

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

What "wrong output format Unexpected end of file — int32 expected" this warning means for my solution for problem D? My Submission: https://mirror.codeforces.com/contest/1504/submission/111928362

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

Need help in problem C. Apparently tried n number of test cases but it says WA on test 2 :(((( https://mirror.codeforces.com/contest/1504/submission/111936720 this is my link to submission. Please help me out.

Thank you

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

Can Anyone Explain me logic behind Problem-B?

I use the following approach but I don't understand where my code goes wrong???

Please Help...

                ll n;
		cin>>n;
		string s1,s2;
		cin>>s1>>s2;
		bool f=0;
		ll k=0;
		vector<int> v,xr;
		v.pb(-1);
		int z=0,o=0;
		int z1=0,o1=0;
		for(int i=0;i<n;i++)
		{
			if(s1[i]=='0')z++;
			else o++;
			if(z==o) v.pb(i);
			xr.pb((s1[i]-'0')^(s2[i]-'0'));
			k^=((s1[i]-'0')^(s2[i]-'0'));
			if(s2[i]=='0') z1++;
			else o1++;
		}
		// cout<<xr<<endl;
		// cout<<v<<endl;
		if(z1!=z or o1!=o) 
		{
			cout<<"NO\n";
			con;
		}
		bool b=0;
		for(int i=1;i<v.size();i++)
		{
			ll prv=xr[v[i-1]+1];
			for(int j=v[i-1]+1;j<=v[i];j++)
			{
				if(prv!=xr[j])
				{
					b=1;
					break;
				}
			}
			if(b) break;
		}
		if(b) cout<<"NO\n";
		else cout<<"YES\n";
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    maybe you are not checking, whether the remaining strings are equal or not(after the last point where number of 1's equals number of 0's)

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

Worth upvoting!

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

Resubmited D because I had a simple test on which my solution wasn't OK, but it turns out that the testcases are weak.

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

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

    Anyone got lower delta like me after removing cheaters? :)

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

Got the idea of D when there were still 30 minutes left, but failed to finish it because of ignoring the case of multiple runs needed. However, if I finished it, maybe I would see my code fail on the simplest n = 1 case in the system test...so Madamashi maybe :)

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

Can someOne Please explain ,why I'm getting WA :( 111939707

UPD: Got it :)

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

jhfuy

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

    N must always be even, so the test you mentioned is invalid

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

Weak system tests in D.

I took the following approach: assume $$$1,2,...,n$$$ appear in distinct cards. Sort the cards by $$$\min(a_i,b_i)$$$ and let $$$x_i=\max(a_i,b_i)$$$ in the sorted sequence. If $$$i<j$$$ and $$$x_i<x_j$$$, exactly one of $$$i$$$ and $$$j$$$ should be on the front. So, if the length of the LIS of $$$x$$$ is $$$\geq 3$$$, there is no solution. Otherwise, construct an undirected graph with edge $$$(i,j)$$$ iff $$$i<j$$$ and $$$x_i<x_j$$$. The resulting graph will be bipartite and we can decide the number of flips individually for each connected component.

This undirected graph can have $$$\Theta(n^2)$$$ edges in the following test case. (Assume n is an even number and m=n/2) (nuip told me about this case)

1 3m
2 3m-1
...
m 2m+1
m+1 4m
m+2 4m-1
...
2m 3m+1

My submission 111924355 did not consider this and made every edge so it should get TLE, but it passed system tests. To avoid this I should have used two segment trees to reduce the number of edges checked in the BFS. 111942077

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

include<bits/stdc++.h>

define int long long

define fi first

define sc second

define pii pair<int,int>

define vi vector

define mii map<int,int>

define msi map<string,int>

define si set

define all(v) v.begin(),v.end()

define sz(v) int((v).size())

define rep(i,a,b) for(int i=a;i<b;i++)

define dep(i,a,b) for(int i=a;i>=b;i--)

define isinarr(i,n) ((i>=0)?((i<n)?1:0):0)

define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

define pb push_back

define ppb pop_back

define lb lower_bound

define ub upper_bound

define present(container, element) (container.find(element) != container.end()) //set,map etc.

define cpresent(container, element) (find(all(container),element) != container.end()) //vector

define hell 1000000007

define PI 3.14159265

define mp make_pair

define inparr(a,n) rep(i,0,n)cin>>a[i];

define strwspaces(s) getline(cin,s)

define give(x,y) cout<<x<<" "<<y<<endl;

define setp(n) cout<<fixed<<setprecision(n);

define endl '\n'

define inp(n) int n;cin>>n;

define inps(s) string s;cin>>s;

define setmem(inde,k) memset(inde,k,sizeof(inde))

define tr(a,m) for(auto a=m.begin();a!=m/end();a++)

using namespace std;

void solve() { int t;

cin>>t;
while(t--){
    int n;
    cin>>n; 
    string a,b;
    cin>>a>>b;
    bool check=0;
    int count0=0,count1=0;
    for(int i=0,j=0;i<n,j<n;i++,j++){
        if(a[i]!=b[j]){
          (a[i]=='0')?++count0:++count1;   
        }
        else if(a[i]==b[j] && count0!=count1){
        //    cout<<i<<" index";
       //    cout<<count0<<" "<<count1<<endl;
          check=1;
            break;
        }
        else{
            count0=0;
            count1=0;
        }
       //     cout<<"i="<<i<<" j="<<j<<endl;
         //   cout<<count0<<" "<<count1<<endl;
    }
    if(count1==count0){

           cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}

}

signed main() { // fastio

solve();
return 0;

}

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

    Can you at least put the code under a spoiler or something?

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

What is the approach for problem C?

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

for problem A: ans is NO when there's only 'a's in the string, otherwise maintain left half count(let say l) and right half count of 'a' (let say r). Then insert 'a' in the beginning if (l > r) else insert at last.

I am not able to find out the flaw in this logic. Can somebody point out please? :// My WA submission

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

    Check test case with baaba

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

    Why don't you just check if 'a'+s is a palindrome?

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

Is C solvable if $$$c_i$$$ can be negative?

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

    I thought about it but could not find a solution except for the special case where they are all negative, which is similar to the all positive case. If someone solves the general version, I would be interested to hear it.

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

    Yes. This harder version is almost identical to IOI 2016's Railroad.

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

why java code for problem C(Balance the bits) is giving TLE on test case 3??? the same code in C++ is running fine

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

Can someone tell me what is Test 64 (Test case 2) in problem C.

Thanks

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

Can someone please check my code for problem D, why am I getting (wrong output format Unexpected end of file — int32 expected). https://mirror.codeforces.com/contest/1504/submission/111982923

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

no contest in coming two weeks ,why!!

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

say along with me , "Hail monoGon"

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

why is there such a long gap in constest now ??

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

I made a video for up solving the round ( div2 without F ) with Arabic commentary here

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

Can someone help me with Problem D Div 2? I am getting WA on test case 6. 111982213

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

Attention!

Your solution 111886576 for the problem 1504B significantly coincides with solutions NO-COMPETITION/111886576, thegreat_6459/111901841. 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://mirror.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 recently i got a message from system I srsly dont know how my solution coincided with that person solution you can check submission times my submission is way too early than that guy submission its clearly a mistake

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

    the code is literally exactly the same: 111901841 and 111886576

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

      kwangg Yeah,i agree to that but sad part is in previous contest i got penalised and other person whose submission was late and i dont know how or why he changed language and submitted didnt get any penalty .Atleast,the person who submits first shouldnt be penalised.

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

As a useful tester and loyal 1-gon supporter

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

    I don't think you were a tester but as a supporter I am obligated to upvote you.

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

Nut for a jar of tuna.

→ Reply