Блог пользователя flaviu2001

Автор flaviu2001, история, 8 дней назад, По-английски

Hi Codeforces!

stefdasca, koala_bear00 and I are very excited to announce our first contest Codeforces Round #676, which will take place Oct/18/2020 12:05 (Moscow time). The round will be rated for participants with rating up to 2099.

The tasks were written by me with help from stefdasca and koala_bear00 and you have to help some of the authors' favorite musical artists to solve the problems they're faced with.

We hope we compiled a very interesting contest with memorable tasks :)

Special thanks to:

You will be given 2 hours to solve 5 problems, good luck everyone and have fun!

UPD 1: After the round you can watch videos explaining the solutions to the tasks on stefdasca's Youtube channel.

UPD 2: The round was rescheduled, because of intersection with other scheduled contests.

UPD 3: The scoring distribution is standard 5001000150020002500.

UPD 4: The editorial was posted and you can check stefdasca's video solutions aswell.

UPD 5: The round is finished, we are glad everything went smooth and hope you enjoyed our tasks!

Div1 winners (unofficial):

  1. I_love_Tanya_Romanova
  2. LJC00118
  3. kefaa2
  4. LayCurse
  5. uwi

Div2 winners:

  1. RGB_ICPC2
  2. _ztyqwq
  3. AnakMbah1937
  4. SakuraiMomoka
  5. asdsasd

Congratulations to those above and to everyone for participating!

 
 
 
 
  • Проголосовать: нравится
  • +561
  • Проголосовать: не нравится

»
7 дней назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Auto comment: topic has been updated by flaviu2001 (previous revision, new revision, compare).

»
7 дней назад, # |
  Проголосовать: нравится +81 Проголосовать: не нравится

i lost the rated contest again :weary:

»
7 дней назад, # |
  Проголосовать: нравится +224 Проголосовать: не нравится

As a tester, you know ... what I want :)

PS
»
7 дней назад, # |
  Проголосовать: нравится +79 Проголосовать: не нравится

As a tester, I would like to say "Good Luck everyone. Have Fun!!"

»
7 дней назад, # |
  Проголосовать: нравится +137 Проголосовать: не нравится

As a tester, I would like to say that I haven't seen the problem yet.

»
7 дней назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Notice the unusual time !
Good luck for your maiden contest !!

»
7 дней назад, # |
Rev. 2   Проголосовать: нравится -235 Проголосовать: не нравится

The blog is written $$$4$$$ days before the contest -> bad contest

»
6 дней назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

As a tester, I would like to say, good luck and have fun!

»
6 дней назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

What time is it? 18:35 or 21:05?

»
6 дней назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Auto comment: topic has been updated by flaviu2001 (previous revision, new revision, compare).

»
6 дней назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Auto comment: topic has been updated by flaviu2001 (previous revision, new revision, compare).

»
6 дней назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

It seems the blog text does not use the "Contest time" feature of the blog editor, like [contest_time:1421]

»
6 дней назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I expect that this contest can be held smoothly.

»
6 дней назад, # |
Rev. 5   Проголосовать: нравится +42 Проголосовать: не нравится

As a Romanian, I am excited to participate in a round made by Romanians!

»
6 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck to everyone

»
6 дней назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

if someone knows why there is no announcement of the Codeforces Raif Round 1??

»
6 дней назад, # |
  Проголосовать: нравится -31 Проголосовать: не нравится

bro can you change the time to 8:00 pm as per IST

»
6 дней назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

What is "Raif" in Codeforces Raif Round 1 (Div. 1 + Div. 2)?

»
6 дней назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Clash with codechef cook-off, but do we even care?

»
6 дней назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

What a great way to promote a youtube channel :D, JK,

»
6 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
5 дней назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

I am a newbie so should i participate in div2 or div3 contests Please help. i want to increase my rating seriously

  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Participate in both.

    • »
      »
      »
      4 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I only get notifications of div1 and div2 contests. till now i have not got even one div3 contest notification so that i can participate

      • »
        »
        »
        »
        4 дня назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Frequency of Div3 contests is lesser than Div2 so you should try to participate in every Div2 and Educational Rounds. Educational Rounds are good too.

        • »
          »
          »
          »
          »
          4 дня назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          oh thanks for the info, btw i saw some participants graph starting from 1200 and for some it was below 1200 , what is this method of starting and rating further

          • »
            »
            »
            »
            »
            »
            4 дня назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            Starting rating changed some time ago. You can learn more about it here -> https://codeforces.com/blog/entry/77890

            • »
              »
              »
              »
              »
              »
              »
              3 дня назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              hey today i gave a div 2 contest , i was only able to do the first problem(this was my first contest ever). the soln got accepted but in my account ,contest section its showing nothing

              • »
                »
                »
                »
                »
                »
                »
                »
                3 дня назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Rating changes happen some time after the contest (usually few hours). That's when your profile page section will be updated. If you want to know rating changes as soon as possible, there are some pretty accurate CF Predictors, that you can find just by googling them.

»
4 дня назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

This contest clash with the cook-off.....They should prepone or postpone the contest whichever is possible

»
4 дня назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

A lots of thanks to MikeMirzayanov and other involved organisers for rescheduling the round:)

»
4 дня назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Why can't CodeChef reschedule for CodeForces?

  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    Cause codechef scheduled the contest before codeforces

    • »
      »
      »
      3 дня назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      In that case, CodeChef two monthly short contest are always prescheduled... So does that mean CodeForces will always have to keep that in mind.. Only a bit unfair, But this also shows how considerate Codeforces is for all of us..

      • »
        »
        »
        »
        3 дня назад, # ^ |
          Проголосовать: нравится -7 Проголосовать: не нравится

        It depends on author/s. If author/s want to reschedule it, it will be rescheduled. If s/he doesn't, it will not.

»
4 дня назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Great another 2AM contest

»
4 дня назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

As a tester, I can say that the problems are really interesting!

  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Really interesting and a hard jump from C->D? Usually I have noticed Div-2 contests with five problems have a large jump in difficulties from C to D, hopefully this round is more balanced.

    • »
      »
      »
      4 дня назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      You see the thing is not that simple, say the author wants to have a difficult problem D (say rating of atleast 2000), for an average participant it requires 40-60 min atleast, so if C is also medium difficult most of them won't have to time solve D or even read E.So they generally make C a bit easy and make D and E kinda difficult, so though there is a huge gap in difficulty but still you will be able to attempt it properly. Though no idea how this contest is gonna be

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hope it will be nice contest, good luck for all participants and have fun!

»
3 дня назад, # |
Rev. 3   Проголосовать: нравится +28 Проголосовать: не нравится

stefdasca Can you leave a dot in comment section? So that we can upvote :p

»
3 дня назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

That's a good time for Chinese competitor!Thanks flaviu2001!

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what will be the scoring distribution? or is there a fixed scoring distribution for div2 rounds and I'm just not aware of it?

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Whoah that's really early round, gives me no time to have dinner. Anyways glhf

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

15 min to be ready (:

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for the video Editorial/Solutions.

»
3 дня назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Good time for a participant from India. Just after lunch full of Energy.

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In question B what does "adjacent by side" means does that exclude diagonal cells?

»
3 дня назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

all problems have nice music :) thanks <3

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Well, cool round! Problem C was sickkkk

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

problem B is very big brain.

»
3 дня назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

https://www.youtube.com/watch?v=ebgjlXyH9s8

Do watch the video editorial here

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится -43 Проголосовать: не нравится

Sorry, but it was a very stupid problem B.

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

The Kind of day i want to wake up to almost everyday during lockdown!!!

Afternoon — CF round

Evening — Kickstart

Night — CC round Cook Off

HAPPPYYYYYYYYYYYY!!!!!!!!!!!!!!!!!!!!!!!!!

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Usually comments start after the contest ends

»
3 дня назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

Gap between D and E is very Huggggggggge.

»
3 дня назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

stefdasca, flaviu2001, koala_bear00 You guys surely have a great taste in music:) I had never imagined that I would be introduced to new music via a contest!

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Am i the only person who find C much easier than B and regret for wasting too much time on B instead of solve C. Or i overcomplicated B?

Solution for C is simply,

R n-1

L n

L 2

Which takes about 15 minutes to come with idea and solve.

For B my idea is

Let b1 and b2 two adjacent cell of F and c1,c2,c3 be adjacent cell of b1 and b2.

Then i checked condition for possible cases which takes 1 hour to implement.

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Actually it was reverse for me,It took 20 min for B and an hour for C.

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    For me B was much much easier than C, I think it depends

  • »
    »
    3 дня назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    C wasn't obvious at all, at least not for me. I wasted 1 hour 45 minutes in it and no AC xD

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    For B it will be easier if you check two adjacent cells of S and two adjacent cells of F.

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Just make both the two cells at one end 0 or both the two cells at another end 1 or vice versa. check this condition I was first tried to implements bfs and got confused with conditions then I got this one. Though ~50 minutes are wasted. Here is my submission.

  • »
    »
    3 дня назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    It took me more time to understand C than solve B lol, So many misunderstandings in C for me

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    u can check only 2 adjacent cell of S, and only 2 adjacent cell of S as barriers to reach inside, no need for c1,c2,c3

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

ConstructiveForces...xD....nice problems. Here are my submissions..hope to pass ST. Still 20 short of Specialist tho :(

A
B
C

Any ideas on D?

  • »
    »
    3 дня назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Think about an alternative way of going to a neighboring cell.

    Path C6 == Path C1 + Path C5

    So, the cost of C6 = minimum of the cost of C6 and (cost of C1 + cost of C5)

    A similar approach for all other paths.

    • »
      »
      »
      3 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How did you got all possible ways of going from one cell to another?

      • »
        »
        »
        »
        3 дня назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        First, compute the optimal cost to all the directions, Then you need to do basic math to get the optimal answer.

        • »
          »
          »
          »
          »
          3 дня назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          And how did you get that maximum only addition of two paths will give minimum cost? Why not three or more?

          • »
            »
            »
            »
            »
            »
            3 дня назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            I don't think there exists any other optimal way except those two. You should try to observe the figure given in the problem.

          • »
            »
            »
            »
            »
            »
            3 дня назад, # ^ |
            Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

            For simplicity consider $$$C2$$$(pure right), only $$$C1,C2,C3$$$ can give some right component. If you include any of $$$C4,C5,C6$$$ then you must need extra $$$C1,C2,C3$$$. Say if you want to use $$$C6$$$ then your path will be sth like $$$C6,C2,C3 > C2$$$ or $$$C6,C1,C3,C3>C1+C3$$$.

            Therefore minimum cost of $$$C2$$$ will be $$$C2$$$ itself, or optimal $$$C1$$$ + optimal $$$C3$$$. In fact, the minimum cost of $$$C2$$$ will be $$$C2$$$ itself, or the original $$$C1$$$ + original $$$C3$$$.

            The proof based on no two consecutive directions are not optimal. Assume $$$C1,C2$$$ are not optimal, then $$$C1>C2+C6$$$ and $$$C2>C1+C3$$$. Adding two inequalities gives $$$C1+C2>C1+C2+C3+C6 \implies 0>C3+C6$$$. Contradiction. If minimum cost of $$$C2$$$ is optimal $$$C1$$$ + optimal $$$C3$$$, then optimal $$$C1$$$ must be itself, the original cost of $$$C1$$$.

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    After applying Floyd Warshall's Algorithm, you may use Greedy approach to find the answer.

    • »
      »
      »
      3 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Target cell can have huge coordinates, so how is a graph algorithm feasible here? Is there some trick to compress the graph or just some O(1) thing?

      • »
        »
        »
        »
        3 дня назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        I mean considering a graph with only seven vertices. Essentially to find the minimum cost to reach from $$$ (x,y) $$$ to $$$ (x+dx,y+dy) $$$.

  • »
    »
    3 дня назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    Optimal right move = min(c[2],c[3]+c[1]) and Optimal left move = min(c[5], c[4]+c[6])

    For positive x: You just gotta find where y lies w.r.t x. There will be 2 choices of movement if (y>x or y<0), and if 0<=y<=x there are 3 possible choices of movement, try to figure them out.

    for negative x: just put x=-x, y=-y and swap opposite Cs and do the same as positive x

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

ppl solved D with O(1)?? I keep getting wrong answer on testcase 3 too. Is O(1) method correct way? find enclosing axis then max three ways to reach point??

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I guess it is possible, but it seemed so troublesome to correctly consider all cases that I abandoned this idea

  • »
    »
    3 дня назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I guess you need to consider also max cases

    say you need to get to (7, 5)

    You can go 7 up-right and 2 down and this can also be optimal

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Yup thats how I did it, but among those 3 ways to reach a point, left and right movement have 2 ways each, I missed that part initially

»
3 дня назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

I just dont get why authors dont get it .. Giving such stories just confuses us ... It does not make any thing "cool about your set". It makes it worse.

Man on a serious note, I know coming up with a interesting plot is definetly tough but I dont want to know that what the hell your character wants to achieve then first grab the info of what is doing what .. and not to mention the names u come up on

»
3 дня назад, # |
Rev. 5   Проголосовать: нравится +8 Проголосовать: не нравится

I tried to hack the following solution for A by generating 1e4 test cases where 1e8<=a, b<=1e9. This solution should time out but I wasn't able to hack it. Can someone please help me why it didn't TLE ?

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        int min=0;
        long long a,b,temp;
        cin>>a>>b;
        for(int i=0; i<=b; i++){
            temp = (a^i)+(b^i);
            if(temp>min){
                min=temp;
            }
        }
        cout<<temp<<endl;
    }
return 0;
}
  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Actually the valuable $$$min$$$ and the loop doesn't do anything. After the loop, $$$temp$$$ is always set to $$$a\oplus b + b\oplus b = a\oplus b$$$, so the compiler ignored the loop.

    Unluckily, $$$a\oplus b$$$ is just the correct answer.

    • »
      »
      »
      3 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      So the compiler after few test cases realized that temp is being set to a^b and hence ignored thousands of other test cases ? Can you please elaborate a bit more ?

      • »
        »
        »
        »
        3 дня назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It's called as O2-optimization, you can google for more information.

        • »
          »
          »
          »
          »
          3 дня назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          I got -150 for this ;-; . I will definitely check for -O2 optimization.

          • »
            »
            »
            »
            »
            »
            3 дня назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Hello I did exactly same code but get TLE why?

                    cin>>a>>b;
            	mi=inf;//9e18
            	ans=0;
            	lp1(i,0,b)//for(ll i=0;i<=b;++i)
            	{
            		mi=min(mi,((a^i)+(b^i)));
            	}
            	cout<<mi<<endl;
            

            Submission

            • »
              »
              »
              »
              »
              »
              »
              3 дня назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              b can be upto 1e9. you can not traverse to 1e9. You need to optimise your code.

              You can read about O2 optimisation here

            • »
              »
              »
              »
              »
              »
              »
              2 дня назад, # ^ |
              Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

              This is not the same code. The code that gets optimized above is roughly equivalent to

              cin>>a>>b;
              mi=inf;//9e18
              ans=0;
              lp1(i,0,b)//for(ll i=0;i<=b;++i)
              {
                  mi=(a^i)+(b^i);
              }
              cout<<mi<<endl;

              So you can see that in the code above, mi is always overwritten in every iteration. This makes it easy for the compiler to realize that only the final iteration of the loop needs to be performed. (The submitter got lucky that this apparently incorrect code always gives the correct answer.)

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

B was so stupid because it was all about typing, annoying question imo.

Unless there's a better way of solving it..

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Only cells adjacent to start and finish matter.

    • »
      »
      »
      3 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes I know that, that's a very obvious observation and that's why its a stupid problem, its very easy to figure out the solution but implementing took a lot of time it was so frustrating.

      • »
        »
        »
        »
        46 часов назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Consider the set of the cells adjacent to S and F and flip the values of the cells adjacent to one of them. Then take the smallest of the two subsets of cells having the same value.

»
3 дня назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

C was just solving this test case — "abc"

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How to convert this to a palindrome ?

    • »
      »
      »
      3 дня назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      3 operations

      L 2 ==> babc

      R 2 ==> babcba

      R 5 ==> babcbab

      'babcbab' is a palindrome.

    • »
      »
      »
      3 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      abc

      Perform R 2

      abcb

      Perform L 3

      cbabcb

      Perform L 2

      bcbabcb

      Now just generalize this to a being the first character of the string, c being the last and b being all the ones in-between. This is actually how I solved it during contest as well.

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope not seeing comment section filled with memes this time

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it only me, who did B in 15 mins but struggled in C for an hour? C definitely was a good problem, but required some thinking, and took me an hour to come up with a 4 line solution :(

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I missed C by one second. As soon as I submitted, the contest ended:(

»
3 дня назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

we got speedforces again lol

  • »
    »
    3 дня назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    I coded D earlier than C

    So my rank is low (ノ ̄ー ̄)ノノ(º_ºノ)

    The 55-minute-long D makes me down. ╮(╯﹏╰)╭

»
3 дня назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Ohhhhhhh as a rock fan I looooove these discription! C and D were so cute!hard E,really. Like this contest!

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится -35 Проголосовать: не нравится

C is one of the worst Adhoc ever, you have to keep trying combinations until you get it, no clever obervation, no analysis, just have pattern aSb and keep trying.

B is equally annoying problem, so many if conditions, pure implementation

Really dissappointed

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    There is a clever observation to make first and last characters same and then apply both the operations one at a time . I dont know if this is clever or not but I was not clever!

    • »
      »
      »
      3 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you arrive at it without trying a zillion samples ?

      • »
        »
        »
        »
        3 дня назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Yes? Clearly distinct characters will be the most difficult case and 3 is the smallest n, so try 3 random distinct characters. This gets an easily generalizable answer. As for solving this case, I just checked for a sample with a distinct character at the end (sample 2) and used it as the basis.

        • »
          »
          »
          »
          »
          3 дня назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I can propose solns that will work for abcde but not for abcdef

        • »
          »
          »
          »
          »
          3 дня назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Exactly what I did just by seeing the problem but I was trying to do it int three operations. I thought there is a way since "abc" can be done in just 3 operations. but bad luck went in wrong direction earlier!

      • »
        »
        »
        »
        3 дня назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        L2 R2 R 2*n-1 would be clever lol .Yes just by thinking

        • »
          »
          »
          »
          »
          3 дня назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          It would have been, if you arrive at it with a proper algorithm,instead of noticing pattern in a few examples

          • »
            »
            »
            »
            »
            »
            3 дня назад, # ^ |
            Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

            And what is a "proper algorithm" for solving a problem?

            In my experience, nearly all problems break down to analyzing it (possibly with some small cases or simplifications or maybe just writing a brute force), noticing interesting properties and then getting some intuition about how to proceed.

            Even most problems requiring formal algorithms or some data structures usually require you to realize that some properties hold which makes you think of that approach.

      • »
        »
        »
        »
        3 дня назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        Test case 1 makes you realize that you can always do it in two moves if the first and third characters are the same. The rest is thinking if you can obtain such a string in a few moves.

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Nah, C had a very nice observation. You don't need to try many samples, just take a string where all characters are distict. If that works, everything else will work. After that its just a bit of thinking and 3 lines of code

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Firstly, $$$type 1$$$ operation will make a prefix of the string a palindrome and $$$type 2$$$ operation will make a suffix of the string a palindrome. A palindrome can have at most $$$1$$$ element having frequency $$$1$$$. Here in the given string, you cannot change the frequency of the first and the last element at the first operation. But if the first and the last element are different, then you must have one of them in some operation. So, first, you do $$$R \ n-1$$$, and then to double the frequency of the last element of the given input string, you do $$$L \ n$$$. Now, it is easy to see that, doing another operation will result in a palindrome.

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I will give you best answer

    Consider a non palindrome of two parts X|Y

    where | is middle point ok?

    lets take for example initital string => X1.X2.X3|Y1.Y2.Y3

    This must be worst case right?

    Now do L,'2'

    -> X2 .X1.X2.X3|Y1.Y2.Y3

    Now Do, R,'2'

    -> X2.X1.X2.X3.Y1.Y2.Y3. Y2.Y1.X3.X2.X1 (length be sz)

    Now Do R, (sz-1) where** sz** is length of string reached above

    -> X2.X1.X2.X3.Y1.Y2.Y3. Y2.Y1.X3.X2.X1. X2

    This is palindrome. Just use induction for all lengths of X and Y

    ez clap

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I did two bfs on B. smh

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for Tzuyu's reference in Problem A

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится +50 Проголосовать: не нравится

Is it just me or was this contest too much ad-hoc?? A,B,C,D all can be implemented in O(1), it was only about solving various test cases until you can see the pattern. I may be very wrong here but I think not much real programming or barely any Data structures and algos were used in this contest :/

»
3 дня назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Damn man, why all Constructive. Imma lose a 100 rating points, where gaining 14 would've put me over to CM. It was so hit or miss.

»
3 дня назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem B, is diagonal movement allowed?

»
3 дня назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Well... Instead of CM i I failed system test for problem B.
Granted, I did implement it in a disgusting way, bit it passes pretests :/

»
3 дня назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Solution for C was so easy :(

crying

»
3 дня назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Ad-hoc Missiles. I'm not complaining though :))

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

q.B was interesting and fun. The implementation was a bit big. I got wa on first attempt and at 2nd attempt, i had to just swipe 1 and 2 which i wrote wrong

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem B: Consider the grid as:

A B C ...
D E F ...
G H I ...

A = Start Case 1. if B=D=0 and C=E=G=1 then STUCK. Case 2. if B=D=1 and C=E=G=0 then STUCK.

We have to make anyone of the two cases in atmost two steps.

Is this logic correct?

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Logic only depends on, BD and HF.

    • »
      »
      »
      3 дня назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, this is also mentioned in editorial and I understood it. But why the above logic did not work? Am I missing something? Any idea.

      • »
        »
        »
        »
        3 дня назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Well, so my idea was like- He will start walking from (1,2) or (2,1) and enter F from (n,n-1) or (n-1,n). So, if (n,n-1)=(n-1,n), you just which one or whether both of (1,2) and (2,1) equals to (n,n-1)and print it else if (1,2)=(2,1), you just which one or whether both of (n,n-1) and (n-1,n) equals to (1,2) and print it else just see (1,2)/(2,1) is different from whether (n,n-1) or (n-1,n) and print both of them // (1,2)/(2,1) and the different one

      • »
        »
        »
        »
        3 дня назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I don't see any counter example for this strategy, i guess this should work well !

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Yeah, this works, I have implemented something similar.

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Your logic is correct. If $$$C=E=G$$$ then at most two steps. Otherwise there will be one of 0/1 appear two times, let's denote if by $$$x$$$. If at least one of $$$B,D$$$ is $$$y$$$ then set $$$C=E=G=x$$$ and $$$B=D=y$$$ which requires at most two steps. Else both $$$B,D$$$ are $$$x$$$, set the two $$$C,E,G$$$ with x to y.

»
3 дня назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

I think the Problem BCD are boring

»
3 дня назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Great contest, great songs. However, I should not have listened to them during the contest.

»
3 дня назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

This was a total disappointment since every question was a case work, I came here to solve the problems hoping to use my implementation and coding skills and not using my case work skills. I don't know about problem E but other 4 questions were total case work. Were you guys expecting us to write only if-else statements rather than using some great concepts out there?

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I wasted so much time on B. I had the solution but got mixed up on silly errors with the cases. Then for some reason I failed pretest 2 for a reason I can't see

»
3 дня назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

Was this contest unrated??

»
3 дня назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Problem E is so hard, so interesting, so mysterious. Thanks for the author's ideas and efforts!

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As soon as I read the first line of problem A, I was like — Aaaah... Imma kill this round... sad not all the problems had "twice" background.

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится -19 Проголосовать: не нравится

Note for C/C++ users: I lost problem D because I was doing negative % positive in the indexes of the c[] array. We know that (-1) % (6) should give 5 but in C/C++ when you do that you will get -1. So I wrote my own modulo to overcome this and I said it would be good to share it with you people:

#define mmod(a,b) ( (a >= 0) ? ((a%b)%b) : ( ( ( a + ( ((abs(a)+b)/b) * b ) ) % b ) % b ) )

Hope it help you and myself get out of Gold Nova! I mean Expert!

»
3 дня назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Problems B, C, and D were just if-else...Not so great round, Should rather call it speedforces, implementationforces, etc.

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have a Rating of 369 and I had solved 1 problem in this contest. Will my rating change as this is a Div 2 contest?

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I graduate to pupil for this round :) I'm so happy!!

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This round promoted me to Specialist.
Thanks for the wonderful round XD

»
3 дня назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

hello there, in the first question of Codeforces Round #676 (Div. 2) some test cases are wrong for the sake of understanding ..in one of the examples given in that question ..if we take a=28 and b=14 the output according to your code is 18 but

minimum possible answer is 10 if we take x as 4 28^4+14^4=10

  • »
    »
    3 дня назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    28^4+14^4==34 not 10 don't write like this in code because priority of '+' is greater than '^' so 28^4+14^4 will become 28^18^4 which is equal to 10 so write in code like this (28^4)+(14^4)

»
3 дня назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I was the first contestant to solve 1421C - Palindromifier, why didn't you put in the announcement people who were the first to solve each problem?

»
3 дня назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I found this because of your contest. Thank you :)

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I gave the contest and used ideone.com to write my code. Someone stole my code, because of which I was marked a violater. But I haven't done any type of cheating. How can I get my rating back??

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sorry we can't do anything about it, but in the future please don't use ideone or at least try to find a way to mark your source codes private.

»
2 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Of course, A little easy.

»
2 дня назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

Is no one going to speak about how incredibly cool the band references and music links were

»
43 часа назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

And yes! We are celebrating TWICE's 5th anniversary today.