Educational Codeforces Round 46 [Rated for Div. 2]
By BledDest, 6 years ago, translation, In English

Hello, Codeforces!

On June 27, 17:35 MSK Educational Codeforces Round 46 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

As usual, the round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were prepared by Adilbek adedalic Dalabaev, Roman Roms Glazov, Mikhail awoo Piklyaev and me.

Good luck to all participants!

UPD. The editorial is here.

I also have a message from our partner, Harbour.Space University:

Hi Codeforces!

For our programming boot camp’s next iteration of Hello Barcelona Programming Bootcamp, Harbour.Space University in collaboration with Moscow Workshops ICPC, ITMO University, Moscow Institute of Physics and Technology, Saint Petersburg State University and Codeforces is bringing the best training practices and coaches to Barcelona to prepare 150 students for winning medals in the next ICPC World Finals.

It's extraordinary to see the entire cultural spectrum meet at the boot camp over a common love of programming and learning, and this autumn, we will be doing it again.

Our boot camp will once again feature the all-time greats Mike MikeMirzayanov Mirzayanov, Andrey andrewzta Stankevich, Michael Endagorion Tikhomirov, Gleb GlebsHP Evstropov, Artem VArtem Vasilyev, Ivan ifsmirnov Smirnov and other world renowned Russian coaches to train the participants.

Expect the most challenging problems, surprise guests and speakers, a branded hackathon, and finally the online round held on Codeforces, so everyone can join the onsite participants, at the finale of the event.

During the nine days of the event from Sept 26 to Oct 4, 2018 in Barcelona, teams will be participating in practice contests, problem discussion sessions and lectures.

Learn more about Barcelona ICPC Bootcamp

You can ask any questions by email: [email protected]

UPD: The contest is over.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Farhod 7 353
2 MrDindows 7 362
3 tzuyu_chou 6 205
4 Wild_Hamster 6 248
5 spj_29 6 252

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 225:-5
2 MarcosK 22:-3
3 sfialok98 5
4 Rhouma 4
5 FakeGuy 3
307 successful hacks and 245 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A 300iq 0:01
B HIT_Zero 0:13
C Dalgerok 0:07
D ruhan.habib39 0:08
E Dalgerok 0:14
F MrDindows 0:17
G chemthan 1:13

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

Comments Comments (187)
| Write comment?
»
6 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Will hacking phase be just 12 hours from now on?

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

Hope we won't wait till the next morning of the contest to know the result and rating changes :D

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

    We will, hacking lasts 12 hours

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

    But I have to wait until the next afternoon (or the next evening, for the poor speed of system testing and rating changing) as a Chinese. I just want to have a good sleep (instead of staying up late) and can see the rating changes as soon as I get up.

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

What does Codeforces have against Mexicans? That's two rounds at the same time as Mexico's matches in the World Cup :'(.

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

    luckily for you they never make it past the fourth game.

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

      Just like you'll never make it to Candidate Master

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

Hope to see good problems,not just implementations.

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

1000th contest

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

I expected special round for anniversary contest :(

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

    To me, all rounds are special :)

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

    Maybe it is a special round? Maybe there will be fast syste... Oh no, fast systests won't help, there is 12 hours long hacking phase...

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

can i hack which problem i have not solved?

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

Most of the hacking is done in first 2-3 hours. Mininize hacking phase to only 6 hours

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

    I agree. It is annoying to wait 12 hours

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

    But then Chinese will have to not only stay up to participate in contests, but also keep staying up after the contests to hack.

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

    Mmm... I made 16 hacks in the last 4 hours of hacking phase, and only 6 in the first 2 hours. I think 24 hours was too much, but 12 hours is not that bad!

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

12 hours to hack is toooooooooo long.

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

    I agree with you. The rating changes are always come out at the second day when we have an Educational or Div. 3 round.

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

What does one mean by hacking problems? This would be my first contest of this type. Can someone please guide regarding the rules and terms ?

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

    After The Contest ended.....everyone Can See your solution and if he found anything wrong he can hack you and the problem won't be Accepted

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

      If my solution gets hacked, it will not be accepted and I will lose points, what will the hacker get ? Thanks for the reply.

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

        nothing

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

        in Educational Contest He Won't Get Any Thing Except if he made a lot of hacks he will became from most hackers of Contest But Also he won't Get any Points.

        But in Usual Contests He Can Hack participants in his room in Codeforces after locking his problem and if he hacked any one he will get 100 points and if he make Hack But it was unsuccessful He will lost 50 points

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

        pleasure.

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

The 12 hour hacking seems to be useless as no one will waste that long time once they comes up with some hacks they tries them and leaves the site.

I can't understand why i am getting this many downvotes

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

Seems people are agreeing on minimizing the hacking phase...

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

i thinks educational hacks shoud give some (points) (reduce time)

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it -136 Vote: I do not like it

now he is dead

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

Problem A fucked me deep....

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

    The weird thing is you commented this in the middle of the contest!! Man, during the contest you should concentrate only on solving problems.

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

problem E is not clear at all and explanation for the sample input/output is also missing.

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

code force is retarded. edu round is dumb. your all dumb

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

What happened to 300iq ???

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

    Left a record in the standings of contest 1000 and plunged into problem preparation. (I guess)

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

Nice contest, thanks, problems B, D and E are really nice. Problem A kinda awful though.

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

TASK F looks for wavelet tree or persistent segtree's.

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

    You can do F with regular segment tree.

    The idea is to sort queries by start-index, and only keep indexes i, such that index i is the first time number V[i] appears in [start-index, n).

    For each such number, store where the next same number is.

    Now, you just want to find the maximum element in an interval. If it's not large enough, answer is 0. Otherwise, its value is the answer.

    When moving to the next query, loop from last-start-index to start-index — 1, deactivate those indexes, and activate indexes of their values's next appearances.

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

A & B & C are mostly implementation problems. Is this really Educational round? Educational rounds used to be different.

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

How to solve G?

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

    What is the story behind your username mango_lassi? You don't seem Indian to me.

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

    Key idea, in my opinion, is to calculate for each i dpi — maximal profit of 2-path starting at i and finishing at i. If i is a root of tree, then dpi is just pretty standard dp for subtrees. To calculate dp for each vertex as if this vertex is root — it's possible with technique of "rerooting" (actually, I don't know it's real name as I don't know where to find materials to this quite standart technique).

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

How to solve C?

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

    Classical scanline problem.

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

      Explain pls. I know its easy (got that by seeing the number of solves) but I couldn't figure it out.

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

        What would we do if constraints were small? Use partial sums!
        So now we can do similar thing just using map instead of arrays for partial sums.
        How to solve D though?
        P.S : I think there is even a way of doing it without using maps. I am unaware of that sorry!

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

          Let dp[i] denote number of good subsequences ending at i. So a subsequence will be divided into parts which are good. Now look at the last part of the subsequences which end at i. Let the start of the last part of that subsequence be j. So dp[i] = sum(((pref[j-1]+1)*ncr[i-j-1][a[j]-1])) because we have to choose a[j]-1 elements between i and j to complete that part and the subsequence can be completed by the rest of the parts ending before j.

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

            Why are you adding +1 to pref[j-1] when taking the summation?

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

              Suppose you have m queries with l and r.(Array of size n)

              Now you can traverse the array 10 times incrementing values between l and r.It take Time Complexity O(n*m). OR u can put +1 on l position and -1 on r+1 position.After inserting u can just traverse the array a single time to get the final array.O(m+n)

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

                No i got how to solve C. I was talking about D and T1duS's method as to why we are adding +1 to pref[j-1]. I got it though. It's because one of the subsequences would be starting at j and ending at i and we ignore the subsequences before that. Add those many subsequences to the number of subsequences starting at j and ending at i multiplied to the number of ways of ending subsequences at j-1. That will be the ans for dp[i].

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

        You can read about it here.

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

        For a given segment say [x y] mark x with +1 and y+1 with -1 and store it. Now just visit these points and check the running sum,and update the running sum on a array with the number of coordinates in between,i.e a[running sum]+=numberofcoordinates,print this array from 1 to n as given.

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

        What I did was create a map with the # of the segments that started and ended at a certain point. Then I traversed the points in order, keeping a variable that kept track of the current number of segments. I treated the intervals (spaces between points) and the endpoints separately. Make sure to use long longs.

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

    keep a map of indices of segments and use it as partial sum. Though it struck me a little late. Solution(Easy to understand)->http://codeforces.me/contest/1000/submission/39725149

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

Wanna ask a question:

What should a person do after finishing problems he can do in an Educational Round?

(As for me, only problem G left, and I have about 20 minute, then I know how to solve G but I know I can't finish in 20 minutes.

Then I have nothing to do in these 20 minutes: sitting there pushing F5 and seeing my rank falling.

So guys, how do you handle these time ? :) (One may hack in a normal round)

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

    I would do nothing, but enjoy looking at standings (because you solved 6 problems).

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

      But you didn't...... Edit: Oh I see what you mean, never mind

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

      Well bro, I didn't find you in the standing ???

      I don't know, maybe you are an accurate one, so waiting won't be a bad choice.

      But almost every contest I participated, I "die from" penalties(wrong submition). So even if I finished early, many who finished after me will have a higher rank than me.

      How should I deal with that? (Yeah, yeah, yeah, control my hands)

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

        Here I meant you solved 6 problems.

        But almost every contest I participated, I "die from" penalties(wrong submition). So even if I finished early, many who finished after me will have a higher rank than me.

        Yeah, you're right, but if they add feature that allows to hack solutions during the contest there is no need to hold special educational rounds, so I still recommend you to enjoy from your results XD

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

          Sorry I misunderstood you.

          And feel guilty that I downvoted you yesterday. :(

          Please forgive me.

          P.S.: But still, I didn't solve 6 problems... :(

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

    try to find bugs in your own solutions so they don't get hacked

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

For E does this work?

1) Find all cycles, and mark each edge in a cycle with 0 (and keep all other edges marked 1)

2) Start at a random node, and find the farthest node from it through a DFS, but by "farthest" i mean weighted distance where the markings denote weight. Denote this farthest node X

3) Similarly find the farthest node from X (with weighted distance, where edges in cycles are distance 0 and edges not in cycles are distance 1), denote this node Y.

Y is the answer

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

    Yes. Though an easier way to think about it is diameter of bridge tree.

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

Never mind, it is indeed diameter

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

Hacking page is not loading..!!

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

Can Problem C be solved using Mo's algorithm?

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

    C? I don't think so. Doesn't even look like a Mo problem.

    Though F definitely has a Mo solution :D Our model implementation works a bit over TL (like 3.4 seconds) but couple of participants actually squeezed it.

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

      Can you please explain how to keep answer? I used unordered set, but I still getting TL

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

        You can store not the hashset but the whole array of number counts. Then you do sqrt decomposition over this array, you make updates in O(1) and then ask in . I believe, the code is pretty much self-explainatory.

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

          Isn't this Mo's Algorithm?

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

            There are both Mo's algorithm and sqrt decomposition)

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

          What is the time complexity of such a solution, wouldn't using a set reduce it (despite large constants)?

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

            It's , I believe. No idea how to make a good use of set in that case.

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

            More precisely, In this task, using Mo's Algorithm, you will need to move left and right borders times, but asking for any element you will make no more than m times, so using sqrt-decomposition gives you slow asking operation (), but fast move operation (O(1)). In result you will get .

            On the other hand, using set will give you same complexity for asking and move operation, so result complexity will be .

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

          I tried to implement this idea but I got TLE, it seems that the comparator you used is the key to get Accepted, the solution passed in under 2 seconds after I tried it, can you explain how it works ?

          Update: I figured it out, this is a very clever trick :D The parity thing makes a block continue working from the index that the previous block finished working. This means that inside some block, the right index of mo's algorithm will keep increasing until it reaches the end, for the next block, it will keep decreasing while answering queries in the opposite direction instead of removing all the elements then increasing the right index from the beginning.

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

in problem C it happened for the first time that PYPY gave TLE and python 2 passed in 2345ms. When I saw the accepted solutions in pypy, there were only three and their time was also quite borderline. How can pypy be slower than python 2

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

    I would like to know the same. My submission got TLE during contest: 39712202. Fearing that the time limit is too strict I switched to C++. And here's my practice submission with an AC: 39725290

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

      cases are too harsh I guess. I guess during main test cases after the 12 hours hacking period python solutions might also fail

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

        Our python3 implementation of it works in 2137ms, we dicided that about 1 second off TL is fine for this.

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

          yeah even python 2 solution worked well within TL. It's just that how come pypy gave a slower output than python. This rarely happens.

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

            Yeah, we didn't really expect that. Unfortunately, we had no way to test it as polygon doesn't support pypy.

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

I thought implementation for A is too heavy (for usual A in educational) until I see this submission...

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

if only the round would be extended for 1 minute, I would solve Е :(

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

E is about finding the diameter of the tree of cycles, right?

But how do you find and isolate each cycle? Tarjan's algorithm only works in directed graphs and I couldn't figure out how to apply it on undirected ones..

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

    You can find the bridges of a graph with Tarjan's like this. With them, you will then be able to combine all the nodes that share some cycle. And you will end up with a tree.

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

maybe i should be saying sorry for this question , but can someone please explain to me A and why n — (all the sizes that are the same in old and new t-shirts sizes) is an logical answer ?

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

    Because you need only 1 second to change one size to another if they have equal length. The answer can't be less because you need to change at least this number of strings.

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

      and if there a test case where input is

      1

      XS

      XXXL

      how can a code like the one i described be good ?

      ((sorry if i just misread or didn't understand the problem))

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

        this one is invalid test case .

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

        1) You can only change letters, not add or remove
        2) It is guaranteed that you can get one list from another

        So this test is incorrect

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

          Thanks Numb and anno

          sorry if i wasted your time with my -3 IQ.

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

    lets take all the t-shirt name of lenght 3 that is xx_ so in old t-shirt either it will be present or absent so if it is absent so we only need to change the last character but if it is present we can use that and we cannot reduce or increase the length of the names so we will only consider length 3 similarly for all.

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

can anyone help me to understand the problem statement of E problem and the output of the given test cases?

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

    You need to find two vertices s and t such that the number of bridges on the way from s to t is maximized.

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

      how the answer of first test case is 2 ?

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

        pick s = 4 and t = 5, then you have two bridges (4, 1) and (5, 2) on the way from s to t.

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

May someone please tell me why my solution for A 39724005 is wrong?

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

Can anyone explain the approach to B? Thanks!

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

    Basically you should notice that the best is to insert the new number just next to some a[i] or just before it.

    So you can try all possibilites. To do that, could be a good idea to have an accmuluate array that tells how many time is on from number i to the end. Then you can go from left to right and get the answer for every possible insertion and take maximun.

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

Can Anyone please explain D and E.

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

    Let's denote with dp[i] the number of good subsequences of the array a[i...n-1], and define dp[n] = 0.

    The good subsequences of dp[i] either use the element a[i] or they don't. There are dp[i+1] good subsequences that don't contain a[i]. So we only need to count those that do.

    These subsequences might contain multiple good arrays. Let's focus on the first one. Its size is exactly a[i] + 1. If a[i] <= 0 then there are obviously no good array starting with a[i]. So assume that a[i] > 0 iterate over the last element in this good array. It can be any element a[j] with i + a[i] <= j <= n-1, and there are nCr(j - i - 1, a[i] - 1) possibilities to pick the middle elements of this good array. We count this sequence alone, and we can also combine it with each good subsequence in dp[j+1].

    Therefore we get the recursion:

    And the solution to the problem is dp[0].

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

      Hi, I followed your solution, however the recurrence relation gave me 1 more than the answer and I don't quite understand why. Could you explain this?

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

        Do you mean my implementation? I used a slightly different definition. I defined the empty array as a good subsequence, so at the end I have to subtract this one.

        This is a submission that corresponds directly to the explanation: 39734194

        Btw, there was a little error my comment above. I forgot the  + 1. But now it is fixed.

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

          Why you added +1 to dp[j+1] before multiplying to that nCr formulae. I didn't got that.

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

      That was a very pretty solution. Thanks a ton. I got that

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

      Why have you added 1 in your formlula? I know that simply dp[j+1] won't give the right answer but (dp[j+1]+1) will give but I am not able to get the idea behind adding 1. Sorry for such a silly question

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

        You can either combine the good array starting at i and ending at j with any of the good subsequences in a[j+1...n-1] => multiply by dp[j+1]

        Or you can only use the subsequence alone (without combining it with other subsequences) => + 1

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

Any one solved F using MO's Algo within TL ? UPD: 39735901

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

Can someone please help out with Problem C?

Thanks! I don't see a way to start. The tag said "SORTING," but I am not sure how to even apply it here.

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

    The keyword is "Sweep line algorithm".

    Basically you convert each segment [l, r] into two events (l, begin), (r, end), sort all those events and compute the answer by iterating over the events. At each event point you can compute the answer for the last interval [last_event + 1, current_event - 1] in constant time, since the number of segments doesn't change in this interval.

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

    This is actually a classic geometry concept, which is called "Line Sweep". It's called that because we can imagine a vertical line moving from left to right, covering all the points lying on the x-axis one-by-one. What we do is, store all the segments(x, y) separated in an array, with each element being (val, isStart), where val is either x or y, and isStart is 1 if it's an x value, and 0 if it's a y value.

    After storing all the segments this way in an array, we sort them according to their value. Then, we perform the sweep while keeping a counter open for the number of segments that are currently open. When we come across a value where isStart is true, that means that a segment is starting at this point, so we increase our counter open. And when we come across a value whose isStart is false, we decrease the counter open.

    This way at any point we know exactly how many segments are covering it, and using this we can find how many points have open number of segments covering them.

    Here is a tutorial blog about the line sweep technique: link

    And, here is my code for this question: link

    If you need any more explanation, do let me know!

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

That moment when your script hacks your own solution

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

    Can I get the code for the script? Is it open source?

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

    Could he use it in an non-educational round?

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

      No, you cant copy solutions, and it is forbidden by rules.

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

    And it is the first test I tried to use for hacking. If only I checked this corner case during the contest...

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

    Ironic. He could save others from hacks, but not himself.

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

Do all hacks run against all submissions at the end of hacking phase?

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

    of course

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

      I was doubtful because I checked the contest page after 5 minutes of end of hacking phase and it said 'Final standings'. I wonder how they managed to run all the codes on all the hacks so quickly!

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

        We need to wait for final testing. 'Final standing' is not final standing yet.

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

        Yeah it is not the true 'Final Standing'。Maybe System will rejudge soon

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

Come on ! Rating changes ?

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

    Time taken to update rating is directly proportional to the amount of rating you are going to gain xD

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

For problem E this is an excellent link by IIIT Hyderabad threads on quora: https://threads-iiith.quora.com/The-Bridge-Tree-of-a-graph

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

Capture

truly a hacker...

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

    I'm scared about systests now :(

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

      Yes, by this time I think they should've been updated the ratings no? Or educational rounds take this much time usually?

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

when can I get the solution and the rating changes?

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

I found two pairs of people, which have one solution — 39722722 and 39716743; 39723479 and 39714675.

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

One of the best educational round I could see on codeforces, in terms of quality problems. Though I couldn't participate in the round.

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

The systest is really fast, but the rating changing is too slow... Maybe make it faster?

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

    Systests were faster because they only need to check for the hack tests.

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

When will you publish the Editorial ?

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

Eagerly waiting for the editorials..when will they come?

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

Can F be solved with a mergesort tree? ( By keeping all the elements which occur once in the nodes. Also, merging is easy. )

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

Why is this code for problem C giving run time error on testcase 4?

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

    You compare operator doesn't make any sense. sort expects that the compare operator cmp(p, q) returns true, if p should appear before q in the sorted order.

    But with you implementation, and using two element p = {1, 'l'} and q = {1, 'l'}, both cmp(p, q) == true and cmp(q, p) == true. So of course C++ is confused. How can an element p appear before q and behind q at the same time?

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

When will you publish the editorial? I'm eager to read it :-)

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

The editorial is published.

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

I tried to do problem E by compressing the cycles to a single node.My solution is running on my computer compiled with command g++ -std=c++14 but on submitting it is giving an error.

Diagnostics detected issues [cpp.clang++-diagnose]: =================================================================
==3384==ERROR: AddressSanitizer: heap-use-after-free on address 0x00f015dd at pc 0x010bb4ad bp 0x1179f0d4 sp 0x1179f0d0
READ of size 1 at 0x00f015dd thread T0
==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_symbolizer_win.cc:64 "((dbghelp && "failed to load dbghelp.dll")) != (0)" (0x0, 0x0)
==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff)
==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff)
==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff)
==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff)
==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff)
==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff)
==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff)
==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff)
==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff)
==3384==AddressSanitizer CHECK failed: C:\src\llvm_package_600-final\llvm\projects\compiler-rt\lib\sanitizer_common\sanitizer_win.cc:795 "((owner_)) == ((LOCK_READY))" (0x4ac, 0xffffffff)

Here is my solution. Any help ?

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

I have a strange behavior for my solution for Problem 1000G - Two-Paths. If I read integers with cin my solution (39859090) is Accepted. If I use scanf (39859098) or getchar (39859106) I receive "Wrong answer on test 9". How is that possible? In getchar-version I even checked whether input is fine, which seems to be the case (otherwise I would have received a Runtime Error). Can somebody figure out the reason?

Update: Found a small bug (using index outside of range of vector) and now it works (39861715). But the question remains: How can it make a difference whether I read with cin or scanf??

→ Reply