How did you solve the problems in today's paper ? What's the expected cutoff ?

general
,
21

I doubt the cutoff is less than 100.

Edit: If even idraumr only got 130 I doubt the cutoff is more than that.

22

sorry but I don’t think they are wrong at least my program gave correct answers on all the sample test data

1 Like
23

Am I the only one who thought that 1 problem was harder than the second one ?

1 Like
24

Nope. I thought the same. Problem 1 is definitely harder IMO.

1 Like
25

Yeah I don’t think they’re wrong.

1 Like
26

Haha, you flatter me. To be fair, I know a few getting in the upper 100s, and am myself scared of my chances.

I made disgustingly silly mistakes while attempting problem 1.

1 Like
27

@vikramnitin9 If you take away all strings of that length, you’d end up taking away strings like 00…000 and 11…11 more than once!

28

Yeah, so subtract 2 after raising every prime factor except 1. Those are the only two repetitions, I think. Am I right?

29

25-30 people will make it to camp, you know of only a few people getting higher than you. I don’t know of anybody (excluding myself). I honestly wouldn’t worry if I were you.

30

I’m surprised there wasn’t a graph question, I was convinced that there was going to be one graph and one DP.

31

Same! I wish there wasn’t a departure from the pattern, but sigh.

1 Like
32

You’re right I guess. Which anyway means that you’re taking the non periodic strings only (I don’t know why you said you’re taking away all strings of that length), considering that 1 gives 2 non periodic strings.

33

Are you saying that the number of periodic strings of length 1260 is less than 10^8?

There are 2^630 strings of length 630, and thus there are at least that many periodic strings of length 1260.

34

Just to clarify, as an example, what would be the correct approach if n=12?
12 = 1 x 4 x 3, so my approach would be (2^12)-((2^1) + (2^4 -2) + (2^3 -2))

So for 1260 = 1 x 4 x 9 x 5 x 7, I subtract (2^1)+(2^4 -2), etc

I have a vague feeling that there’s something wrong with this, though.

35

It’s correct, but the way I reached it is different:

2^12 - ((2^1) + (2^2 - 2^1) + (2^4 - (2^2 - 2^1) - 2^1) + (2^3 - 2^1))

36

So are the two ways exactly equivalent? In your method, do you also include (2^6 -2) ? And @sandy999, I did that intentionally, to combine both in one step. Eg: I wanted to take away 1010 and 0101 also. These are patterns for 2, but they can be merged with 4.

37

Yeah, didn’t notice that.

38

I don’t think so, I think they happen to be equivalent in this case.

39

My method must be wrong, because like you mentioned above, for 1260, I don’t take 2^630, only its individual factors.

40

last year was comparitively cakewalk. One question was direct Floyd warshall and the 1st question was difficult, but not impossible…