By BledDest, 4 months 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 Ajosteen Glazov, Mikhail PikMike 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: hello@harbour.space

UPD: The contest is over.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Farhod_Farmon 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  

»
4 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Will hacking phase be just 12 hours from now on?

»
4 months 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

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

    We will, hacking lasts 12 hours

  • »
    »
    4 months 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.

»
4 months 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 :'(.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -33 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it -27 Vote: I do not like it

      Just like you'll never make it to Candidate Master

»
4 months ago, # |
  Vote: I like it +54 Vote: I do not like it

Hope to see good problems,not just implementations.

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

    Yeah true. Problem A and B should be implementation then after all problems must concentrate only on logic.

»
4 months ago, # |
  Vote: I like it +55 Vote: I do not like it

1000th contest

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I expected special round for anniversary contest :(

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

    To me, all rounds are special :)

  • »
    »
    4 months 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...

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

can i hack which problem i have not solved?

»
4 months 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

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

    thanks bro...

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

    I agree. It is annoying to wait 12 hours

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

    Couldn't agree more.

  • »
    »
    4 months 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.

  • »
    »
    4 months 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!

»
4 months ago, # |
  Vote: I like it +15 Vote: I do not like it

12 hours to hack is toooooooooo long.

  • »
    »
    4 months 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.

»
4 months ago, # |
  Vote: I like it -25 Vote: I do not like it

Messi Is back xD

»
4 months 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 ?

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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.

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

        nothing

      • »
        »
        »
        »
        4 months 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

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

        pleasure.

»
4 months 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

»
4 months ago, # |
  Vote: I like it +28 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it -27 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it -136 Vote: I do not like it

My brother is suffering from cold, Doctor said that he will feel good if I get upvotes here. I am new to codeforces and have no friends, will you help me?

»
4 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Problem A fucked me deep....

  • »
    »
    4 months 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.

»
4 months 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.

»
4 months ago, # |
  Vote: I like it -83 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What happened to 300iq ???

  • »
    »
    4 months 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)

»
4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months 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
»
4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G?

  • »
    »
    4 months 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.

  • »
    »
    4 months 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).

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve C?

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

    Classical scanline problem.

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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!

        • »
          »
          »
          »
          »
          4 months 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.

          • »
            »
            »
            »
            »
            »
            4 months 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?

            • »
              »
              »
              »
              »
              »
              »
              4 months 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)

              • »
                »
                »
                »
                »
                »
                »
                »
                4 months 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].

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

        You can read about it here.

      • »
        »
        »
        »
        4 months 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.

      • »
        »
        »
        »
        4 months 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.

  • »
    »
    4 months 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.com/contest/1000/submission/39725149

»
4 months ago, # |
  Vote: I like it -51 Vote: I do not like it

Codeforces contest is not as good as it was before .

»
4 months 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)

  • »
    »
    4 months 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).

    • »
      »
      »
      4 months 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

    • »
      »
      »
      4 months 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)

      • »
        »
        »
        »
        4 months 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

        • »
          »
          »
          »
          »
          4 months 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... :(

  • »
    »
    4 months 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

»
4 months 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

  • »
    »
    4 months 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.

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

Never mind, it is indeed diameter

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hacking page is not loading..!!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Problem C be solved using Mo's algorithm?

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months 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.

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

          Isn't this Mo's Algorithm?

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
            Rev. 3   Vote: I like it +4 Vote: I do not like it

            There are both Mo's algorithm and sqrt decomposition)

        • »
          »
          »
          »
          »
          4 months 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)?

          • »
            »
            »
            »
            »
            »
            4 months 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.

          • »
            »
            »
            »
            »
            »
            4 months 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 .

        • »
          »
          »
          »
          »
          4 months 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.

»
4 months 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

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months 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.

        • »
          »
          »
          »
          »
          4 months 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.

          • »
            »
            »
            »
            »
            »
            4 months 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.

»
4 months 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...

»
4 months 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 Е :(

»
4 months 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..

  • »
    »
    4 months 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.

»
4 months 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 ?

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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))

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

        this one is invalid test case .

      • »
        »
        »
        »
        4 months 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

        • »
          »
          »
          »
          »
          4 months 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.

  • »
    »
    4 months 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.

»
4 months 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?

  • »
    »
    4 months 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.

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

      how the answer of first test case is 2 ?

      • »
        »
        »
        »
        4 months 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.

»
4 months 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?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the approach to B? Thanks!

  • »
    »
    4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Anyone please explain D and E.

  • »
    »
    4 months 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].

    • »
      »
      »
      4 months 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?

      • »
        »
        »
        »
        4 months 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.

        • »
          »
          »
          »
          »
          4 months 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.

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

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

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months 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

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

          Oh okay! Completely missed that! Btw thanks for providing such a nice explanation!

»
4 months 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

»
4 months 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.

  • »
    »
    4 months 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.

  • »
    »
    4 months 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!

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

      Damn towards the end of the contest I had this idea but it was too late. Thanks for the explanation :)

»
4 months ago, # |
Rev. 2   Vote: I like it +154 Vote: I do not like it

That moment when your script hacks your own solution

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

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

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

    Could he use it in an non-educational round?

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

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

  • »
    »
    4 months 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...

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

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

»
4 months 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?

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

    of course

    • »
      »
      »
      4 months 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!

      • »
        »
        »
        »
        4 months 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.

      • »
        »
        »
        »
        4 months 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

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Come on ! Rating changes ?

  • »
    »
    4 months 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

»
4 months 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

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Capture

truly a hacker...

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

    I'm scared about systests now :(

    • »
      »
      »
      4 months 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?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

when can I get the solution and the rating changes?

»
4 months 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.

»
4 months 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.

»
4 months 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?

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

When will you publish the Editorial ?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months 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. )

»
4 months 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?

  • »
    »
    4 months 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?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your crafting.oj.uz ratings are updated!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am new to codeforces. Can someone tell when we can expect editorial for this round?

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it
»
4 months ago, # |
  Vote: I like it -17 Vote: I do not like it

It's expected a tutorial about how to solve the problems?

»
3 months 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 ?

»
3 months 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??